oj.uz

Submission #632518

# Submission time Handle Problem Language Result Execution time Memory
632518 2022-08-20T09:19:10 Z karolb2011 Coins (LMIO19_monetos) Python 3
100 / 100
 1638 ms 75500 KB 
import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
m=[]
if t<=2:
    sw=1
else:
    sw=5
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)]
d[nn][0][0]=0
for i in reversed(range(nn)):
    a=0
    di=d[i]
    dip=d[i+1]
    for j in range(nn+1):
        dij=di[j]
        dipj=dip[j]
        dipjp=dip[j+1]
        ma=nn*nn//2+1-j*(i+1)
        mi=max(0,nn*nn//2-(i+1)*nn)
        for k in range(mi,ma):
            dk=dipj[k]
            if dij[k+j]>dk+a:
                dij[k+j]=dk+a
            if dipjp[k]>dk:
                dipjp[k]=dk
        if j<nn:
            a+=mm[i][j]
v=[0 for _ in range(nn)]
k=nn*nn//2
dm=1000000
for x in range(nn+1):
    if d[0][x][k]<dm:
        dm=d[0][x][k]
        j=x
for i in range(nn):
    if i>0:
        while j>0 and d[i][j-1][k]==d[i][j][k]:
            j-=1
    v[i]=j
    k-=j
for i in range(n):
    ss=""
    for j in range(nn):
        if v[i//sw]>j:           
            ss+="0 "*sw
        else:
            ss+="1 "*sw
    ss+="\n"
    sys.stdout.write(ss)

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3044 KB K = 17
2 Correct 832 ms 34780 KB K = 576
3 Correct 1638 ms 74080 KB K = 18657
4 Correct 1495 ms 72928 KB K = 21839
5 Correct 1400 ms 72164 KB K = 17169
6 Correct 1575 ms 74420 KB K = 20873
7 Correct 1406 ms 73540 KB K = 21477
8 Correct 1466 ms 75500 KB K = 19614
9 Correct 1434 ms 72000 KB K = 20777
10 Correct 1513 ms 69572 KB K = 20150