結果
問題 | No.1211 円環はお断り |
ユーザー |
|
提出日時 | 2020-08-30 16:37:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,722 ms / 2,000 ms |
コード長 | 1,076 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 279,480 KB |
最終ジャッジ日時 | 2024-11-23 16:25:57 |
合計ジャッジ時間 | 25,890 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
import sysinput = lambda : sys.stdin.readline().rstrip()sys.setrecursionlimit(max(1000, 10**9))write = lambda x: sys.stdout.write(x+"\n")n,k = list(map(int, input().split()))a = list(map(int, input().split()))aa = a + as = sum(a)def sub(x):if s<x*k:return Falsel = [None]*nv = a[0]j = 0for i in range(n):if j<i:j = iv = aa[i]while v<x:j += 1v += aa[j]l[i] = (j-i)+1v -= a[i]kk = 1dp = [l]while kk<n:tmp = [(dp[-1][i]+dp[-1][(dp[-1][i]+i)%n]) for i in range(n)]dp.append(tmp)kk *= 2vals = [0]*nindex = list(range(n))for j in range(kk):if (k>>j)&1:for i in range(n):vals[i] += dp[j][index[i]]index[i] += dp[j][index[i]]index[i] %= n# print(l, dp, x)return any((vals[i]<=n) for i in range(n))ll = 0rr = s+1while ll<rr-1:m = (ll+rr)//2if sub(m):ll = melse:rr = mprint(ll)