Submission #13609058


Source Code Expand

Copy
import sys
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M, L, X = map(int, readline().split())
    A = list(map(int, readline().split()))
    #燃料aまでを使って0≤j≤M-1に何周した状態で止まることができるか
    limit = M*X
    dp = np.full(M, limit+100,np.int64)
    dp[0] = 0
    limit = M*X
    for a in A:
        point = a%M
        if point==0:
            continue
        prev = dp.copy()
        dp[point:M] = np.minimum(dp[point:M], prev[0:M-point]+a)
        dp[0:point] = np.minimum(dp[0:point], prev[M-point:M]+a)
    roop = dp[L]
    if roop<=limit:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission Info

Submission Time
Task D - Many Go Round
User motchy
Language Python3 (3.4.3)
Score 100
Code Size 809 Byte
Status
Exec Time 379 ms
Memory 14272 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 100 / 100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 151 ms 12224 KB
02.txt 148 ms 12508 KB
03.txt 148 ms 12224 KB
04.txt 148 ms 12220 KB
05.txt 150 ms 12224 KB
06.txt 149 ms 12224 KB
07.txt 150 ms 12224 KB
08.txt 151 ms 12224 KB
09.txt 378 ms 12848 KB
10.txt 379 ms 12848 KB
11.txt 152 ms 12224 KB
12.txt 151 ms 12224 KB
13.txt 149 ms 12224 KB
14.txt 150 ms 12224 KB
15.txt 148 ms 12224 KB
16.txt 149 ms 12224 KB
17.txt 375 ms 12848 KB
18.txt 372 ms 12848 KB
19.txt 373 ms 12336 KB
20.txt 369 ms 12336 KB
21.txt 151 ms 12224 KB
s1.txt 149 ms 12224 KB
s2.txt 149 ms 14272 KB
s3.txt 151 ms 12224 KB