제출 #293334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293334		peti1234	Shortcut (IOI16_shortcut)	C++17	31 / 100	2092 ms	2304 KiB

shortcut

#include <bits/stdc++.h>

using namespace std;
const int c=502;
vector<int> pl;
long long ans=0, kom[c], elott[c], utan[c], ert, maxi, maxj, am, tav[c][c];
long long dist(int a, int b) {
    return pl[a]+pl[b]+abs(kom[b]-kom[a]);
}
long long find_shortcut(int n, vector<int> sz, vector<int> s, int d) {
    for (int i=0; i<n-1; i++) kom[i+1]=kom[i]+sz[i];
    for (int i=0; i<n; i++) pl.push_back(s[i]);
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
        tav[i][j]=dist(i, j);
        if (i!=j) ans=max(ans, tav[i][j]);
    }
    for (int i=1; i<n; i++) {
        elott[i]=elott[i-1];
        for (int j=0; j<i-1; j++) elott[i]=max(elott[i], tav[i-1][j]);
    }
    for (int i=n-2; i>=0; i--) {
        utan[i]=utan[i+1];
        for (int j=i+2; j<n; j++) utan[i]=max(utan[i], tav[i+1][j]);
    }
    for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) {
        ert=max(elott[i], utan[j]), maxi=0, maxj=0;
        for (int k=0; k<i; k++) maxi=max(maxi, tav[k][i]-pl[i]);
        for (int k=j+1; k<n; k++) maxj=max(maxj, tav[k][j]-pl[j]);
        ert=max(ert, maxi+maxj+d);
        for (int k=i; k<=j; k++) {
            long long tavi=min(tav[k][i]-pl[i], tav[k][j]-pl[j]+d), tavj=min(tav[k][j]-pl[j], tav[k][i]-pl[i]+d);
            ert=max({ert, tavi+maxi, tavj+maxj});
            for (int l=k+1; l<=j; l++) {
                long long x=min(tav[l][i]-pl[i], tav[l][j]-pl[j]+d);
                ert=max(ert, min(x+tavi, tav[k][l]));
            }
        }
        ans=min(ans, ert);
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3