import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
m=[]
if t<=2:
sw=1
else:
sw=6
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):
dij[k+j]=min(dij[k+j],dipj[k]+a)
dipjp[k]=min(dipjp[k],dipj[k])
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(nn):
if i>0:
while j>0 and d[i][j-1][k]==d[i][j][k]:
j-=1
v[i]=j
k-=j
if j==0:
break
#print(*v)
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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3028 KB |
K = 17 |
| 2 |
Correct |
1140 ms |
34716 KB |
K = 576 |
| 3 |
Partially correct |
1173 ms |
37816 KB |
K = 18672 |
| 4 |
Partially correct |
1271 ms |
37240 KB |
K = 21858 |
| 5 |
Partially correct |
1205 ms |
36824 KB |
K = 17199 |
| 6 |
Partially correct |
1190 ms |
37980 KB |
K = 20888 |
| 7 |
Partially correct |
1224 ms |
37548 KB |
K = 21498 |
| 8 |
Partially correct |
1243 ms |
38476 KB |
K = 19635 |
| 9 |
Partially correct |
1228 ms |
36964 KB |
K = 20784 |
| 10 |
Partially correct |
1162 ms |
35664 KB |
K = 20181 |
