oj.uz

Submission #632231

# Submission time Handle Problem Language Result Execution time Memory
632231 2022-08-19T17:33:19 Z karolb2011 Coins (LMIO19_monetos) Python 3
0 / 100
 2000 ms 262144 KB 
import sys
input = sys.stdin.readline
t,n,k1,k2=list(map(int,input().split()))
m=[]
for i in range(n):
    m.append(list(map(int,input().split())))
d=[[[1000000 for _ in range(n*n//2+1)]for _ in range(n+2)]for _ in range(n+1)]
p=[[[-1 for _ in range(n*n//2+1)]for _ in range(n+2)]for _ in range(n+1)]
d[n][0][0]=0
for i in reversed(range(n)):
    a=0
    for j in range(n+1):
        for k in range(n*n//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<n:
            a+=m[i][j]
v=[0 for _ in range(n)]
k=n*n//2
j=n
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]
for i in range(n):
    for j in range(n):
        if v[i]>j:
            print(0,end="")
        else:
            print(1,end="")
    print()

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3148 KB Expected integer, but "0000000000" found
2 Execution timed out 2081 ms 69296 KB Time limit exceeded
3 Runtime error 1382 ms 262144 KB Execution killed with signal 9
4 Runtime error 1385 ms 262144 KB Execution killed with signal 9
5 Runtime error 1383 ms 262144 KB Execution killed with signal 9
6 Runtime error 1380 ms 262144 KB Execution killed with signal 9
7 Runtime error 1368 ms 262144 KB Execution killed with signal 9
8 Runtime error 1362 ms 262144 KB Execution killed with signal 9
9 Runtime error 1372 ms 262144 KB Execution killed with signal 9
10 Runtime error 1361 ms 262144 KB Execution killed with signal 9