結果

問題 No.1211 円環はお断り
コンテスト
ユーザー vwxyz
提出日時 2023-03-30 22:33:39
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,400 bytes
コンパイル時間 91 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 53,112 KB
最終ジャッジ日時 2024-09-22 07:27:32
合計ジャッジ時間 4,443 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 13 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline=sys.stdin.readline

class Path_Doubling:
    def __init__(self,N,permutation,lst=None,f=None,e=None):
        self.N=N
        self.permutation=permutation
        self.lst=lst
        self.f=f
        self.e=e

    def Build_Next(self,K=None):
        if K==None:
            K=self.N
        self.k=K.bit_length()
        self.permutation_doubling=[[self.permutation[n]] for n in range(self.N)]
        if self.lst!=None:
            self.doubling=[[self.lst[n]] for n in range(self.N)]
        for k in range(1,self.k):
            for n in range(self.N):
                if self.permutation_doubling[n][k-1]==None:
                    self.permutation_doubling[n].append(None)
                    if self.f!=None:
                        self.doubling[n].append(None)
                if self.permutation_doubling[n][k-1]!=None:
                    self.permutation_doubling[n].append(self.permutation_doubling[self.permutation_doubling[n][k-1]][k-1])
                    if self.f!=None:
                        self.doubling[n].append(self.f(self.doubling[n][k-1],self.doubling[self.permutation_doubling[n][k-1]][k-1]))

    def Permutation_Doubling(self,N,K):
        if K<0 or 1<<self.k<=K:
            return None
        for k in range(self.k):
            if K>>k&1 and N!=None:
                N=self.permutation_doubling[N][k]
        return N

    def Doubling(self,N,K):
        if K<0:
            return self.e
        retu=self.e
        for k in range(self.k):
            if K>>k&1:
                if self.permutation_doubling[N][k]==None:
                    return None
                retu=self.f(retu,self.doubling[N][k])
                N=self.permutation_doubling[N][k]
        return retu

def Bisect_Int(ok,ng,is_ok):
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if is_ok(mid):
            ok=mid
        else:
            ng=mid
    return ok

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
sum_A=sum(A)
A=[0]+A*2
for i in range(1,2*N+1):
    A[i]+=A[i-1]
def is_ok(ans):
    perm=[None]*(2*N+1)
    r=0
    for l in range(N):
        while A[r]-A[l]<ans:
            r+=1
        perm[l]=r
    PD=Path_Doubling(2*N+1,perm)
    PD.Build_Next()
    for i in range(N):
        x=PD.Permutation_Doubling(i,K)
        if x!=None and x<=i+N:
            return True
    return False
ans=Bisect_Int(0,sum_A+1,is_ok)
print(ans)
0