oj.uz

Submission #1020620

# Submission time Handle Problem Language Result Execution time Memory
1020620 2024-07-12T07:46:17 Z vjudge1 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 596 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define pb push_back


ll b[200100];

long long find_shortcut(int n, std::vector<int> dl, std::vector<int> d, int c)
{
    ll ans = 1e18;
    for(int l=0; l<n; l++){
        for(int r=l+1; r<n; r++){
            ll sum = 0;
            b[l] = 0;
            for(int i=l; i>=0; i--){
                b[l] = max(b[l], sum + d[i]);
                if(i > 0) sum += dl[i-1];
            }
            b[r] = 0;
            sum = 0;
            for(int i=r; i<n; i++){
                b[r] = max(b[r], sum + d[i]);
                if(i < n - 1) sum += dl[i];
            }
            for(int i=l + 1; i<=r-1; i++){
                b[i] = d[i];
            }
            sum = c;
            for(int i=l; i<r; i++){
                sum += dl[i];
            }
            //cout<<l<<' '<<r<<' '<<sum<<'\n';
            //for(int i=l; i<=r; i++){
            //    cout<<b[i]<<' ';
            //}
            //cout<<"\n___________________\n";
            ll res = 0;
            for(int i=l; i<=r; i++){
                ll dsum = 0;
                for(int j=i-1; j>=0; j--){
                    dsum += dl[j];
                    res = max(res, min(dsum, sum - dsum) + b[i] + b[j]);
                }
            }
            for(int i=0; i<=l; i++){
                ll dsum = 0;
                for(int j=i-1; j>=0; j--){
                    dsum += dl[j];
                    res = max(res, dsum + d[i] + d[j]);
                }
            }
            for(int i=r; i<n; i++){
                ll dsum = 0;
                for(int j=i-1; j>=r; j--){
                    dsum += dl[j];
                    res = max(res, dsum + d[i] + d[j]);
                }
            }
            ans = min(ans, res);
        }
    }
    return ans;

            
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 1 ms 344 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 1 ms 440 KB n = 2, 3 is a correct answer
7 Correct 0 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 448 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 344 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 344 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 348 KB n = 10, 7000000000 is a correct answer
20 Correct 0 ms 348 KB n = 5, 12 is a correct answer
21 Correct 0 ms 348 KB n = 5, 25 is a correct answer
22 Correct 1 ms 596 KB n = 2, 122 is a correct answer
23 Correct 0 ms 344 KB n = 10, 117 is a correct answer
24 Incorrect 0 ms 348 KB n = 10, incorrect answer: jury 336 vs contestant 360
25 Halted 0 ms 0 KB -