Submission #66357155

Source Code Expand

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

Submission Info

Submission Time
Task F - Athletic
User juten
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 405 Byte
Status WA
Exec Time 1803 ms
Memory 158328 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 2
WA × 37
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 121 ms 84692 KiB
00_sample_01.txt AC 119 ms 84336 KiB
01_test_00.txt WA 154 ms 87148 KiB
01_test_01.txt WA 150 ms 87588 KiB
01_test_02.txt WA 122 ms 84612 KiB
01_test_03.txt WA 131 ms 85724 KiB
01_test_04.txt WA 156 ms 87464 KiB
01_test_05.txt WA 157 ms 87768 KiB
01_test_06.txt WA 961 ms 128164 KiB
01_test_07.txt WA 1803 ms 156844 KiB
01_test_08.txt WA 522 ms 103692 KiB
01_test_09.txt WA 393 ms 100512 KiB
01_test_10.txt WA 594 ms 106588 KiB
01_test_11.txt WA 1387 ms 151456 KiB
01_test_12.txt WA 617 ms 109720 KiB
01_test_13.txt WA 193 ms 90984 KiB
01_test_14.txt WA 473 ms 100560 KiB
01_test_15.txt WA 356 ms 98896 KiB
01_test_16.txt WA 1196 ms 133504 KiB
01_test_17.txt WA 1286 ms 140288 KiB
01_test_18.txt WA 1745 ms 158120 KiB
01_test_19.txt WA 1687 ms 156024 KiB
01_test_20.txt WA 1589 ms 157032 KiB
01_test_21.txt WA 1784 ms 156900 KiB
01_test_22.txt WA 1717 ms 158328 KiB
01_test_23.txt WA 1716 ms 156476 KiB
01_test_24.txt WA 1458 ms 155228 KiB
01_test_25.txt WA 1323 ms 155932 KiB
01_test_26.txt WA 1337 ms 155804 KiB
01_test_27.txt WA 475 ms 152940 KiB
01_test_28.txt WA 514 ms 155188 KiB
01_test_29.txt WA 497 ms 153100 KiB
01_test_30.txt WA 945 ms 155984 KiB
01_test_31.txt WA 901 ms 155732 KiB
01_test_32.txt WA 923 ms 155044 KiB
01_test_33.txt WA 880 ms 156140 KiB
01_test_34.txt WA 878 ms 156008 KiB
01_test_35.txt WA 842 ms 155280 KiB
01_test_36.txt WA 125 ms 84784 KiB
Facebook Twitter Telegram Share

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

More…