CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results
Submission details
Task:Programming contest
Sender:paulschulte
Submission time:2024-10-07 17:17:28 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.01 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33--details
#34--details
#35--details
#36--details
#37--details
#38--details
#39--details
#40--details
#41--details
#42--details
#43--details
#44--details
#45--details
#46--details
#47--details
#48--details
#49--details
#50--details
#51--details
#52--details
#53--details
#54--details
#55--details
#56--details
#57--details
#58--details
#59--details
#60--details
#61--details
#62--details
#63--details
#64--details
#65--details
#66--details
#67--details
#68--details
#69--details
#70--details
#71--details
#72--details
#73--details
#74--details
#75--details
#76--details
#77--details
#78--details
#79--details
#80--details
#81--details
#82--details
#83--details
#84--details
#85--details
#86--details

Code

// ~/.vim/cpp_template.cpp
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

#define REP(i,a,b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

#define LL_INF std::numeric_limits<long long int>::max()
#define INF std::numeric_limits<int>::max()


using namespace std;


template <typename T>
void pV(const std::vector<T>& vec, const std::string& label = "Vector") {
    std::cout << label << ": [ ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << "]" << std::endl;
}


void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {
    if ((*visited)[s]) return;
    (*visited)[s] = true;
    // process node s


    for (auto u: (*adj)[s]) {
        dfs(u, visited, adj);
    }
}
/*
// DEPTH-FRIRST-SEARCH
vector<int> adj[N];                                                          
vector<bool> visited(N, false);
int u, v;
for(int i = 0; i < M;i++){
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
*/

vector<long long> dijkstra(int N, int x, vector<vector<pair<int,int>>> *adj){
    vector<bool> processed(N, false);
    vector<long long> distance(N, LL_INF);
    priority_queue<pair<long long,int>> q;
    //for (int i = 1; i <= n; i++) distance[i] = INF;
    distance[x] = 0;
    q.push({0,x});
    while (!q.empty()) {
        int a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (auto u : (*adj)[a]) {
            int b = u.first, w = u.second;
            if (distance[a]+w < distance[b]) {
                distance[b] = distance[a]+w;
                q.push({-distance[b],b});
            }
        }
    }
    return distance;


}


/*
DIJKSTRA
//vector<vector<pair<int,int>>> adj(N, vector<pair<int, int>>(N));
*/

long long solve(long long t, int m_i, int n, vector<int> *m, vector<int> *p){
    if(m_i >= n) return 0;

    long long take = max(0LL, ((long long)(*p)[m_i] - t)) + solve(t+(*m)[m_i], m_i+1, n, m, p);
    long long noTake = solve(t, m_i+1, n, m, p);
    //cout << m_i << ": " << take << ", " << noTake << endl;
    return max(take, noTake);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // Your code starts here
    int n;
    cin >> n;
    vector<int> m(n, 0);
    vector<int> p(n, 0);
    vector<int> pn(n, 0);

    REP(i, 0, n){
        cin >> m[i];
    }
    REP(i, 0, n){
        cin >> p[i];
        pn[i] = max(0,p[i] - m[i]);
    }

    //pV(pn);

    cout << solve(0, 0, n, &m, &pn) << endl;



    return 0;
}


Test details

Test 1

Verdict: ACCEPTED

input
1
15 
13 

correct output
0

user output
0

Test 2

Verdict: ACCEPTED

input
2
19 20 
13 20 

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
2
1 2 
16 17 

correct output
29

user output
29

Test 4

Verdict: ACCEPTED

input
3
8 12 17 
8 12 13 

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

input
3
8 12 17 
8 12 13 

correct output
0

user output
0

Test 6

Verdict: ACCEPTED

input
3
1 2 3 
10 6 1 

correct output
12

user output
12

Test 7

Verdict: ACCEPTED

input
3
1 2 3 
18 14 8 

correct output
30

user output
30

Test 8

Verdict: ACCEPTED

input
4
4 6 8 11 
17 12 11 20 

correct output
18

user output
18

Test 9

Verdict: ACCEPTED

input
4
9 11 12 19 
20 20 16 18 

correct output
11

user output
11

Test 10

Verdict: ACCEPTED

input
4
1 2 3 4 
9 11 2 5 

correct output
16

user output
16

Test 11

Verdict: ACCEPTED

input
4
1 2 3 4 
4 10 18 15 

correct output
27

user output
27

Test 12

Verdict: ACCEPTED

input
4
11 13 18 20 
1 2 14 15 

correct output
0

user output
0

Test 13

Verdict: ACCEPTED

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

correct output
6

user output
6

Test 14

Verdict: ACCEPTED

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

correct output
28

user output
28

Test 15

Verdict: ACCEPTED

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

correct output
23

user output
23

Test 16

Verdict: ACCEPTED

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

correct output
32

user output
32

Test 17

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 18

Verdict: ACCEPTED

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

correct output
28

user output
28

Test 19

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 20

Verdict: ACCEPTED

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

correct output
29

user output
29

Test 21

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 22

Verdict: ACCEPTED

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

correct output
19

user output
19

Test 23

Verdict: ACCEPTED

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
23

Test 24

Verdict: ACCEPTED

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
43

Test 25

Verdict: ACCEPTED

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
23

Test 26

Verdict: ACCEPTED

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
23

Test 27

Verdict: ACCEPTED

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
0

Test 28

Verdict: ACCEPTED

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
38

Test 29

Verdict: ACCEPTED

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
9

Test 30

Verdict: ACCEPTED

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
33

Test 31

Verdict: ACCEPTED

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
5

Test 32

Verdict: ACCEPTED

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
19

Test 33

Verdict:

input
100
18795 20223 56726 60240 71053 ...

correct output
4890035

user output
(empty)

Test 34

Verdict:

input
100
115 18293 19372 27394 34180 39...

correct output
6552875

user output
(empty)

Test 35

Verdict:

input
100
25933 65302 79664 96553 106970...

correct output
3978147

user output
(empty)

Test 36

Verdict:

input
100
18753 20620 23123 23988 29883 ...

correct output
5937872

user output
(empty)

Test 37

Verdict:

input
100
5161 6232 8989 19030 35767 397...

correct output
176136

user output
(empty)

Test 38

Verdict:

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

correct output
51426569

user output
(empty)

Test 39

Verdict:

input
100
41707 54487 59593 64270 82478 ...

correct output
11320

user output
(empty)

Test 40

Verdict:

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

correct output
49363797

user output
(empty)

Test 41

Verdict:

input
100
11117 11402 21287 28739 32016 ...

correct output
141639

user output
(empty)

Test 42

Verdict:

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

correct output
52217614

user output
(empty)

Test 43

Verdict:

input
200
4697 9359 13575 18795 19993 20...

correct output
9389918

user output
(empty)

Test 44

Verdict:

input
200
115 2871 11672 18293 19372 273...

correct output
9859853

user output
(empty)

Test 45

Verdict:

input
200
5546 13021 25557 25933 27209 4...

correct output
7165521

user output
(empty)

Test 46

Verdict:

input
200
18753 20620 21231 23123 23988 ...

correct output
8314788

user output
(empty)

Test 47

Verdict:

input
200
5161 6232 8989 19030 21624 357...

correct output
90139

user output
(empty)

Test 48

Verdict:

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

correct output
98965271

user output
(empty)

Test 49

Verdict:

input
200
853 24517 36617 41385 41707 47...

correct output
44597

user output
(empty)

Test 50

Verdict:

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

correct output
100382390

user output
(empty)

Test 51

Verdict:

input
200
8311 8875 11117 11402 13410 21...

correct output
67695

user output
(empty)

Test 52

Verdict:

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

correct output
92786819

user output
(empty)

Test 53

Verdict:

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

correct output
19745639

user output
(empty)

Test 54

Verdict:

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

correct output
22107472

user output
(empty)

Test 55

Verdict:

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

correct output
22546809

user output
(empty)

Test 56

Verdict:

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

correct output
18678807

user output
(empty)

Test 57

Verdict:

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

correct output
24195

user output
(empty)

Test 58

Verdict:

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

correct output
386011497

user output
(empty)

Test 59

Verdict:

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

correct output
25175

user output
(empty)

Test 60

Verdict:

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

correct output
386081788

user output
(empty)

Test 61

Verdict:

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

correct output
19304

user output
(empty)

Test 62

Verdict:

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

correct output
378585373

user output
(empty)

Test 63

Verdict:

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

correct output
70300404

user output
(empty)

Test 64

Verdict:

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

correct output
73062361

user output
(empty)

Test 65

Verdict:

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

correct output
66608855

user output
(empty)

Test 66

Verdict:

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

correct output
59816359

user output
(empty)

Test 67

Verdict:

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

correct output
6749

user output
(empty)

Test 68

Verdict:

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

correct output
505666198

user output
(empty)

Test 69

Verdict:

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

correct output
3928

user output
(empty)

Test 70

Verdict:

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

correct output
501551005

user output
(empty)

Test 71

Verdict:

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

correct output
11632

user output
(empty)

Test 72

Verdict:

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

correct output
495441709

user output
(empty)

Test 73

Verdict:

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

correct output
217817507

user output
(empty)

Test 74

Verdict:

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

correct output
211203417

user output
(empty)

Test 75

Verdict:

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

correct output
211728199

user output
(empty)

Test 76

Verdict:

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

correct output
210855476

user output
(empty)

Test 77

Verdict:

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

correct output
1163

user output
(empty)

Test 78

Verdict:

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

correct output
505666198

user output
(empty)

Test 79

Verdict:

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

correct output
3267

user output
(empty)

Test 80

Verdict:

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

correct output
501551005

user output
(empty)

Test 81

Verdict:

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

correct output
4223

user output
(empty)

Test 82

Verdict:

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

correct output
495441709

user output
(empty)

Test 83

Verdict:

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

correct output
941809245

user output
(empty)

Test 84

Verdict:

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

correct output
499016214

user output
(empty)

Test 85

Verdict:

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

correct output
495159245

user output
(empty)

Test 86

Verdict:

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

correct output
220537561

user output
(empty)