Submission #831626

#	Time	Username	Problem	Language	Result	Execution time	Memory
831626		OrazB	Shortcut (IOI16_shortcut)	C++14	23 / 100	2056 ms	312 KiB

shortcut

#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 0;
    ll x = p[r-1];
    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-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 = x+1; k < n; k++){
                    mx = max(mx, min(dis(x, k, d), dis(x,i,d)+c+dis(j,k,d))+d[x]+d[k]);
                }
            }
            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: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3