QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302632#2734. Professional NetworkCamillus11 24ms3608kbC++201.4kb2024-01-11 01:45:002024-01-11 01:45:01

Judging History

你现在查看的是最新测评结果

  • [2024-01-11 01:45:01]
  • 评测
  • 测评结果:11
  • 用时:24ms
  • 内存:3608kb
  • [2024-01-11 01:45:00]
  • 提交

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%