Submission #595091

#	Time	Username	Problem	Language	Result	Execution time	Memory
595091		Lucpp	Shortcut (IOI16_shortcut)	C++17	23 / 100	2078 ms	340 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n;
vector<ll> x, d;
ll c;

ll max_dist(int p, int a, int b){
    ll res = 0;
    for(int q = 0; q < n; q++){
        if(p == q) continue;
        int i = min(p, q), j = max(p, q);
        ll no = x[j]-x[i];
        ll use = abs(x[i]-x[a])+c+abs(x[j]-x[b]);
        ll dis = min(no, use)+d[i]+d[j];
        res = max(res, dis);
    }
    return res;
}

ll find_shortcut(int n_, vector<int> len, vector<int> d_, int c_) {
    n = n_;
    for(int i = 0; i < n; i++) d.push_back(d_[i]);
    c = c_;
    x.resize(n);
    x[0] = 0;
    for(int i = 0; i < n-1; i++) x[i+1] = x[i]+len[i];
    ll ans = INF;
    for(int a = 0; a < n; a++){
        for(int b = a+1; b < n; b++){
            ll dia = 0;
            for(int p = 0; p < n; p++){
                dia = max(dia, max_dist(p, a, b));
            }
            ans = min(ans, dia);
        }
    }
    return ans;
}

• 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