oj.uz

Submission #632523

# Submission time Handle Problem Language Result Execution time Memory
632523 2022-08-20T09:36:15 Z karolb2011 Coins (LMIO19_monetos) Python 3
100 / 100
 1582 ms 75240 KB 
import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
c=1
if t>2:
    c=5
r=n//c
z=r*r//2
mm=[[0 for i in range(r)]for j in range(r)]
for i in range(n):
    mx=list(map(int,input().split()))
    for j in range(n):
        mm[i//c][j//c]+=mx[j]
dm=1000000
d=[[[dm for _ in range(z+1)]for _ in range(r+2)]for _ in range(r+1)]
d[r][0][0]=0
for i in reversed(range(r)):
    a=0
    di=d[i]
    dip=d[i+1]
    mi=max(0,z-(i+1)*r)
    for j in range(r+1):
        dij=di[j]
        dipj=dip[j]
        dipjp=dip[j+1]
        ma=z+1-j*(i+1)
        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<r:
            a+=mm[i][j]
for x in range(r+1):
    if di[x][z]<dm:
        dm=di[x][z]
        j=x
for i in range(r):
    if i>0:
        while j>0 and d[i][j-1][z]==d[i][j][z]:
            j-=1
    z-=j
    w="0 "*c*j+"1 "*c*(r-j)+"\n"
    for _ in range(c):
        sys.stdout.write(w)

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2992 KB K = 17
2 Correct 696 ms 34776 KB K = 576
3 Correct 1454 ms 74000 KB K = 18657
4 Correct 1412 ms 72784 KB K = 21839
5 Correct 1504 ms 71688 KB K = 17169
6 Correct 1351 ms 74328 KB K = 20873
7 Correct 1419 ms 73212 KB K = 21477
8 Correct 1432 ms 75240 KB K = 19614
9 Correct 1536 ms 71932 KB K = 20777
10 Correct 1582 ms 69348 KB K = 20150