結果
問題 | No.2500 Products in a Range |
ユーザー |
|
提出日時 | 2023-10-13 22:28:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 361 ms / 2,000 ms |
コード長 | 2,325 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 76,288 KB |
最終ジャッジ日時 | 2024-09-15 18:13:27 |
合計ジャッジ時間 | 8,721 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
def solve(n,l,r,A):minus = []plus = []zero = []for a in A:if a < 0:minus.append(a)elif a > 0:plus.append(a)else:zero.append(a)minus.sort()plus.sort()ans = 1def solve1(plus,minus):ans = 1minus += zerominus = minus[::-1]plus = zero + plusfor i in range(len(minus)-1):for j in range(i+1,len(minus)):l1,l2 = minus[i],minus[i+1]r1,r2 = minus[j],minus[j-1]if l1*l2 >= l and r1*r2 <= r:ans = max(ans,j-i+1)for i in range(len(plus)-1):for j in range(i+1,len(plus)):l1,l2 = plus[i],plus[i+1]r1,r2 = plus[j],plus[j-1]if l1*l2 >= l and r1*r2 <= r:ans = max(ans,j-i+1)if ans > 1:return ansfor i in range(len(minus)):for j in range(i):if l <= minus[i]*minus[j] <= r:ans = 2for i in range(len(plus)):for j in range(i):if l <= plus[i]*plus[j] <= r:ans = 2return ansdef solve2(plus,minus):plus = zero + plusminus = minus[::-1]ans = 1for i in range(len(plus)):for j in range(len(minus)):l1 = plus[i]if i:l2 = plus[i-1]else:l2 = 0r1 = minus[j]if j:r2 = minus[j-1]else:r2 = 0if l1*l2 <= r and r1*r2 <= r and l1*r1 >= l:ans = max(ans,j+i+2)return ansdef solve3(plus,minus):ans = 1for p in plus:for m in minus:if l <= p*m <= r:ans = 2return ansif l >= 0:ans = solve1(plus[:],minus[:])elif r < 0:ans = solve3(plus[:],minus[:])else:ans = max(solve1(plus[:],minus[:]),solve2(plus[:],minus[:]))assert ansreturn ansn,l,r = map(int,input().split())A = list(map(int,input().split()))ans = solve(n,l,r,A)print(ans)