QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107524#5592. Family VisitsSDTBU_LYAC ✓3ms3464kbC++141.7kb2023-05-21 19:40:272023-05-21 19:40:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 19:40:28]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3464kb
  • [2023-05-21 19:40:27]
  • 提交

answer

// Problem: D - Family Visits
// Contest: Virtual Judge - sdtbu组队赛3
// URL: https://vjudge.net/contest/558996#problem/D
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2023-05-21 19:23:19

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define MAXN 1010

using namespace std;

typedef long long ll;

int n,d;
int a[MAXN],b[MAXN];

int t[MAXN];

int res=0;


int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> n >> d;
    
    for(int i=1;i<=n;i++)
        cin >> a[i] >> b[i];
    
    for(int i=1;i<=d;i++)
        cin >> t[i];
    
    for(int i=1;i<=d;i++)
    {
        int cur=0,deal=0;
        
        priority_queue<int> q;
        
        for(int j=t[i];j>=t[i-1]+1;j--)
        {
            cur+=a[j];
            if(deal>0)
            {
                int num=min(cur,deal);
                cur-=num;
                deal-=num;
            }
            q.push(b[j]);
            while(cur>0&&q.size()>0)
            {
                
                int val=q.top();
                q.pop();
                int num=min(cur,val);
                cur-=num,val-=num;
                deal+=val;
                res++;
            }
            if(cur>0)
            {
                cout << -1 << endl;
                return 0;
            }
        }
        
        
    }
    
    cout << res << endl;
    
    
    
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3340kb

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: 2ms
memory: 3332kb

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: 2ms
memory: 3412kb

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: 2ms
memory: 3340kb

input:

3 1
10 10
10 10
10 0
2

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3456kb

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:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3332kb

input:

6 1
1 0
1 0
1 2
1 0
1 0
1 2
6

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3356kb

input:

9 1
1 0
1 0
1 9
1 0
1 0
1 2
1 0
1 0
1 3
9

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3384kb

input:

6 1
1 0
1 0
1 2
1 0
1 0
1 4
6

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

6 1
0 0
0 1
0 2
0 0
0 1
0 2
6

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3352kb

input:

999 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

956

result:

ok single line: '956'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3352kb

input:

997 1
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0
60 0
61 ...

output:

567

result:

ok single line: '567'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

758 1
499 0
500 0
501 0
502 0
503 0
504 0
505 0
506 0
507 0
508 0
509 0
510 0
511 0
512 0
513 0
514 0
515 0
516 0
517 0
518 0
519 0
520 0
521 0
522 0
523 0
524 0
525 0
526 0
527 0
528 0
529 0
530 0
531 0
532 0
533 0
534 0
535 0
536 0
537 0
538 0
539 0
540 0
541 0
542 0
543 0
544 0
545 0
546 0
547 0
...

output:

499

result:

ok single line: '499'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3328kb

input:

500 1
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 ...

output:

340

result:

ok single line: '340'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3408kb

input:

1000 1
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2...

output:

340

result:

ok single line: '340'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

997 1
322 0
216 0
418 0
179 0
519 0
391 0
556 0
23 0
400 0
505 0
190 0
577 0
162 0
502 0
223 0
54 0
181 0
560 0
333 0
508 0
409 0
455 0
353 0
255 0
413 0
458 0
463 0
143 0
373 0
158 0
551 0
221 0
399 0
174 0
284 0
147 0
406 0
71 0
401 0
208 0
236 0
184 0
149 0
491 0
39 0
507 0
228 0
72 0
21 0
282 0
...

output:

567

result:

ok single line: '567'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

1000 1
6 0
3 0
7 0
1 0
2 0
8 0
5 0
9 0
7 0
8 0
10 0
6 0
9 0
5 0
7 0
3 0
7 0
4 0
1 0
7 0
5 0
7 0
5 0
7 0
10 0
3 0
1 0
6 0
10 0
4 0
8 0
7 0
10 0
5 0
2 0
10 0
10 0
2 0
2 0
10 0
1 0
4 0
9 0
8 0
3 0
9 0
3 0
6 0
9 0
8 0
6 0
9 0
1 0
4 0
9 0
9 0
7 0
6 0
7 0
8 0
9 0
9 0
4 0
2 0
7 0
10 0
3 0
4 0
3 0
1 0
5 0
5...

output:

340

result:

ok single line: '340'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3328kb

input:

1000 1000
207 363
789 986
722 813
73 821
461 790
403 761
489 746
42 285
415 536
565 669
983 994
561 978
610 961
371 851
857 997
365 559
935 988
258 731
296 827
850 854
437 646
184 206
599 802
725 976
207 495
568 664
118 669
376 493
377 429
232 284
810 995
255 404
43 709
562 894
239 477
970 982
184 8...

output:

997

result:

ok single line: '997'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

1000 500
309 243
53 202
232 7
411 924
307 250
433 815
496 487
311 470
52 229
325 943
3 32
244 319
226 56
273 895
318 344
415 558
377 82
477 811
476 92
379 910
109 356
496 702
260 488
46 179
283 331
472 523
322 465
80 182
497 157
164 681
279 206
422 748
292 16
139 426
422 498
178 453
34 373
94 463
37...

output:

692

result:

ok single line: '692'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3340kb

input:

1000 50
22 82
70 148
40 141
89 147
24 137
80 131
75 150
25 84
42 75
99 142
94 75
80 145
96 132
49 146
9 75
25 149
5 145
23 99
85 103
62 114
31 138
33 91
81 82
6 107
35 111
44 128
40 106
10 133
42 91
60 100
38 108
80 97
58 90
24 119
25 111
4 121
56 144
22 109
26 97
18 116
57 89
3 129
88 89
23 131
65 ...

output:

388

result:

ok single line: '388'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

1000 10
95 111
65 112
1 106
18 98
35 101
94 96
40 85
68 84
62 133
49 93
1 113
61 134
100 145
16 128
85 91
37 100
23 90
75 131
31 89
49 84
11 148
64 82
68 83
59 129
93 115
42 80
43 146
65 76
23 81
61 127
25 149
100 135
19 85
14 125
38 79
77 114
4 97
62 122
33 148
97 147
7 88
96 90
69 148
39 146
65 87...

output:

366

result:

ok single line: '366'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

1000 1
14 122
5 121
18 107
100 97
29 91
52 134
84 139
81 97
3 128
61 104
0 95
58 94
86 122
17 115
79 134
97 76
96 85
92 137
76 94
34 145
88 79
43 88
80 121
62 84
83 134
39 85
93 146
78 77
89 128
86 142
82 95
70 111
46 75
23 146
25 91
23 138
31 129
11 149
34 145
75 144
36 77
63 82
60 123
89 133
15 13...

output:

376

result:

ok single line: '376'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3340kb

input:

1000 1
935 988
935 977
952 954
941 914
951 997
938 924
934 975
948 944
941 922
936 990
940 926
940 940
937 985
959 972
948 943
950 937
935 953
933 973
947 932
930 911
935 1000
931 932
959 972
950 975
940 967
954 970
946 965
937 982
942 913
950 978
949 950
950 979
945 912
933 990
953 942
947 910
940 ...

output:

991

result:

ok single line: '991'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

1000 1
932 925
931 917
952 943
943 954
956 915
954 911
948 992
938 961
933 939
960 920
932 979
938 960
947 937
941 977
935 1000
949 927
941 925
933 943
949 937
949 974
949 917
945 924
941 917
947 995
942 968
936 988
931 952
955 968
953 977
936 953
947 951
937 943
948 976
950 942
931 996
937 991
955 ...

output:

990

result:

ok single line: '990'

Test #24:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

1000 1
940 951
934 966
955 939
950 926
951 988
956 981
942 941
937 985
940 946
960 966
938 995
954 959
958 956
948 998
939 985
949 963
960 983
941 976
933 996
939 982
934 919
960 992
944 952
941 925
937 925
954 971
935 915
953 981
954 914
952 928
930 944
931 943
950 962
955 980
943 919
940 960
939 9...

output:

988

result:

ok single line: '988'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

1 1
3 2
1

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

1 1
2 3
1

output:

1

result:

ok single line: '1'