QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107523 | #5592. Family Visits | SDTBU_LY | WA | 2ms | 3432kb | C++14 | 1.8kb | 2023-05-21 19:37:04 | 2023-05-21 19:37:55 |
Judging History
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'