QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#826586 | #8532. Train Scheduling | guosoun | 100 ✓ | 142ms | 248156kb | C++17 | 1.8kb | 2024-12-22 14:23:19 | 2024-12-22 14:23:20 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
void chkmin(T &x, const T &y) {
if (x > y) x = y;
}
using ll = long long;
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n;
ll z, ans = 0;
std::array<std::vector<ll>, 2> a;
std::cin >> n >> z;
for (int i = 0; i < n; i++) {
char c;
ll t;
std::cin >> c >> t;
a[c == 'B'].push_back(t);
ans += t;
}
for (auto &v : a) std::sort(v.begin(), v.end());
n = a[0].size();
int m = a[1].size();
std::array<std::vector<std::vector<ll>>, 2> dp, g;
dp.fill(std::vector(n + 1, std::vector(m + 1, (ll)1e18))), g = dp;
dp[0][n][m] = dp[1][n][m] = 0;
for (int i = n - 1; i >= 0; i--) {
dp[0][i][m] = dp[0][i + 1][m] + a[0][i];
}
for (int i = m - 1; i >= 0; i--) {
dp[1][n][i] = dp[1][n][i + 1] + a[1][i];
}
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
for (int t : {0, 1}) {
chkmin(dp[t][i][j], dp[t][i + !t][j + t]);
std::array p{i, j};
if (a[t][p[t]] + z >= a[t ^ 1][p[t ^ 1]]) {
if (g[t][i + t][j + !t] != 1e18) {
g[t][i][j] = g[t][i + t][j + !t] + a[t][p[t]] + z;
} else {
ll lim = a[t][p[t]] + z, sum = 0;
p[t]++;
for (int c = t ^ 1;; c ^= 1) {
bool ok = 0;
while (p[c] < (int)a[c].size() && a[c][p[c]] < lim)
p[c]++, ok = 1, sum += lim;
chkmin(g[t][i][j], dp[c][p[0]][p[1]] + sum);
if (!ok) break;
lim += z;
}
}
chkmin(dp[t][i][j], g[t][i][j]);
} else {
chkmin(dp[t][i][j], dp[t ^ 1][i + !t][j + t]);
}
dp[t][i][j] += a[t][t ? j : i];
}
}
}
std::cout << std::min(dp[0][0][0], dp[1][0][0]) - ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 3536kb
input:
1 95 B 63
output:
0
result:
ok single line: '0'
Test #2:
score: 4.16667
Accepted
time: 0ms
memory: 3824kb
input:
4 1 B 3 B 2 A 1 A 3
output:
1
result:
ok single line: '1'
Test #3:
score: 4.16667
Accepted
time: 0ms
memory: 3648kb
input:
4 10 A 1 B 2 A 3 A 21
output:
13
result:
ok single line: '13'
Test #4:
score: 4.16667
Accepted
time: 0ms
memory: 3544kb
input:
8 125000000000 B 17108575619 B 57117098303 A 42515717584 B 26473500855 A 108514697534 B 110763448122 B 117731666682 A 29117227954
output:
548047356974
result:
ok single line: '548047356974'
Test #5:
score: 4.16667
Accepted
time: 0ms
memory: 3620kb
input:
15 66666666666 B 18321553618 A 19075277868 B 23311375251 B 40808967822 A 1177192404 A 20959169967 A 55611055322 A 59819730757 A 4974902987 B 1222716560 A 16056478800 A 45716098074 A 50518537625 B 66538461856 B 66630582720
output:
542084726711
result:
ok single line: '542084726711'
Test #6:
score: 4.16667
Accepted
time: 0ms
memory: 3796kb
input:
15 66666666666 B 42940111219 B 60375044015 A 33037106266 B 56197221470 A 19061672260 A 20340458760 B 47889740766 A 29003368297 B 43165632313 B 31046123026 A 32586841316 B 42488614860 A 24994001232 A 43655072267 A 11263635180
output:
448149684862
result:
ok single line: '448149684862'
Test #7:
score: 4.16667
Accepted
time: 0ms
memory: 3924kb
input:
100 10000000000 B 176666666664 B 276666666637 A 526666666561 A 2679130135 B 496666666571 A 566666666552 B 696666666516 B 476666666580 B 876666666457 A 666666666529 B 656666666531 B 676666666524 A 2264099968 A 826666666472 B 376666666601 A 506666666568 B 396666666599 B 2241057559 A 386666666600 B 960...
output:
102978802857
result:
ok single line: '102978802857'
Test #8:
score: 4.16667
Accepted
time: 0ms
memory: 3896kb
input:
100 10000000000 A 246666666641 A 226666666649 B 976666666420 B 856666666457 A 406666666597 A 6737604411 A 346666666617 A 726666666491 B 176666666662 B 7630250095 B 616666666525 A 266666666635 B 316666666625 B 556666666544 B 576666666535 B 916666666438 B 256666666637 A 866666666455 A 766666666480 B 9...
output:
47936217526
result:
ok single line: '47936217526'
Test #9:
score: 4.16667
Accepted
time: 1ms
memory: 3660kb
input:
100 10000000000 B 896666666459 A 246666666646 A 566666666561 B 736666666508 B 536666666567 A 966666666444 B 376666666613 A 3462494580 A 406666666608 B 1909199404 A 506666666580 A 546666666563 A 886666666461 A 926666666455 A 5782193487 A 486666666584 A 6261863608 A 386666666612 B 436666666599 A 46666...
output:
80280002343
result:
ok single line: '80280002343'
Test #10:
score: 4.16667
Accepted
time: 0ms
memory: 3656kb
input:
100 10000000000 A 166666666666 A 406666666586 B 916666666419 B 356666666602 B 816666666449 A 4212009491 A 546666666530 B 736666666470 A 426666666576 B 836666666445 A 326666666612 A 866666666436 B 656666666487 B 996666666396 A 626666666499 A 486666666548 B 9091451701 B 556666666525 B 976666666402 B 6...
output:
94861796954
result:
ok single line: '94861796954'
Test #11:
score: 4.16667
Accepted
time: 2ms
memory: 5752kb
input:
500 2000000000 B 412666666318 A 510666666179 B 713348532 B 476666666236 A 422666666303 A 1607274852 B 184666666642 A 662666665958 A 166666666666 A 846666665664 A 838666665675 B 713588398 A 722666665879 A 558666666114 B 704666665904 A 702666665909 A 174666666659 B 568666666099 B 300666666478 A 145980...
output:
92916853209
result:
ok single line: '92916853209'
Test #12:
score: 4.16667
Accepted
time: 0ms
memory: 5888kb
input:
500 2000000000 A 934666665492 B 564666666056 B 788666665715 A 554666666072 A 838666665646 B 412666666271 A 490666666165 A 970666665440 A 818666665673 A 822666665664 B 484666666174 B 1969946218 B 1472123216 B 228666666559 B 1500232266 B 296666666461 A 902666665546 A 826666665659 A 394666666301 A 3066...
output:
106520016120
result:
ok single line: '106520016120'
Test #13:
score: 4.16667
Accepted
time: 2ms
memory: 5684kb
input:
500 2000000000 A 442666666243 B 776666665724 A 882666665557 B 1750350928 A 298666666462 A 922666665498 B 616666665977 B 319922261 B 300666666457 B 868666665581 A 434666666253 A 850666665609 B 725951487 A 186666666634 A 334666666400 B 804666665680 A 978666665418 A 786666665706 A 690666665867 A 902666...
output:
109798349797
result:
ok single line: '109798349797'
Test #14:
score: 4.16667
Accepted
time: 0ms
memory: 5680kb
input:
500 2000000000 A 186666666632 B 172666666657 A 834666665651 A 926666665517 B 460666666217 A 750666665772 B 1161674235 A 682666665869 A 982666665434 B 1126653769 B 280666666480 B 1455843431 A 454666666226 A 862666665607 B 212666666590 B 272666666494 A 602666665998 B 1322272380 A 394666666321 A 550666...
output:
98302806188
result:
ok single line: '98302806188'
Test #15:
score: 4.16667
Accepted
time: 20ms
memory: 42556kb
input:
2000 500000000 B 79262531 B 275384819 A 490666664677 A 429666665060 B 697166663371 A 675666663507 A 961666661825 B 192166666522 B 142528017 A 817666662677 A 948666661905 A 642666663730 B 787166662836 B 441166664999 B 691166663407 B 168166666654 A 543666664320 A 922666662058 B 481166664739 B 77116666...
output:
118403180255
result:
ok single line: '118403180255'
Test #16:
score: 4.16667
Accepted
time: 19ms
memory: 42444kb
input:
2000 500000000 A 419912922 A 693666663608 B 934166662183 B 803166662970 B 341514304 A 751666663282 A 890666662443 B 94436203 B 810166662937 B 824166662853 A 195666666495 A 621666663995 A 535666664515 A 471666664894 B 394567790 A 169666666647 A 614666664035 B 926166662230 B 113657574 B 949166662082 B...
output:
110143274947
result:
ok single line: '110143274947'
Test #17:
score: 4.16667
Accepted
time: 15ms
memory: 42548kb
input:
2000 500000000 A 953666661991 B 306166665846 B 350166665583 B 328166665714 A 474666664836 A 876666662430 B 738166663231 B 939166662074 A 520666664540 A 361666665513 B 228166666314 A 572666664248 A 731666663277 A 652666663752 A 582666664180 A 124599441 B 997166661746 B 654166663743 B 320166665758 A 4...
output:
110260437733
result:
ok single line: '110260437733'
Test #18:
score: 4.16667
Accepted
time: 23ms
memory: 42456kb
input:
2000 500000000 B 888166662375 A 886666662386 B 455166664999 A 417152040 A 873666662442 B 933166662112 B 230358294 B 636166663903 A 615666664036 B 573166664303 B 416539875 B 891166662356 B 224165899 A 274666666052 A 527666664582 A 746666663215 B 690166663583 A 64794015 B 692166663571 B 287166665979 B...
output:
104954387406
result:
ok single line: '104954387406'
Test #19:
score: 4.16667
Accepted
time: 142ms
memory: 247832kb
input:
5000 200000000 B 826866656733 A 173325862 B 363666663644 A 245066665434 A 776266657436 A 627866659663 A 189886330 A 813866656914 B 90406902 B 934466655162 B 302466664576 A 528666661191 A 342666663953 B 109905426 B 970466654654 A 813066656930 A 278266664945 B 443266662448 A 557066660758 B 21926666582...
output:
120788681412
result:
ok single line: '120788681412'
Test #20:
score: 4.16667
Accepted
time: 141ms
memory: 248088kb
input:
5000 200000000 A 699466658724 B 494866661817 A 919066655412 A 587866660431 A 931066655222 B 995666654285 A 852666656415 B 647266659521 B 809666657062 A 592266660369 B 782466657466 A 241866665547 B 777666657543 A 35772658 A 198666666170 A 488666661920 A 713866658484 B 302066664719 A 160065791 A 91786...
output:
123785707074
result:
ok single line: '123785707074'
Test #21:
score: 4.16667
Accepted
time: 130ms
memory: 248156kb
input:
5000 200000000 B 321666664353 B 209266666044 A 401066663196 A 867466656131 B 487266661889 A 707066658529 A 708035 B 152582349 B 661266659262 A 141581476 A 285866664916 B 281666664978 B 23631365 A 224266665822 A 581866660444 B 492066661816 A 178266666507 B 850066656394 A 462666662245 B 546466660997 B...
output:
121703249249
result:
ok single line: '121703249249'
Test #22:
score: 4.16667
Accepted
time: 132ms
memory: 248036kb
input:
5000 200000000 A 210266666001 A 893466655976 B 280066664954 B 736866658339 A 933066655355 B 678866659186 A 368266663673 B 820066657073 A 262266665214 A 180035408 B 24702218 A 406666663117 A 277866664991 B 173330642 A 313066664448 A 751866658117 B 883266656120 B 311666664467 B 34959515 B 194437123 A ...
output:
122179180601
result:
ok single line: '122179180601'
Test #23:
score: 4.16667
Accepted
time: 131ms
memory: 248068kb
input:
5000 200000000 B 632066659739 A 668666659192 B 976866654568 A 873466656076 A 275066665079 B 812066657011 B 28858966 A 188266666332 B 547666661034 A 283466664932 B 611666660051 B 990066654377 A 181466666427 B 458866662340 B 203666666099 A 783866657433 A 120205648 A 82300803 A 273466665103 B 682066658...
output:
122628842469
result:
ok single line: '122628842469'
Test #24:
score: 4.16667
Accepted
time: 141ms
memory: 247776kb
input:
5000 200000000 A 143756643 A 794666657257 A 527866661254 B 283266664899 A 729466658253 B 708466658556 A 64601713 B 33533125 B 402466663139 A 451866662401 A 756666657833 B 336866664093 A 340266664051 B 772066657587 B 529266661230 B 297666664674 A 935866655102 A 484266661891 B 998866654203 B 884866655...
output:
118906071812
result:
ok single line: '118906071812'