Submission #632522

#	Time	Username	Problem	Language	Result	Execution time	Memory
632522		karolb2011	Coins (LMIO19_monetos)	Cpython 3	100 / 100	1566 ms	75240 KiB

monetos

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
z=nn*nn//2
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]
dm=1000000
d=[[[dm for _ in range(z+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]
    mi=max(0,z-(i+1)*nn)
    for j in range(nn+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<nn:
            a+=mm[i][j]
for x in range(nn+1):
    if d[0][x][z]<dm:
        dm=d[0][x][z]
        j=x
for i in range(nn):
    if i>0:
        while j>0 and d[i][j-1][z]==d[i][j][z]:
            j-=1
    z-=j
    w="0 "*sw*j+"1 "*sw*(nn-j)+"\n"
    for _ in range(sw):
        sys.stdout.write(w)

• Subtask 1: 100 / 100