Submission #632521

#TimeUsernameProblemLanguageResultExecution timeMemory
632521karolb2011Coins (LMIO19_monetos)Cpython 3
100 / 100
1566 ms75400 KiB
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] mi=max(0,nn*nn//2-(i+1)*nn) for j in range(nn+1): dij=di[j] dipj=dip[j] dipjp=dip[j+1] ma=nn*nn//2+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] 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 k-=j ss="0 "*sw*j+"1 "*sw*(nn-j)+"\n" for _ in range(sw): sys.stdout.write(ss)
#Verdict Execution timeMemoryGrader output
Fetching results...