QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#827515#9552. The ChariotLilyWhiteRE 0ms0kbPython31.4kb2024-12-23 00:41:322024-12-23 00:41:33

Judging History

This is the latest submission verdict.

  • [2024-12-23 00:41:33]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-12-23 00:41:32]
  • Submitted

answer

import sys

def minimal_travel_cost(A, B, C, X, Y, D):
    # Maximum segment length is X + Y
    max_segment = X + Y
    # Precompute cost for each possible segment length
    cost = [0] * (max_segment + 1)
    for k in range(1, max_segment + 1):
        if k <= X:
            cost[k] = A
        elif k <= X + Y:
            cost[k] = A + B * (k - X)
        else:
            cost[k] = A + B * Y + C * (k - X - Y)
    
    # Initialize DP array
    INF = float('inf')
    dp = [INF] * (D + 1)
    dp[0] = 0  # Cost to travel 0 meters is 0
    
    # Fill DP array
    for i in range(1, D + 1):
        # Iterate over all possible segment lengths
        for k in range(1, max_segment + 1):
            if i - k >= 0:
                if dp[i - k] + cost[k] < dp[i]:
                    dp[i] = dp[i - k] + cost[k]
    
    return dp[D]

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    T = int(data[0])
    idx = 1
    results = []
    for _ in range(T):
        A = int(data[idx])
        B = int(data[idx+1])
        C = int(data[idx+2])
        X = int(data[idx+3])
        Y = int(data[idx+4])
        D = int(data[idx+5])
        idx +=6
        cost = minimal_travel_cost(A, B, C, X, Y, D)
        results.append(str(cost))
    print('\n'.join(results))

if __name__ == "__main__":
    main()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

5
160 27 41 3 12 3
160 27 41 3 12 4
160 27 41 3 12 99
1 999 999 1 99 999
999 999 1 1 99 9999999999999999

output:


result: