QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556404 | #3966. Live aid | LaVuna47# | AC ✓ | 56ms | 41508kb | C++17 | 2.2kb | 2024-09-10 17:45:04 | 2024-09-10 17:45:05 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define RFOR(i, n) for(int i = n-1; i >= 0; --i)
#define output_vec(vec) { FOR(i_, sz(vec)) cout << vec[i_] << ' '; cout << '\n'; }
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<bool> vb;
typedef short si;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
#define MAX_N 1000000+47
struct Segment
{
int l, r;
ll a;
};
vector<pair<int, ll>> L[MAX_N];
vector<ll> dp(MAX_N, 0);
int solve()
{
int n;
if(!(cin >> n))
return 1;
vector<Segment> segs(n);
FOR(i, n)
{
cin >> segs[i].l >> segs[i].r >> segs[i].a;
segs[i].l += 1, segs[i].r += 1;
}
FOR(i, n)
{
L[segs[i].r].pb({segs[i].l, segs[i].a});
}
ll res = 0;
for(int i = 1; i < MAX_N; ++i)
{
dp[i] = dp[i-1];
for(auto [l, a]: L[i])
{
dp[i] = max(dp[i], a+dp[l]);
}
res = max(res, dp[i]);
}
cout << res << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 34228kb
input:
4 0 2 3 5 10 6 1 7 10 8 10 2
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 34428kb
input:
2 0 1 1 1 2 1
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 12ms
memory: 35932kb
input:
30714 1 46 85 54 98 48 103 114 17 124 159 28 161 199 57 207 232 40 241 278 25 282 296 12 302 319 11 324 344 18 345 380 24 387 411 33 413 440 24 443 465 30 468 512 30 519 546 48 551 565 26 575 580 4 584 596 14 600 616 22 624 666 25 668 699 49 704 732 56 735 765 39 768 782 19 787 837 65 843 851 14 861...
output:
1045282
result:
ok single line: '1045282'
Test #4:
score: 0
Accepted
time: 8ms
memory: 36132kb
input:
30851 4 53 44 54 66 15 72 100 36 103 143 60 151 184 59 193 236 25 239 267 44 271 284 19 289 296 4 306 350 48 358 376 27 379 423 70 429 465 43 475 489 14 493 504 22 514 537 43 537 557 36 557 575 32 581 613 41 613 646 56 655 698 47 704 733 55 742 786 22 791 806 27 806 842 43 843 875 32 876 916 56 923 ...
output:
1051078
result:
ok single line: '1051078'
Test #5:
score: 0
Accepted
time: 8ms
memory: 36164kb
input:
30708 9 48 62 57 99 42 104 133 46 137 167 33 177 205 22 211 256 76 257 294 59 300 330 42 340 346 9 355 367 22 370 385 22 395 444 93 453 474 23 482 491 5 492 523 18 533 539 6 542 553 15 556 589 49 589 633 66 639 680 49 688 695 9 698 742 44 750 788 38 798 806 16 815 849 17 857 893 57 901 942 53 946 95...
output:
1048611
result:
ok single line: '1048611'
Test #6:
score: 0
Accepted
time: 14ms
memory: 34248kb
input:
19 1 46 85 54 98 48 103 114 17 124 159 28 161 199 57 207 232 40 241 278 25 282 296 12 302 319 11 324 344 18 345 380 24 387 411 33 413 440 24 443 465 30 468 512 30 519 546 48 551 565 26 575 580 4 584 596 14
output:
574
result:
ok single line: '574'
Test #7:
score: 0
Accepted
time: 4ms
memory: 34388kb
input:
19 4 53 44 54 66 15 72 100 36 103 143 60 151 184 59 193 236 25 239 267 44 271 284 19 289 296 4 306 350 48 358 376 27 379 423 70 429 465 43 475 489 14 493 504 22 514 537 43 537 557 36 557 575 32 581 613 41
output:
682
result:
ok single line: '682'
Test #8:
score: 0
Accepted
time: 10ms
memory: 34460kb
input:
19 9 48 62 57 99 42 104 133 46 137 167 33 177 205 22 211 256 76 257 294 59 300 330 42 340 346 9 355 367 22 370 385 22 395 444 93 453 474 23 482 491 5 492 523 18 533 539 6 542 553 15 556 589 49 589 633 66
output:
710
result:
ok single line: '710'
Test #9:
score: 0
Accepted
time: 55ms
memory: 41380kb
input:
150000 647760 927345 744364 383619 982334 614243 767447 810881 812856 864418 951657 402344 665713 854376 966501 322576 733148 730984 214901 903058 905792 956621 980534 114598 446156 864265 943852 68517 598461 733174 700576 883082 931483 423192 846156 840552 773371 983104 325950 695991 705337 872947 ...
output:
383818500
result:
ok single line: '383818500'
Test #10:
score: 0
Accepted
time: 49ms
memory: 41452kb
input:
150000 909165 954640 284152 901969 989812 989529 495541 724942 546049 560350 702863 674622 938713 988877 984499 595431 864306 129139 853438 924626 13377 702498 808039 129205 753335 874415 246495 556104 618718 293588 959359 969842 992305 477121 880322 545789 460531 955369 552589 590936 813288 960631 ...
output:
383861980
result:
ok single line: '383861980'
Test #11:
score: 0
Accepted
time: 56ms
memory: 41508kb
input:
150000 658203 766440 288712 47285 88565 785432 843099 935503 223781 208761 650609 216977 529171 905636 668788 442832 814392 981436 454519 916838 408295 741393 783973 872483 78998 772463 218338 455312 983107 834278 3219 799322 215205 258877 443616 916697 506186 539774 561939 679486 951637 939391 9514...
output:
375903614
result:
ok single line: '375903614'
Test #12:
score: 0
Accepted
time: 52ms
memory: 41440kb
input:
150000 369416 935323 178510 293330 298533 799242 114224 771632 577309 100568 981083 555726 803349 995593 363330 914135 949032 563429 893444 949426 269166 13921 187306 26473 756136 949722 625008 869984 898095 667622 356388 536494 394612 879500 963539 988051 928216 985239 455356 85219 107431 973196 53...
output:
380363178
result:
ok single line: '380363178'
Test #13:
score: 0
Accepted
time: 45ms
memory: 41264kb
input:
150000 474988 855842 598131 312161 642266 36079 894971 911965 389760 747954 795557 10372 447904 651593 305935 865390 969877 694785 71473 404270 244658 197925 999063 809675 373571 876045 363590 26718 89611 996563 257014 318601 453246 775175 803650 96244 545794 985962 94940 31823 677776 66502 731960 8...
output:
393013478
result:
ok single line: '393013478'
Test #14:
score: 0
Accepted
time: 6ms
memory: 34368kb
input:
19 647760 927345 744364 383619 982334 614243 767447 810881 812856 864418 951657 402344 665713 854376 966501 322576 733148 730984 214901 903058 905792 956621 980534 114598 446156 864265 943852 68517 598461 733174 700576 883082 931483 423192 846156 840552 773371 983104 325950 695991 705337 872947 3703...
output:
3245834
result:
ok single line: '3245834'
Test #15:
score: 0
Accepted
time: 4ms
memory: 34468kb
input:
19 909165 954640 284152 901969 989812 989529 495541 724942 546049 560350 702863 674622 938713 988877 984499 595431 864306 129139 853438 924626 13377 702498 808039 129205 753335 874415 246495 556104 618718 293588 959359 969842 992305 477121 880322 545789 460531 955369 552589 590936 813288 960631 3847...
output:
3072768
result:
ok single line: '3072768'
Test #16:
score: 0
Accepted
time: 9ms
memory: 34372kb
input:
19 658203 766440 288712 47285 88565 785432 843099 935503 223781 208761 650609 216977 529171 905636 668788 442832 814392 981436 454519 916838 408295 741393 783973 872483 78998 772463 218338 455312 983107 834278 3219 799322 215205 258877 443616 916697 506186 539774 561939 679486 951637 939391 951446 9...
output:
3807226
result:
ok single line: '3807226'
Test #17:
score: 0
Accepted
time: 6ms
memory: 34304kb
input:
19 369416 935323 178510 293330 298533 799242 114224 771632 577309 100568 981083 555726 803349 995593 363330 914135 949032 563429 893444 949426 269166 13921 187306 26473 756136 949722 625008 869984 898095 667622 356388 536494 394612 879500 963539 988051 928216 985239 455356 85219 107431 973196 534523...
output:
4113163
result:
ok single line: '4113163'
Test #18:
score: 0
Accepted
time: 4ms
memory: 34324kb
input:
19 474988 855842 598131 312161 642266 36079 894971 911965 389760 747954 795557 10372 447904 651593 305935 865390 969877 694785 71473 404270 244658 197925 999063 809675 373571 876045 363590 26718 89611 996563 257014 318601 453246 775175 803650 96244 545794 985962 94940 31823 677776 66502 731960 80918...
output:
3369401
result:
ok single line: '3369401'
Test #19:
score: 0
Accepted
time: 14ms
memory: 41372kb
input:
150000 0 10 18 3 11 4 6 20 16 13 21 4 13 25 14 16 27 15 19 27 16 21 30 17 23 37 23 27 42 10 28 36 12 33 41 16 37 43 10 40 50 10 46 59 26 50 55 3 51 64 19 59 68 10 68 74 3 72 77 6 77 85 15 80 85 8 82 95 20 95 101 5 100 112 15 103 114 13 112 122 16 117 127 17 126 136 11 129 136 7 136 142 4 139 154 16 ...
output:
821689
result:
ok single line: '821689'
Test #20:
score: 0
Accepted
time: 28ms
memory: 41480kb
input:
150000 0 10 11 3 10 14 8 21 9 19 29 20 23 37 12 27 41 16 34 41 11 34 43 11 41 55 8 55 69 16 63 69 10 64 78 8 77 92 15 84 89 3 84 89 9 84 97 22 87 101 28 101 107 11 105 119 25 119 126 11 126 133 11 130 139 6 132 138 7 135 142 14 137 143 9 139 154 9 153 166 9 154 160 9 154 160 8 154 161 8 158 168 7 16...
output:
821473
result:
ok single line: '821473'
Test #21:
score: 0
Accepted
time: 33ms
memory: 41308kb
input:
150000 0 12 20 3 17 12 6 17 13 17 31 15 20 34 12 26 36 17 30 40 9 32 39 10 36 51 18 36 43 9 40 52 12 41 55 16 43 49 5 45 56 6 45 54 7 54 67 26 54 65 12 55 61 8 59 65 10 60 69 4 69 84 25 76 88 6 85 96 16 90 98 15 95 104 8 99 114 21 108 114 7 109 117 9 116 127 22 126 135 4 128 143 15 139 147 9 139 147...
output:
820268
result:
ok single line: '820268'
Test #22:
score: 0
Accepted
time: 4ms
memory: 34456kb
input:
19 0 10 18 3 11 4 6 20 16 13 21 4 13 25 14 16 27 15 19 27 16 21 30 17 23 37 23 27 42 10 28 36 12 33 41 16 37 43 10 40 50 10 46 59 26 50 55 3 51 64 19 59 68 10 68 74 3
output:
95
result:
ok single line: '95'
Test #23:
score: 0
Accepted
time: 3ms
memory: 34376kb
input:
19 0 10 11 3 10 14 8 21 9 19 29 20 23 37 12 27 41 16 34 41 11 34 43 11 41 55 8 55 69 16 63 69 10 64 78 8 77 92 15 84 89 3 84 89 9 84 97 22 87 101 28 101 107 11 105 119 25
output:
122
result:
ok single line: '122'
Test #24:
score: 0
Accepted
time: 6ms
memory: 34248kb
input:
19 0 12 20 3 17 12 6 17 13 17 31 15 20 34 12 26 36 17 30 40 9 32 39 10 36 51 18 36 43 9 40 52 12 41 55 16 43 49 5 45 56 6 45 54 7 54 67 26 54 65 12 55 61 8 59 65 10
output:
83
result:
ok single line: '83'