QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107524 | #5592. Family Visits | SDTBU_LY | AC ✓ | 3ms | 3464kb | C++14 | 1.7kb | 2023-05-21 19:40:27 | 2023-05-21 19:40:28 |
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<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;
}
Details
Tip: Click on the bar to expand more detailed information
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'