import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
m=[]
if t<=1:
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)]
p=[[[-1 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
for j in range(nn+1):
for k in range(nn*nn//2+1-j):
if d[i][j][k+j]>d[i+1][j][k]+a:
d[i][j][k+j]=d[i+1][j][k]+a
p[i][j][k+j]=k
if d[i+1][j][k]<d[i+1][j+1][k]:
d[i+1][j+1][k]=d[i+1][j][k]
p[i+1][j+1][k]=-1
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(n):
while j>0 and p[i][j][k]<0:
j-=1
if j==0:
break
if p[i][j][k]>=0:
v[i]=j
k=p[i][j][k]
#print(*v)
for i in range(n):
for j in range(nn):
if v[i//sw]>j:
print("0 "*sw,end="")
else:
print("1 "*sw,end="")
print()
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
3156 KB |
K = 17 |
| 2 |
Incorrect |
22 ms |
3276 KB |
K = 589 |
| 3 |
Execution timed out |
2075 ms |
125892 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2074 ms |
127232 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2074 ms |
127040 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2094 ms |
129192 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2079 ms |
127592 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2072 ms |
126508 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2084 ms |
127456 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2084 ms |
127808 KB |
Time limit exceeded |
