QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302632 | #2734. Professional Network | Camillus | 11 | 24ms | 3608kb | C++20 | 1.4kb | 2024-01-11 01:45:00 | 2024-01-11 01:45:01 |
Judging History
answer
#include "bits/stdc++.h"
using ll = long long;
using namespace std;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
auto cost = [&](int m) -> int {
set<int> all;
for (int i = 0; i < n; i++) {
all.insert(i);
}
auto best = [&](int top) -> int {
int res = -1;
for (int i : all) {
if (top >= a[i]) {
if (res == -1 || (res != -1 && b[res] < b[i])) {
res = i;
}
}
}
return res;
};
int sum = 0;
for (int i = 0; i < n; i++) {
sum += b[i];
}
for (int i = m; i < n; i++) {
int j = best(i);
if (j == -1) {
return INT32_MAX;
} else {
sum -= b[j];
all.erase(j);
}
}
return sum;
};
int l = -1;
int r = n;
while (r - l > 1) {
int m = (l + r) / 2;
if (cost(m) != INT32_MAX) {
r = m;
} else {
l = m;
}
}
cout << cost(r) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
200000 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 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...
output:
result:
Subtask #2:
score: 4
Accepted
Test #11:
score: 4
Accepted
time: 1ms
memory: 3440kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
10 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000
output:
100000
result:
ok single line: '100000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
10 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
10 10 219 9 728 8 425 8 380 7 512 7 617 8 434 9 789 8 74 7 100
output:
2360
result:
ok single line: '2360'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
10 2 7163 7 7183 9 8179 9 6271 7 6425 7 1502 7 1115 5 6916 3 184 8 6840
output:
15313
result:
ok single line: '15313'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
10 7 3593 8 2206 9 290 5 1836 10 5899 8 2166 7 6378 10 3962 8 2120 9 684
output:
15121
result:
ok single line: '15121'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
10 3 3235 10 325 9 806 8 2534 10 3271 10 641 8 192 9 43 8 815 9 2397
output:
6093
result:
ok single line: '6093'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
10 7 387 7 1461 9 1180 0 1809 9 616 9 605 1 300 7 857 0 620 10 1018
output:
2626
result:
ok single line: '2626'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
10 6 54 10 4496 6 1946 4 4677 5 3791 8 4101 6 4720 2 3859 10 4381 6 3219
output:
8931
result:
ok single line: '8931'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
10 7 275 2 2001 8 5315 1 3938 10 530 3 3584 10 4559 7 1934 4 52 9 5043
output:
5364
result:
ok single line: '5364'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3388kb
input:
10 9 1500 0 635 1 1825 4 1934 3 2015 9 332 10 1956 2 1782 9 1283 2 1238
output:
3571
result:
ok single line: '3571'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 4 4561 5 3797 4 6708 5 982 1 2333
output:
9340
result:
ok single line: '9340'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
8 8 1687 2 3319 4 1742 7 2319 4 3378 2 4107 4 316 0 2405
output:
1687
result:
ok single line: '1687'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
3 0 762 0 1464 0 316
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1 1 1686
output:
1686
result:
ok single line: '1686'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
8 2 2361 2 3762 6 2726 8 6136 1 2163 0 5565 2 4962 3 400
output:
6136
result:
ok single line: '6136'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 4 7471 1 4420 0 5824 4 7662
output:
15133
result:
ok single line: '15133'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
2 2 4872 0 6634
output:
4872
result:
ok single line: '4872'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 1 1773
output:
1773
result:
ok single line: '1773'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
1 0 4003
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Subtask #3:
score: 7
Accepted
Dependency #2:
100%
Accepted
Test #33:
score: 7
Accepted
time: 1ms
memory: 3496kb
input:
1000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 1000...
output:
10000000
result:
ok single line: '10000000'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1000 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1...
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 12ms
memory: 3540kb
input:
1000 977 544 801 52 926 385 778 344 867 379 929 211 964 402 849 583 804 567 836 333 873 210 767 177 955 573 378 39 425 541 548 367 921 245 809 279 962 13 865 131 795 316 980 578 875 53 954 154 386 181 787 106 862 434 900 54 811 259 903 454 791 157 943 204 836 245 882 402 934 517 857 554 958 387 975 ...
output:
125174
result:
ok single line: '125174'
Test #36:
score: 0
Accepted
time: 12ms
memory: 3540kb
input:
1000 885 1410 759 939 313 203 748 3708 943 2471 971 851 753 1512 974 175 876 1432 930 644 798 3901 913 493 893 2373 981 1189 511 3183 995 3438 971 3605 841 3075 93 1309 780 575 832 1572 792 2844 979 2240 821 3785 835 2726 447 1856 909 3452 828 1784 852 742 998 3818 986 312 803 633 798 2846 887 513 7...
output:
830265
result:
ok single line: '830265'
Test #37:
score: 0
Accepted
time: 13ms
memory: 3540kb
input:
1000 969 549 919 1616 781 1055 1000 1041 796 547 887 1692 901 128 835 646 581 450 967 487 939 1669 833 1735 326 1061 922 1411 997 1338 870 822 927 15 975 663 993 67 767 510 867 1585 934 1642 760 1606 927 1033 827 709 773 1196 798 723 770 511 870 170 907 575 793 1760 89 432 235 1473 864 1403 839 317 ...
output:
376498
result:
ok single line: '376498'
Test #38:
score: 0
Accepted
time: 12ms
memory: 3500kb
input:
1000 444 1831 865 175 875 3633 810 2571 791 1803 958 2075 877 4115 850 823 802 397 957 1582 906 1035 896 1678 872 594 995 3875 763 3636 853 1562 882 1813 812 700 877 1788 286 1678 793 3863 947 3656 875 2785 856 1020 152 4072 21 3044 354 618 912 444 959 1007 865 625 298 3082 874 3853 967 3164 968 522...
output:
990462
result:
ok single line: '990462'
Test #39:
score: 0
Accepted
time: 13ms
memory: 3540kb
input:
1000 158 894 896 3096 858 2659 890 1138 1000 2081 934 256 502 896 904 2463 962 659 906 2489 985 2190 962 1927 817 1684 882 2631 846 1441 590 2755 915 647 894 568 756 385 908 247 973 1418 308 1888 751 1513 777 2171 783 1628 787 1283 834 46 913 716 895 2086 872 1362 821 58 818 1571 934 2661 813 2355 8...
output:
717727
result:
ok single line: '717727'
Test #40:
score: 0
Accepted
time: 22ms
memory: 3496kb
input:
1000 474 2541 794 3628 709 1105 4 3633 393 1663 856 2848 731 4309 748 130 868 94 956 1606 145 2602 616 2602 935 4231 885 803 204 693 842 2089 106 1696 351 880 63 1471 44 775 722 2518 496 2981 405 4514 151 1453 74 2715 560 1420 861 3415 621 4182 316 1194 197 3045 41 4472 710 1647 11 2717 104 2410 509...
output:
938
result:
ok single line: '938'
Test #41:
score: 0
Accepted
time: 24ms
memory: 3524kb
input:
1000 516 5752 610 2047 410 6176 879 1946 607 6888 303 6598 72 1430 848 2688 587 4215 69 260 10 963 390 2467 484 3046 634 1381 946 938 899 7604 243 1300 941 3567 814 1454 96 6223 189 7122 158 7663 122 4320 107 5846 328 4694 616 267 157 6394 139 95 698 4730 96 2242 117 5180 569 1057 612 2436 232 2725 ...
output:
11051
result:
ok single line: '11051'
Test #42:
score: 0
Accepted
time: 23ms
memory: 3608kb
input:
1000 768 1360 239 2989 87 2251 939 2467 57 1434 719 1576 104 1087 27 3707 624 507 205 823 271 3823 749 865 738 3837 629 889 800 3958 985 2045 903 2223 354 2531 516 1910 2 3783 914 1135 303 955 624 1694 423 1531 603 3436 857 3816 76 2209 933 1662 711 2911 917 2430 838 298 413 4081 479 3229 564 3763 2...
output:
7551
result:
ok single line: '7551'
Test #43:
score: 0
Accepted
time: 14ms
memory: 3476kb
input:
833 520 1291 612 5314 720 6179 439 3508 625 7709 319 8285 312 1859 731 2199 574 6596 143 1776 237 7577 181 3490 243 3678 604 5644 24 4207 204 3927 18 2064 564 4017 433 5825 497 706 276 6698 262 1414 644 6215 798 7984 413 5130 650 5294 596 2592 35 1042 158 5816 47 1527 0 101 627 3327 179 2606 231 106...
output:
4300
result:
ok single line: '4300'
Test #44:
score: 0
Accepted
time: 15ms
memory: 3532kb
input:
813 400 5967 81 3054 591 4558 639 7376 15 4228 325 7164 353 762 170 7644 634 3172 684 3014 391 7363 773 7688 526 209 597 2136 524 8192 318 8197 384 5796 376 3450 655 4583 597 3233 635 2210 86 6840 313 3382 80 4223 84 3844 669 776 258 2528 51 3389 309 1935 200 691 119 1653 126 998 329 5037 292 7639 1...
output:
4102
result:
ok single line: '4102'
Test #45:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
620 79 1074 580 678 118 2089 243 2387 160 466 478 1298 22 733 390 1540 320 867 498 1213 405 811 395 94 466 171 603 1982 495 73 25 1806 205 102 455 980 262 838 61 1748 464 122 400 1390 146 1901 170 2433 378 564 560 2235 119 1238 517 1031 550 1784 88 2005 74 1038 578 2474 580 1844 327 1841 438 406 8 1...
output:
1183
result:
ok single line: '1183'
Test #46:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
276 259 553 41 600 191 15 6 75 109 110 53 619 40 228 118 560 101 607 9 127 151 537 156 308 188 276 270 490 172 450 239 577 270 485 253 127 129 456 166 195 61 353 215 121 263 501 221 493 114 295 205 327 36 485 238 284 270 270 154 432 151 254 97 379 14 89 62 540 245 60 52 573 192 614 0 356 24 412 139 ...
output:
657
result:
ok single line: '657'
Test #47:
score: 0
Accepted
time: 18ms
memory: 3564kb
input:
987 24 2574 503 847 712 2555 435 766 323 1562 963 884 755 1687 289 1305 531 1628 749 2606 566 2411 889 293 61 2037 300 1777 212 1982 866 659 333 326 787 1150 901 1985 516 1496 21 1184 73 1943 179 34 746 2237 566 2044 613 2068 321 1406 745 1174 69 728 626 74 110 1390 875 2290 263 2404 527 2203 943 51...
output:
5429
result:
ok single line: '5429'
Test #48:
score: 0
Accepted
time: 4ms
memory: 3568kb
input:
425 206 8032 409 6573 423 7220 237 7178 55 2817 305 3473 219 7008 93 3388 202 5 423 6947 192 1712 174 3309 86 8161 387 1927 385 8316 322 3406 402 3426 264 6303 421 8010 255 7855 128 430 209 3366 290 3555 169 606 118 7414 315 6004 395 8395 260 7543 179 3397 76 1765 206 5089 38 615 365 2389 216 4519 2...
output:
18503
result:
ok single line: '18503'
Test #49:
score: 0
Accepted
time: 17ms
memory: 3488kb
input:
883 562 1362 667 2803 781 2069 489 484 171 539 832 1782 269 213 346 267 331 2719 823 2380 18 40 550 1808 861 1922 82 284 280 1232 714 1440 744 2289 806 881 399 744 55 2040 856 2042 655 274 707 431 610 2412 51 2587 834 2857 350 1952 197 2421 469 2599 409 2815 657 1432 3 613 719 2334 376 2367 384 1153...
output:
4097
result:
ok single line: '4097'
Test #50:
score: 0
Accepted
time: 3ms
memory: 3456kb
input:
364 100 360 271 1362 281 1054 197 1495 111 519 57 1087 185 1487 15 878 248 13 43 2173 56 595 297 1571 295 973 217 684 297 1658 17 533 60 1752 147 106 260 715 225 1768 176 846 30 78 170 1858 22 463 247 336 234 1180 19 1327 346 866 335 1472 59 2162 66 1351 77 1804 34 293 181 512 217 20 58 861 293 958 ...
output:
549
result:
ok single line: '549'
Test #51:
score: 0
Accepted
time: 6ms
memory: 3468kb
input:
623 457 1286 605 726 143 728 250 2614 383 662 616 2850 585 2778 424 1187 399 945 576 80 506 2212 458 1403 275 1933 145 1876 570 1318 327 1602 99 2941 466 2880 196 767 618 1650 121 2173 205 3054 208 421 220 1482 445 813 187 3158 391 310 292 3238 569 2689 133 1462 562 1925 573 2021 438 2874 451 2317 3...
output:
1237
result:
ok single line: '1237'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%