oj.uz

답안 #632344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632344 2022-08-19T21:23:17 Z karolb2011 Coins (LMIO19_monetos) Python 3
88.7068 / 100
 2000 ms 48288 KB 
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]
        for k in range(nn*nn//2+1-j*(i+1)):
            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)

Subtask #1
88.7067849834 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3028 KB K = 17
2 Correct 1791 ms 39292 KB K = 576
3 Partially correct 1928 ms 47160 KB K = 18672
4 Partially correct 1842 ms 46752 KB K = 21858
5 Partially correct 1882 ms 42692 KB K = 17199
6 Execution timed out 2016 ms 48288 KB Time limit exceeded
7 Partially correct 1822 ms 47216 KB K = 21498
8 Partially correct 1889 ms 43500 KB K = 19635
9 Partially correct 1856 ms 43296 KB K = 20784
10 Partially correct 1866 ms 42880 KB K = 20181