QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107523#5592. Family VisitsSDTBU_LYWA 2ms3432kbC++141.8kb2023-05-21 19:37:042023-05-21 19:37:55

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:37:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3432kb
  • [2023-05-21 19:37:04]
  • 提交

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<set>

#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;
        
        multiset<int> s;
        
        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;
            }
            s.insert(b[j]);
            while(cur>0&&s.size()>0)
            {
                multiset<int>::reverse_iterator maxit=s.rbegin();
                int val=*maxit;
                s.erase(*maxit);
                maxit=s.rbegin();
                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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3404kb

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: 3336kb

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

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: 3400kb

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: 3352kb

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

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: 0ms
memory: 3432kb

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: 1ms
memory: 3344kb

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: 3340kb

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

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

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: -100
Wrong Answer
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:

398

result:

wrong answer 1st lines differ - expected: '340', found: '398'