QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286581#5592. Family Visitsmfshi03WA 16ms9136kbPython31.4kb2023-12-18 03:52:592023-12-18 03:52:59

Judging History

你现在查看的是最新测评结果

  • [2023-12-18 03:52:59]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:9136kb
  • [2023-12-18 03:52:59]
  • 提交

answer

# This solution is wrong the smallest solution on kattis is around 700 lines idk?
import sys
sys.setrecursionlimit(1000000)

n, d = map(int, input().split())

mess = [0 for i in range(n)]
times = [0 for i in range(n)]
prefix = [0 for i in range(n + 1)]
for i in range(n):
    m, c = map(int, input().split())
    mess[i] = m
    prefix[i+1] = prefix[i] + m
    times[i] = c

cache = dict()

def recur(start, i, target, count):
    #print(start, i, target, count, prefix[i+1] - prefix[start])
    if target <= 0:
        return count 

    if i < start:
        return float("inf")

    if (i, target) in cache:
        return cache[(i, target)]

    val = float("inf")

    if mess[i] == 0:
        val = recur(start, i - 1, target, count)

    removed = min(times[i], prefix[i+1] - prefix[start])
    cache[(i, target)] = min(recur(start, i - 1, target - removed, count + 1), val)
    return cache[(i, target)]
    

cdays = 0
start = 0
np = False
days = []

for i in range(d):
    days.append(int(input()))
    
for day in days:

    if times[day - 1] < mess[day - 1]:
        np = True
        break

    clean_days = recur(start, day - 1, prefix[day] - prefix[start], 0)
    #print(clean_days)
    #print()

    if clean_days == float("inf"):
        np = True
        break

    cdays += clean_days
    start = day

if np:
    print(-1)
else:
    print(cdays)




详细

Test #1:

score: 100
Accepted
time: 13ms
memory: 9024kb

input:

6 2
1 2
2 1
1 4
3 2
3 6
2 3
3
6

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 16ms
memory: 9136kb

input:

10 5
12 10
0 2
7 1
1 8
3 4
3 4
2 3
1 2
10 1
7 5
2
4
5
6
8

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 14ms
memory: 9116kb

input:

10 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
10

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 12ms
memory: 8976kb

input:

3 1
10 10
10 10
10 0
2

output:

2

result:

ok single line: '2'

Test #5:

score: -100
Wrong Answer
time: 16ms
memory: 9020kb

input:

12 1
1 1
1 1
1 1
0 4
1 1
1 1
1 1
0 6
1 1
1 1
1 1
0 4
12

output:

4

result:

wrong answer 1st lines differ - expected: '2', found: '4'