(cache)Submission #66337728 - AtCoder Beginner Contest 408

Contest Duration: 2025-05-31(Sat) 21:00 - 2025-05-31(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66337728

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for _ in range(int(input())):
    n=int(input())
    s=input()
    lis=[]
    for i in range(n):
        if s[i]=="1":
            lis.append(i)
    m=len(lis)
    if m==0:
        print(0)
        continue
    best=-(1<<60)
    mm=1<<60
    for j in range(m):
        if best<lis[j]-2*j:best=lis[j]-2*j
        cost=(lis[j]-2*j)-best-1
        if cost+m <mm:
            mm=cost+m
    ans=min(m,mm)
    print(ans)
        
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

for _ in range(int(input())):
    n=int(input())
    s=input()
    lis=[]
    for i in range(n):
        if s[i]=="1":
            lis.append(i)
    m=len(lis)
    if m==0:
        print(0)
        continue
    best=-(1<<60)
    mm=1<<60
    for j in range(m):
        if best<lis[j]-2*j:best=lis[j]-2*j
        cost=(lis[j]-2*j)-best-1
        if cost+m <mm:
            mm=cost+m
    ans=min(m,mm)
    print(ans)

Submission Info

Submission Time	2025-05-31 21:40:14
Task	D - Flip to Gather
User	juten
Language	Python (CPython 3.11.4)
Score	400
Code Size	443 Byte
Status	AC
Exec Time	114 ms
Memory	17048 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 2

× 30

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

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	10 ms	8524 KiB
00_sample_01.txt	AC	10 ms	8500 KiB
01_test_00.txt	AC	114 ms	8532 KiB
01_test_01.txt	AC	106 ms	8480 KiB
01_test_02.txt	AC	101 ms	8464 KiB
01_test_03.txt	AC	103 ms	8496 KiB
01_test_04.txt	AC	101 ms	8480 KiB
01_test_05.txt	AC	100 ms	8508 KiB
01_test_06.txt	AC	103 ms	8476 KiB
01_test_07.txt	AC	101 ms	8580 KiB
01_test_08.txt	AC	101 ms	8460 KiB
01_test_09.txt	AC	88 ms	8500 KiB
01_test_10.txt	AC	64 ms	8600 KiB
01_test_11.txt	AC	63 ms	8540 KiB
01_test_12.txt	AC	62 ms	8528 KiB
01_test_13.txt	AC	52 ms	8960 KiB
01_test_14.txt	AC	51 ms	9020 KiB
01_test_15.txt	AC	52 ms	8912 KiB
01_test_16.txt	AC	55 ms	9192 KiB
01_test_17.txt	AC	45 ms	9260 KiB
01_test_18.txt	AC	50 ms	9420 KiB
01_test_19.txt	AC	54 ms	11808 KiB
01_test_20.txt	AC	51 ms	11964 KiB
01_test_21.txt	AC	51 ms	11936 KiB
01_test_22.txt	AC	54 ms	13236 KiB
01_test_23.txt	AC	24 ms	9352 KiB
01_test_24.txt	AC	80 ms	16188 KiB
01_test_25.txt	AC	83 ms	17048 KiB
01_test_26.txt	AC	22 ms	9272 KiB
01_test_27.txt	AC	48 ms	13248 KiB