QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798201 | #5417. Chat Program | vwxyz | RE | 0ms | 0kb | Python3 | 1.2kb | 2024-12-04 09:39:33 | 2024-12-04 09:39:34 |
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