CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results
Submission details
Task:Programming contest
Sender:louaha1
Submission time:2024-10-07 17:46:52 +0300
Language:Python3 (CPython3)
Status:READY
Result:
Test results
testverdicttime
#10.02 sdetails
#20.02 sdetails
#30.02 sdetails
#40.02 sdetails
#50.02 sdetails
#60.02 sdetails
#70.02 sdetails
#80.02 sdetails
#90.02 sdetails
#100.02 sdetails
#110.02 sdetails
#120.02 sdetails
#130.02 sdetails
#140.02 sdetails
#150.02 sdetails
#160.02 sdetails
#170.02 sdetails
#180.02 sdetails
#190.02 sdetails
#200.02 sdetails
#210.02 sdetails
#220.02 sdetails
#230.02 sdetails
#240.02 sdetails
#250.02 sdetails
#260.02 sdetails
#270.02 sdetails
#280.02 sdetails
#290.02 sdetails
#300.02 sdetails
#310.02 sdetails
#320.02 sdetails
#330.02 sdetails
#340.02 sdetails
#350.02 sdetails
#360.02 sdetails
#370.02 sdetails
#380.02 sdetails
#390.02 sdetails
#400.02 sdetails
#410.02 sdetails
#420.02 sdetails
#430.02 sdetails
#440.02 sdetails
#450.02 sdetails
#460.02 sdetails
#470.02 sdetails
#480.02 sdetails
#490.02 sdetails
#500.02 sdetails
#510.02 sdetails
#520.02 sdetails
#530.02 sdetails
#540.02 sdetails
#550.02 sdetails
#560.02 sdetails
#570.02 sdetails
#580.02 sdetails
#590.02 sdetails
#600.02 sdetails
#610.02 sdetails
#620.02 sdetails
#630.03 sdetails
#640.03 sdetails
#650.03 sdetails
#660.03 sdetails
#670.03 sdetails
#680.03 sdetails
#690.03 sdetails
#700.04 sdetails
#710.03 sdetails
#720.03 sdetails
#730.17 sdetails
#740.17 sdetails
#750.17 sdetails
#760.17 sdetails
#770.17 sdetails
#780.17 sdetails
#790.16 sdetails
#800.17 sdetails
#810.16 sdetails
#820.17 sdetails
#830.17 sdetails
#840.16 sdetails
#850.17 sdetails
#860.17 sdetails

Code

import heapq

n = int(input())
m = list(map(int, input().split()))
p = list(map(int, input().split()))

tasks = []
for i in range(n):
    tasks.append((p[i], m[i]))

# Sort the tasks by their times (m_i) as they are given in increasing difficulty
tasks.sort(key=lambda x: x[1])

heap = []
total_time = 0
total_points = 0

for points, time in tasks:
    if total_time < time:
        heapq.heappush(heap, points)
        total_time += 1
        total_points += points
    elif heap and heap[0] < points:
        total_points += points - heapq.heappop(heap)
        heapq.heappush(heap, points)

print(total_points)

Test details

Test 1

Verdict:

input
1
15 
13 

correct output
0

user output
13

Test 2

Verdict:

input
2
19 20 
13 20 

correct output
0

user output
33

Test 3

Verdict:

input
2
1 2 
16 17 

correct output
29

user output
33

Test 4

Verdict:

input
3
8 12 17 
8 12 13 

correct output
0

user output
33

Test 5

Verdict:

input
3
8 12 17 
8 12 13 

correct output
0

user output
33

Test 6

Verdict:

input
3
1 2 3 
10 6 1 

correct output
12

user output
17

Test 7

Verdict:

input
3
1 2 3 
18 14 8 

correct output
30

user output
40

Test 8

Verdict:

input
4
4 6 8 11 
17 12 11 20 

correct output
18

user output
60

Test 9

Verdict:

input
4
9 11 12 19 
20 20 16 18 

correct output
11

user output
74

Test 10

Verdict:

input
4
1 2 3 4 
9 11 2 5 

correct output
16

user output
27

Test 11

Verdict:

input
4
1 2 3 4 
4 10 18 15 

correct output
27

user output
47

Test 12

Verdict:

input
4
11 13 18 20 
1 2 14 15 

correct output
0

user output
32

Test 13

Verdict:

input
5
12 13 15 17 18 
15 19 14 16 17 

correct output
6

user output
81

Test 14

Verdict:

input
5
1 3 15 19 20 
13 20 11 12 11 

correct output
28

user output
67

Test 15

Verdict:

input
5
1 4 9 11 19 
15 14 13 13 11 

correct output
23

user output
66

Test 16

Verdict:

input
5
2 3 6 15 17 
15 16 19 14 19 

correct output
32

user output
83

Test 17

Verdict:

input
5
4 11 18 19 20 
5 12 13 14 15 

correct output
1

user output
59

Test 18

Verdict:

input
5
1 2 3 4 5 
2 18 17 5 8 

correct output
28

user output
50

Test 19

Verdict:

input
5
2 5 7 17 19 
1 3 8 12 20 

correct output
1

user output
44

Test 20

Verdict:

input
5
1 2 3 4 5 
5 16 7 9 20 

correct output
29

user output
57

Test 21

Verdict:

input
5
1 5 8 18 20 
1 5 9 11 17 

correct output
1

user output
43

Test 22

Verdict:

input
5
1 2 3 4 5 
8 11 10 10 1 

correct output
19

user output
40

Test 23

Verdict:

input
10
2 6 8 9 11 12 13 15 17 18 
20 12 14 15 18 18 15 15 16 14 

correct output
23

user output
157

Test 24

Verdict:

input
10
1 2 3 4 5 7 8 15 19 20 
14 13 17 14 20 15 19 14 13 17 

correct output
43

user output
156

Test 25

Verdict:

input
10
1 4 5 7 9 10 11 13 14 19 
11 13 15 12 16 16 19 15 17 11 

correct output
23

user output
145

Test 26

Verdict:

input
10
1 2 3 6 9 11 12 15 17 18 
11 10 12 12 10 11 14 17 10 11 

correct output
23

user output
118

Test 27

Verdict:

input
10
4 5 11 12 13 14 15 18 19 20 
1 3 5 6 9 13 14 16 19 20 

correct output
0

user output
106

Test 28

Verdict:

input
10
1 2 3 4 5 6 7 8 9 10 
2 18 17 5 8 19 20 10 2 13 

correct output
38

user output
114

Test 29

Verdict:

input
10
1 2 3 5 7 8 12 17 19 20 
2 7 9 9 10 11 11 13 13 17 

correct output
9

user output
102

Test 30

Verdict:

input
10
1 2 3 4 5 6 7 8 9 10 
5 16 7 9 20 15 10 20 7 11 

correct output
33

user output
120

Test 31

Verdict:

input
10
1 5 8 9 11 13 16 17 18 20 
3 9 9 10 11 11 12 15 18 19 

correct output
5

user output
117

Test 32

Verdict:

input
10
1 2 3 4 5 6 7 8 9 10 
8 11 10 10 1 3 7 3 1 5 

correct output
19

user output
59

Test 33

Verdict:

input
100
18795 20223 56726 60240 71053 ...

correct output
4890035

user output
73880394

Test 34

Verdict:

input
100
115 18293 19372 27394 34180 39...

correct output
6552875

user output
75806059

Test 35

Verdict:

input
100
25933 65302 79664 96553 106970...

correct output
3978147

user output
77651806

Test 36

Verdict:

input
100
18753 20620 23123 23988 29883 ...

correct output
5937872

user output
75748299

Test 37

Verdict:

input
100
5161 6232 8989 19030 35767 397...

correct output
176136

user output
51837623

Test 38

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
51426569

user output
51592583

Test 39

Verdict:

input
100
41707 54487 59593 64270 82478 ...

correct output
11320

user output
48391684

Test 40

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
49363797

user output
49535497

Test 41

Verdict:

input
100
11117 11402 21287 28739 32016 ...

correct output
141639

user output
50580879

Test 42

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
52217614

user output
52389314

Test 43

Verdict:

input
200
4697 9359 13575 18795 19993 20...

correct output
9389918

user output
151153314

Test 44

Verdict:

input
200
115 2871 11672 18293 19372 273...

correct output
9859853

user output
146832607

Test 45

Verdict:

input
200
5546 13021 25557 25933 27209 4...

correct output
7165521

user output
147917068

Test 46

Verdict:

input
200
18753 20620 21231 23123 23988 ...

correct output
8314788

user output
151052915

Test 47

Verdict:

input
200
5161 6232 8989 19030 21624 357...

correct output
90139

user output
103028955

Test 48

Verdict:

input
200
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
98965271

user output
100282919

Test 49

Verdict:

input
200
853 24517 36617 41385 41707 47...

correct output
44597

user output
95829954

Test 50

Verdict:

input
200
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
100382390

user output
101721213

Test 51

Verdict:

input
200
8311 8875 11117 11402 13410 21...

correct output
67695

user output
101623413

Test 52

Verdict:

input
200
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
92786819

user output
94103313

Test 53

Verdict:

input
1000
56 4050 4697 9243 9359 9691 97...

correct output
19745639

user output
750917212

Test 54

Verdict:

input
1000
115 403 1014 2871 3019 4665 80...

correct output
22107472

user output
744220802

Test 55

Verdict:

input
1000
124 1542 1884 2483 2584 3337 4...

correct output
22546809

user output
743295192

Test 56

Verdict:

input
1000
479 746 2127 4268 6059 6696 98...

correct output
18678807

user output
753077885

Test 57

Verdict:

input
1000
782 1357 2928 3874 3922 5161 6...

correct output
24195

user output
499443050

Test 58

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
386011497

user output
505218483

Test 59

Verdict:

input
1000
520 853 2625 4146 7236 7897 79...

correct output
25175

user output
503493867

Test 60

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
386081788

user output
507174019

Test 61

Verdict:

input
1000
745 929 1179 2177 2424 4167 45...

correct output
19304

user output
499679789

Test 62

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
378585373

user output
495983629

Test 63

Verdict:

input
10000
56 61 73 74 187 368 547 665 69...

correct output
70300404

user output
7489393709

Test 64

Verdict:

input
10000
97 115 142 394 399 403 590 742...

correct output
73062361

user output
7496562445

Test 65

Verdict:

input
10000
124 389 469 554 635 650 724 80...

correct output
66608855

user output
7469492306

Test 66

Verdict:

input
10000
15 270 396 479 513 568 703 746...

correct output
59816359

user output
7493870055

Test 67

Verdict:

input
10000
3 384 389 440 781 782 875 907 ...

correct output
6749

user output
4994327621

Test 68

Verdict:

input
10000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
505666198

user output
5038136162

Test 69

Verdict:

input
10000
35 190 210 272 485 520 577 853...

correct output
3928

user output
4995169502

Test 70

Verdict:

input
10000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
501551005

user output
5015921187

Test 71

Verdict:

input
10000
109 113 409 484 500 516 664 74...

correct output
11632

user output
5000394575

Test 72

Verdict:

input
10000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
495441709

user output
4985362553

Test 73

Verdict:

input
100000
5 21 25 33 47 56 61 73 74 100 ...

correct output
217817507

user output
75039314782

Test 74

Verdict:

input
100000
1 11 39 48 52 57 63 73 79 80 8...

correct output
211203417

user output
74958543081

Test 75

Verdict:

input
100000
21 25 44 52 60 72 86 110 111 1...

correct output
211728199

user output
74950227684

Test 76

Verdict:

input
100000
13 15 24 38 45 47 62 63 66 80 ...

correct output
210855476

user output
75076338149

Test 77

Verdict:

input
100000
3 7 23 26 31 46 54 66 84 102 1...

correct output
1163

user output
49828122514

Test 78

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
505666198

user output
50015311571

Test 79

Verdict:

input
100000
7 18 19 33 35 40 43 52 56 65 7...

correct output
3267

user output
49885760030

Test 80

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
501551005

user output
50064480100

Test 81

Verdict:

input
100000
2 8 13 20 23 29 39 41 71 73 76...

correct output
4223

user output
49962771144

Test 82

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
495441709

user output
49864918264

Test 83

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
941809245

user output
100000000000

Test 84

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
499016214

user output
50007485090

Test 85

Verdict:

input
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
495159245

user output
49962949303

Test 86

Verdict:

input
100000
1 18 33 39 41 64 73 97 98 106 ...

correct output
220537561

user output
74991945507