Submission #25290

#	Time	Username	Problem	Language	Result	Execution time	Memory
25290		leejseo	리조트 (KOI16_resort)	Cpython 2	100 / 100	68 ms	3 KiB

resort

from sys import maxint
def solve(n, L):
    D = [ [maxint]*(2*i + 1) for i in range(n+1)]
    D[0][0] = 0
    for i in range (n):
        for j in range(2*i +1): 
            if D[i][j] == maxint: continue
            if i+1 in L:
                D[i+1][j] = min(D[i+1][j], D[i][j])
                continue                        
            D[i+1][j] = min(D[i+1][j], D[i][j]+10000)
            for k in range(1, 4):
                if i + k > n: break
                D[i+k][j+1] = min(D[i+k][j+1], D[i][j]+25000)
            for k in range(1, 6):
                if i + k > n: break
                D[i+k][j+2] = min(D[i+k][j+2], D[i][j]+37000)
            if j >= 3:
                D[i+1][j-3] = min(D[i+1][j-3], D[i][j])            
    return min(D[n])

def main():
    n, k = map(int, raw_input().split())
    if k == 0:
        print solve(n, [])
        return
    L = map(int, raw_input().split())
    print solve(n, L)
    return
main()

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 72 / 72