QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#487630#4358. RelayEl_Medonho100 ✓77ms15100kbC++202.2kb2024-07-23 03:42:032024-07-23 03:42:03

Judging History

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

  • [2024-07-23 03:42:03]
  • 评测
  • 测评结果:100
  • 用时:77ms
  • 内存:15100kb
  • [2024-07-23 03:42:03]
  • 提交

answer

// ⢸⣿⣿⣿⣿⠃⠄⢀⣴⡾⠃⠄⠄⠄⠄⠄⠈⠺⠟⠛⠛⠛⠛⠻⢿⣿⣿⣿⣿⣶⣤⡀⠄
// ⢸⣿⣿⣿⡟⢀⣴⣿⡿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣸⣿⣿⣿⣿⣿⣿⣿⣷
// ⢸⣿⣿⠟⣴⣿⡿⡟⡼⢹⣷⢲⡶⣖⣾⣶⢄⠄⠄⠄⠄⠄⢀⣼⣿⢿⣿⣿⣿⣿⣿⣿⣿
// ⢸⣿⢫⣾⣿⡟⣾⡸⢠⡿⢳⡿⠍⣼⣿⢏⣿⣷⢄⡀⠄⢠⣾⢻⣿⣸⣿⣿⣿⣿⣿⣿⣿
// ⡿⣡⣿⣿⡟⡼⡁⠁⣰⠂⡾⠉⢨⣿⠃⣿⡿⠍⣾⣟⢤⣿⢇⣿⢇⣿⣿⢿⣿⣿⣿⣿⣿
// ⣱⣿⣿⡟⡐⣰⣧⡷⣿⣴⣧⣤⣼⣯⢸⡿⠁⣰⠟⢀⣼⠏⣲⠏⢸⣿⡟⣿⣿⣿⣿⣿⣿
// ⣿⣿⡟⠁⠄⠟⣁⠄⢡⣿⣿⣿⣿⣿⣿⣦⣼⢟⢀⡼⠃⡹⠃⡀⢸⡿⢸⣿⣿⣿⣿⣿⡟
// ⣿⣿⠃⠄⢀⣾⠋⠓⢰⣿⣿⣿⣿⣿⣿⠿⣿⣿⣾⣅⢔⣕⡇⡇⡼⢁⣿⣿⣿⣿⣿⣿⢣
// ⣿⡟⠄⠄⣾⣇⠷⣢⣿⣿⣿⣿⣿⣿⣿⣭⣀⡈⠙⢿⣿⣿⡇⡧⢁⣾⣿⣿⣿⣿⣿⢏⣾
// ⣿⡇⠄⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢻⠇⠄⠄⢿⣿⡇⢡⣾⣿⣿⣿⣿⣿⣏⣼⣿
// ⣿⣷⢰⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⢰⣧⣀⡄⢀⠘⡿⣰⣿⣿⣿⣿⣿⣿⠟⣼⣿⣿
// ⢹⣿⢸⣿⣿⠟⠻⢿⣿⣿⣿⣿⣿⣿⣿⣶⣭⣉⣤⣿⢈⣼⣿⣿⣿⣿⣿⣿⠏⣾⣹⣿⣿
// ⢸⠇⡜⣿⡟⠄⠄⠄⠈⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟⣱⣻⣿⣿⣿⣿⣿⠟⠁⢳⠃⣿⣿⣿
// ⠄⣰⡗⠹⣿⣄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⠟⣅⣥⣿⣿⣿⣿⠿⠋⠄⠄⣾⡌⢠⣿⡿⠃
// ⠜⠋⢠⣷⢻⣿⣿⣶⣾⣿⣿⣿⣿⠿⣛⣥⣾⣿⠿⠟⠛⠉⠄⠄

#include "bits/stdc++.h"

using namespace std;

#define endl '\n'

typedef long long ll;

const int mod = 1e9+7;


signed main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n; cin >> n;

    vector<pair<int,int>> arr(n);

    for(int i = 0; i < n; i++) cin >> arr[i].second >> arr[i].first;

    sort(arr.begin(), arr.end());

    vector<int> dp(n, 1e9);

    set<int> st; st.insert(arr[0].second);

    for(int i = 1; i < n; i++){
        dp[i] = min(dp[i-1], arr[i].first + arr[i].second + (*st.begin()));
        st.insert(arr[i].second);
    }

    int ans = 1e9;

    for(int i = 2; i < n; i++) ans = min(ans, dp[i-1] + arr[i].first + arr[i].second);

    cout << ans << endl;
    

    return 0;
}

详细

Subtask #1:

score: 25
Accepted

Test #1:

score: 25
Accepted
time: 0ms
memory: 3844kb

input:

3
1 2
2 3
3 1

output:

11

result:

ok single line: '11'

Test #2:

score: 25
Accepted
time: 0ms
memory: 3576kb

input:

3
1 1
1 1
1 1

output:

5

result:

ok single line: '5'

Test #3:

score: 25
Accepted
time: 0ms
memory: 3572kb

input:

3
100000000 100000000
100000000 99999998
100000000 99999999

output:

499999999

result:

ok single line: '499999999'

Test #4:

score: 25
Accepted
time: 0ms
memory: 3880kb

input:

97
41604679 31846321
46400007 48755155
67574989 37232471
50565372 67761890
64228101 39214456
47779566 31310192
26317319 33674132
28360454 36404326
29357345 57650721
32306278 73013779
82553345 75501381
76804151 79747219
24797049 25528103
45533508 52358371
40500666 81379177
36089046 82440282
53272155 ...

output:

142765603

result:

ok single line: '142765603'

Test #5:

score: 25
Accepted
time: 0ms
memory: 3588kb

input:

100
92659402 40397170
92629010 39707661
92618046 41181667
92655563 39821041
92593162 40012800
92607376 39577210
92604921 39837334
92604825 40675187
92663171 39788892
92639463 40601920
92653627 41425719
92608709 41592478
92653858 40874188
92638063 40576385
92646086 41513200
92653863 39577552
92628134...

output:

356865273

result:

ok single line: '356865273'

Test #6:

score: 25
Accepted
time: 0ms
memory: 3876kb

input:

82
507185 828121
1349494 986913
2107684 1011527
2238221 1016503
2305657 1146599
2308900 1411622
3454557 1436161
4864359 2426147
5121217 2431789
5157902 2477687
5197409 2852196
5911272 3670898
6285337 3871060
7210701 3878619
7458307 4211435
7747733 4512548
9616552 4676945
10767710 5141039
10786388 56...

output:

5962803

result:

ok single line: '5962803'

Test #7:

score: 25
Accepted
time: 0ms
memory: 3588kb

input:

99
226681 100912
481907 100898
747258 100620
1001946 100495
1371666 100489
1411839 97794
1824410 96582
1911554 96451
2339082 95377
2938847 95107
3028805 93857
4031334 93521
4277006 92953
4597564 92358
4993172 91721
5284204 88631
5377183 87288
5510278 87123
5533989 86278
5832284 86016
6143761 82831
6...

output:

1657656

result:

ok single line: '1657656'

Test #8:

score: 25
Accepted
time: 0ms
memory: 3536kb

input:

100
1175155 90425574
1531036 89495955
2397110 88476390
3393221 87409800
3886264 86426207
4008337 86008034
5139305 85016107
5392481 84005604
5660101 83135013
6045739 82801449
7139671 81360774
7622368 80639982
8281738 80040814
8917824 79239771
9751909 77735255
10460634 76549591
10749399 76357625
11227...

output:

183285052

result:

ok single line: '183285052'

Subtask #2:

score: 33
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 33
Accepted
time: 1ms
memory: 3808kb

input:

2825
53977479 41256702
62120310 33927327
64289290 28430408
41979035 38932339
55313162 26670027
45972699 36506339
49774934 39297335
57230453 34014568
62417131 34643430
55765586 27058848
57720925 38119761
68340363 42507788
63818626 42903108
66333476 34545383
47665991 42810931
68141480 42245524
6447051...

output:

174980572

result:

ok single line: '174980572'

Test #10:

score: 33
Accepted
time: 1ms
memory: 4056kb

input:

3000
20761615 5583790
33379176 12664639
18848700 24522741
23376364 31453245
13143862 31247691
32018345 39253652
25462045 7636816
40548037 29746928
23203002 40610765
31083440 38924412
25759203 24728631
18809337 27535539
16340061 40540274
27970404 36352630
33845281 15725177
31548031 8208246
41733167 2...

output:

48713552

result:

ok single line: '48713552'

Test #11:

score: 33
Accepted
time: 1ms
memory: 3608kb

input:

1467
84232666 70728659
84232666 75026547
84232666 81119106
84232666 79359761
84232666 72582313
84232666 82172045
84232666 76793299
84232666 68129196
84232666 73820962
84232666 76874875
84232666 83075010
84232666 79848458
84232666 67049821
84232666 66064954
84232666 65267030
84232666 64455907
8423266...

output:

381332765

result:

ok single line: '381332765'

Test #12:

score: 33
Accepted
time: 1ms
memory: 3760kb

input:

2996
803929 90803572
964226 90693929
864077 90469890
767832 90011942
585369 90151330
226117 89993426
1001823 90344760
1002875 90703698
934041 90173793
562467 90313701
474666 89910827
1102855 90335889
866183 90489451
859210 90589203
492100 89711794
991741 90439453
798615 89547927
427373 89824537
1045...

output:

180530112

result:

ok single line: '180530112'

Test #13:

score: 33
Accepted
time: 1ms
memory: 3764kb

input:

2999
95261 90014809
505968 90104266
528748 90005628
465975 90871580
791826 89893687
954568 90357152
1117183 90703112
1058513 89988162
837653 90442235
368500 90312384
1013399 90185890
607645 90593767
1057373 90551372
462097 90539948
380951 89804642
1034821 89950119
1043398 90186850
1007223 89709938
8...

output:

180379060

result:

ok single line: '180379060'

Test #14:

score: 33
Accepted
time: 1ms
memory: 3988kb

input:

3000
209235 90208507
229332 90156796
234134 90820003
239783 90499259
1053561 89983382
323824 90789366
687731 90756906
272749 90410774
1100365 90603812
751084 90036139
855385 90311178
1066241 90411105
1195748 90327985
1199926 90606200
576365 90159876
1296650 90302152
1089029 90498752
702767 89585037
...

output:

180491480

result:

ok single line: '180491480'

Test #15:

score: 33
Accepted
time: 1ms
memory: 4024kb

input:

3000
79999999 1
79999998 2
79999997 3
79999996 4
79999995 5
79999994 6
79999993 7
79999992 8
79999991 9
79999990 10
79999989 11
79999988 12
79999987 13
79999986 14
79999985 15
79999984 16
79999983 17
79999982 18
79999981 19
79999980 20
79999979 21
79999978 22
79999977 23
79999976 24
79999975 25
7999...

output:

192000006

result:

ok single line: '192000006'

Subtask #3:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 31ms
memory: 5456kb

input:

191299
57369094 6503182
57369094 9057989
57369094 8912175
57369094 6723541
57369094 5910487
57369094 9045112
57369094 7816655
57369094 9262043
57369094 10152587
57369094 5837092
57369094 9571656
57369094 6463836
57369094 7925573
57369094 9294276
57369094 7029182
57369094 9292611
57369094 7372538
573...

output:

183084623

result:

ok single line: '183084623'

Test #17:

score: 10
Accepted
time: 37ms
memory: 5380kb

input:

200000
98307096 85291783
98307096 81779140
98307096 85779516
98307096 84216614
98307096 82424547
98307096 82452036
98307096 82371920
98307096 85499982
98307096 85602931
98307096 85964006
98307096 84667883
98307096 83362216
98307096 84174656
98307096 82055209
98307096 81879760
98307096 82076204
98307...

output:

458160942

result:

ok single line: '458160942'

Test #18:

score: 10
Accepted
time: 24ms
memory: 5572kb

input:

193487
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529036 70225553
50529...

output:

292038214

result:

ok single line: '292038214'

Test #19:

score: 10
Accepted
time: 26ms
memory: 5456kb

input:

200000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
100000000 100...

output:

500000000

result:

ok single line: '500000000'

Subtask #4:

score: 32
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #20:

score: 32
Accepted
time: 64ms
memory: 12900kb

input:

164595
72762774 14647627
45538448 50317377
52413131 42343404
59505690 6476263
79317256 53397603
62517558 59722737
75346706 53973815
80715897 15459410
51777699 44282638
43637154 35801486
78974978 44797415
47467587 75842214
76317057 45026585
52524416 43935367
59289265 28365885
55039611 34977567
553243...

output:

135854225

result:

ok single line: '135854225'

Test #21:

score: 32
Accepted
time: 77ms
memory: 14692kb

input:

200000
22714956 88351591
8349552 79927885
8470872 65878362
2868678 88324648
9237138 89190658
21889201 88109721
5310624 89461083
21590036 70185091
6020551 91171402
15812425 78382825
22371204 95504263
22673217 82631826
14108169 76966802
15940689 79477314
6324889 65896013
4384454 83994982
13303924 8058...

output:

128281748

result:

ok single line: '128281748'

Test #22:

score: 32
Accepted
time: 56ms
memory: 14668kb

input:

200000
190 20
465 33
787 66
1117 75
1212 79
1247 110
1310 139
1368 154
1408 208
1411 213
1423 220
1507 231
1527 253
1590 355
1695 388
1735 416
1768 421
1838 456
2072 460
2138 476
2151 506
2160 518
2293 548
3393 552
3626 598
3704 641
3775 645
3783 659
3954 711
4013 721
4093 725
4294 742
4343 834
4389...

output:

1541

result:

ok single line: '1541'

Test #23:

score: 32
Accepted
time: 41ms
memory: 14688kb

input:

199999
62 1046606
83 1046605
111 1046604
236 1046601
374 1046597
448 1046589
452 1046588
505 1046588
589 1046583
690 1046576
721 1046567
849 1046559
1084 1046557
1214 1046555
1741 1046555
1915 1046542
1974 1046541
1989 1046539
1990 1046534
2029 1046528
2121 1046520
2132 1046513
2183 1046507
2185 104...

output:

2093467

result:

ok single line: '2093467'

Test #24:

score: 32
Accepted
time: 56ms
memory: 14816kb

input:

196196
61768 90529709
818004 90027655
60914 90177986
683915 90626174
765532 90320991
648050 90554485
351315 90737259
784713 90769283
731260 90245148
868175 90566676
808109 90213028
301312 90720931
154280 90298157
389957 90422874
688426 90775033
367450 90416274
583248 90051743
419156 90653995
770570 ...

output:

180074947

result:

ok single line: '180074947'

Test #25:

score: 32
Accepted
time: 63ms
memory: 14764kb

input:

197883
578989 90336551
64348 90612468
735405 90973827
31604 90540203
332454 90202738
777903 90250710
795450 90160363
397318 90956935
322841 90455077
471538 90278474
812607 90336216
198518 90670956
751856 90174060
693967 90136145
16149 90433301
90724 90083952
586287 90249280
570612 90683032
42942 907...

output:

180082773

result:

ok single line: '180082773'

Test #26:

score: 32
Accepted
time: 54ms
memory: 15100kb

input:

200000
852592 90587251
182263 90531182
144064 90372272
808727 90496451
439751 90550998
803724 90407000
151685 90765061
223680 90512523
348612 90253901
92438 90812774
912371 90489331
103681 90086872
255152 90838148
620502 90543491
212462 90108398
968101 90804686
968078 90618881
410642 90805051
383676...

output:

180074610

result:

ok single line: '180074610'

Test #27:

score: 32
Accepted
time: 53ms
memory: 15080kb

input:

200000
79999999 1
79999998 2
79999997 3
79999996 4
79999995 5
79999994 6
79999993 7
79999992 8
79999991 9
79999990 10
79999989 11
79999988 12
79999987 13
79999986 14
79999985 15
79999984 16
79999983 17
79999982 18
79999981 19
79999980 20
79999979 21
79999978 22
79999977 23
79999976 24
79999975 25
79...

output:

192000006

result:

ok single line: '192000006'

Extra Test:

score: 0
Extra Test Passed