oj.uz

Submission #632266

# Submission time Handle Problem Language Result Execution time Memory
632266 2022-08-19T19:27:29 Z karolb2011 Coins (LMIO19_monetos) Python 3
79.8795 / 100
 108 ms 3968 KB 
import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
m=[]
if t<=1:
    sw=1
elif t==2:
    sw=5
else:
    sw=20
nn=n//sw
ssw=sw*sw
mm=[[0 for i in range(nn)]for j in range(nn)]
for i in range(n):
    mx=list(map(int,input().split()))
    for j in range(n):
        mm[i//sw][j//sw]+=mx[j]

d=[[[1000000 for _ in range(nn*nn//2+1)]for _ in range(nn+2)]for _ in range(nn+1)]
p=[[[-1 for _ in range(nn*nn//2+1)]for _ in range(nn+2)]for _ in range(nn+1)]
d[nn][0][0]=0
for i in reversed(range(nn)):
    a=0
    for j in range(nn+1):
        for k in range(nn*nn//2+1-j):
            if d[i][j][k+j]>d[i+1][j][k]+a:
                d[i][j][k+j]=d[i+1][j][k]+a
                p[i][j][k+j]=k
            if d[i+1][j][k]<d[i+1][j+1][k]:
                d[i+1][j+1][k]=d[i+1][j][k]
                p[i+1][j+1][k]=-1
        if j<nn:
            a+=mm[i][j]
v=[0 for _ in range(nn)]

k=nn*nn//2
dm=1000000
for j in range(nn+1):
    if d[0][j][k]<dm:
        dm=d[0][j][k]
        jj=j
j=jj
for i in range(n):
    while j>0 and p[i][j][k]<0:
        j-=1
    if j==0:
        break
    if p[i][j][k]>=0:
        v[i]=j
        k=p[i][j][k]
#print(*v)
for i in range(n):
    for j in range(nn):
        if v[i//sw]>j:
            print("0 "*sw,end="")
        else:
            print("1 "*sw,end="")
    print()

Subtask #1
79.8794728576 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3128 KB K = 17
2 Incorrect 23 ms 3184 KB K = 589
3 Partially correct 91 ms 3968 KB K = 18758
4 Partially correct 100 ms 3940 KB K = 21995
5 Partially correct 96 ms 3852 KB K = 17386
6 Partially correct 88 ms 3928 KB K = 21060
7 Partially correct 94 ms 3928 KB K = 21687
8 Partially correct 93 ms 3916 KB K = 19757
9 Partially correct 108 ms 3948 KB K = 20820
10 Partially correct 99 ms 3936 KB K = 20212