oj.uz

Submission #831619

# Submission time Handle Problem Language Result Execution time Memory
831619 2023-08-20T11:24:21 Z OrazB Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 308 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define ll long long

const int N = 1e5+5;
ll pref[N], suff[N], p[N];

ll dis(int l, int r, vector<int> d){
    if (l > r) swap(l, r);
    if (l == r) return d[l];
    ll x = p[r-1]+d[l]+d[r];
    if (l) x -= p[l-1];
    return x;
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
    // for (int i = 0; i < n; i++){
    //     ll sum = 0;
    //     pref[i] = suff[i] = d[i];
    //     for (int j = i-1; j >= 0; j--){
    //         sum += l[j];
    //         pref[i] = max(pref[i], sum+d[j]); 
    //     }
    //     sum = l[i];
    //     for (int j = i+1; j < n; j++){
    //         suff[i] = max(suff[i], sum+d[j]);
    //         if (j == n-1) break;
    //         sum += l[j];
    //     }
    // }
    for (int i = 0; i < n-1; i++){
        p[i] = l[i];
        if (i) p[i] += p[i-1];
    }
    ll mn = 1e18;
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
           ll mx = 0;
            for (int x = 0; x < n; x++){
                for (int k = i; k <= j; k++){
                    ll minn = dis(x, k, d);
                    // if (x == 0 and k == 5 and i == 3 and j == 4) cout << minn << '\n';
                    // if (x < i and j < k) minn = dis(x,i,d)-d[i]+c+dis(j,k,d)-d[j];
                    if (x < k) minn = min(minn, dis(x, i, d)+c+dis(k, j, d));
                    else minn = min(minn, dis(x, j, d)+c+dis(i, k, d));
                    mx = max(mx, minn);
                }
            }
            for (int x = 0; x < i; x++){
                for (int k = j+1; k < n; k++){
                    mx = max(mx, dis(x,i,d)-d[i]+c+dis(j,k,d)-d[j]);
                }
            }
            mn = min(mn, mx);
            // if (mn == 80) cout << i << " " << j << '\n';
        }
    }
    return mn;
}

// int main()
// {
//     int n, c;
//     assert(2 == scanf("%d%d", &n, &c));
    
//     std::vector<int> l(n - 1);
//     std::vector<int> d(n);
//     for (int i = 0; i < n - 1; i++)
//         assert(1 == scanf("%d", &l[i]));
//     for (int i = 0; i < n; i++)
//         assert(1 == scanf("%d", &d[i]));
        
//     long long t = find_shortcut(n, l, d, c);
    
    
//     printf("%lld\n", t);
    
//     return 0;
// }

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 0 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Correct 1 ms 212 KB n = 2, 62 is a correct answer
6 Correct 0 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 308 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 308 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 212 KB n = 3, 3000000000 is a correct answer
14 Incorrect 0 ms 212 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -