Submission #66360881

Source Code Expand

Copy
n,d,r=map(int,input().split())
h=list(map(int,input().split()))
from atcoder.segtree import SegTree
lis=[-1]*n
dp=SegTree(max,-1,lis)
hh=[(h[i],i) for i in range(n)]
hh.sort()
ans=[0]*n
p=0
for i in range(n):
    hi,now=hh[i]
    lim=hi-d
    while p<i and hh[p][0]<=lim:
        _,jj=hh[p]
        dp.set(jj,ans[jj])
        p+=1
    ll=max(now-r,0)
    rr=min(now+r,n-1)+1
    best=dp.prod(ll,rr)+1
    if best>=0:
        ans[now]=best
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
n,d,r=map(int,input().split())
h=list(map(int,input().split()))
from atcoder.segtree import SegTree
lis=[-1]*n
dp=SegTree(max,-1,lis)
hh=[(h[i],i) for i in range(n)]
hh.sort()
ans=[0]*n
p=0
for i in range(n):
    hi,now=hh[i]
    lim=hi-d
    while p<i and hh[p][0]<=lim:
        _,jj=hh[p]
        dp.set(jj,ans[jj])
        p+=1
    ll=max(now-r,0)
    rr=min(now+r,n-1)+1
    best=dp.prod(ll,rr)+1
    if best>=0:
        ans[now]=best
    else:
        ans[now]=0
print(max(ans))

Submission Info

Submission Time
Task F - Athletic
User juten
Language Python (PyPy 3.10-v7.3.12)
Score 500
Code Size 506 Byte
Status AC
Exec Time 1768 ms
Memory 157656 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 39
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 249 ms 84700 KiB
00_sample_01.txt AC 137 ms 84496 KiB
01_test_00.txt AC 170 ms 86836 KiB
01_test_01.txt AC 172 ms 88040 KiB
01_test_02.txt AC 135 ms 84412 KiB
01_test_03.txt AC 143 ms 85588 KiB
01_test_04.txt AC 172 ms 87956 KiB
01_test_05.txt AC 172 ms 87900 KiB
01_test_06.txt AC 895 ms 128060 KiB
01_test_07.txt AC 1653 ms 156300 KiB
01_test_08.txt AC 526 ms 103884 KiB
01_test_09.txt AC 402 ms 99592 KiB
01_test_10.txt AC 536 ms 106532 KiB
01_test_11.txt AC 1405 ms 150532 KiB
01_test_12.txt AC 588 ms 109548 KiB
01_test_13.txt AC 211 ms 90620 KiB
01_test_14.txt AC 460 ms 100324 KiB
01_test_15.txt AC 361 ms 99392 KiB
01_test_16.txt AC 1085 ms 133564 KiB
01_test_17.txt AC 1352 ms 140376 KiB
01_test_18.txt AC 1680 ms 157592 KiB
01_test_19.txt AC 1717 ms 156124 KiB
01_test_20.txt AC 1580 ms 157340 KiB
01_test_21.txt AC 1768 ms 157656 KiB
01_test_22.txt AC 1623 ms 157376 KiB
01_test_23.txt AC 1744 ms 156960 KiB
01_test_24.txt AC 1502 ms 155176 KiB
01_test_25.txt AC 1267 ms 155784 KiB
01_test_26.txt AC 1264 ms 155744 KiB
01_test_27.txt AC 404 ms 153008 KiB
01_test_28.txt AC 474 ms 155328 KiB
01_test_29.txt AC 507 ms 153860 KiB
01_test_30.txt AC 899 ms 156120 KiB
01_test_31.txt AC 885 ms 155584 KiB
01_test_32.txt AC 890 ms 155704 KiB
01_test_33.txt AC 916 ms 156336 KiB
01_test_34.txt AC 919 ms 156436 KiB
01_test_35.txt AC 866 ms 155716 KiB
01_test_36.txt AC 144 ms 84252 KiB
Facebook Twitter Telegram Share

2025-05-31 (Sat)
22:52:17 +09:00

More…