QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798201#5417. Chat ProgramvwxyzRE 0ms0kbPython31.2kb2024-12-04 09:39:332024-12-04 09:39:34

Judging History

你现在查看的是最新测评结果

  • [2024-12-04 09:39:34]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-12-04 09:39:33]
  • 提交

answer

import heapq
from collections import defaultdict
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item

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,M,C,D=map(int,input().split())
A=list(map(int,input().split()))
inf=1<<50
def is_ok(x):
    retu=False
    cnt=[0]+[int(a>=x) for a in A]
    for i in range(1,N+1):
        cnt[i]+=cnt[i-1]
    for l in range(N-M,-1,-1):
        r=l+M
        if l==N-M:
            MS=Multi_Set([A[n]+C+n*D for n in range(l,r)])
        else:
            if A[r]+C+r*D<x+D*l:
                MS.discard(A[r]+C+r*D)
            MS.push(A[l]+C+l*D)
        while len(MS) and MS.Top()>=x+D*(l-1):
            MS.pop()
        c=cnt[l]+cnt[N]-cnt[r]
        if D*(l-1)<inf:
            c+=r-l-len(MS)
        if c>=K:
            retu=True
    return retu
ans=Bisect_Int(0,inf,is_ok)
print(ans)

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

6 4 3 1 2
1 1 4 5 1 4

output:


result: