Submission #226202

#	Time	Username	Problem	Language	Result	Execution time	Memory
226202		VEGAnn	Shortcut (IOI16_shortcut)	C++14	31 / 100	2075 ms	2304 KiB

shortcut

# include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef std::vector<int> V;
typedef long long ll;
const int N = 510;
ll dist[N][N],pf[N],lt[N],rt[N],ans=0ll,C,cur,suf[N],pref[N];
int n;

long long find_shortcut (int n, V l, V d, int c) {
    pf[0]=0; C=ll(c);
    for (int i=1;i<n;i++) pf[i]=pf[i-1]+ll(l[i-1]);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            dist[i][j]=ll(d[i])+ll(d[j])+pf[max(i,j)]-pf[min(i,j)];
            if (i==j) dist[i][j]-=ll(d[i]);
            if (j>=i) rt[i]=max(rt[i],dist[i][j]);
            if (j<=i) lt[i]=max(lt[i],dist[i][j]);
            ans=max(ans,dist[i][j]);
        }
    pref[0]=lt[0];
    for (int i=1;i<n;i++) pref[i]=max(pref[i-1],lt[i]);
    suf[n-1]=rt[n-1];
    for (int i=n-2;i>=0;i--) suf[i]=max(suf[i+1],rt[i]);
    for (int Lt=0;Lt<n;Lt++)
        for (int r=Lt+1;r<n;r++){
            cur=max(lt[Lt]-ll(d[Lt]),ll(d[Lt]))+min(C,pf[r]-pf[Lt])+max(rt[r]-ll(d[r]),ll(d[r]));
            cur=max(cur,suf[r]);
            cur=max(cur,pref[Lt]);
            for (int L=Lt;L<=r;L++){
                cur=max(cur,min(lt[L],ll(d[L])+C+(pf[r]-pf[L])+max(lt[Lt]-ll(d[Lt]),ll(d[Lt]))));
                cur=max(cur,min(rt[L],ll(d[L])+C+(pf[L]-pf[Lt])+max(rt[r]-ll(d[r]),ll(d[r]))));
                for (int R=L+1;R<=r;R++){
                    cur=max(cur,min(dist[L][R],ll(d[L])+ll(d[R])+(pf[L]-pf[Lt])+(pf[r]-pf[R])+C));
                }
            }
            ans=min(ans,cur);
        }
    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