Submission #1038123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038123		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	348 KiB

shortcut

#include "shortcut.h"

#include<bits/stdc++.h>
using namespace std;

using lint=int64_t;

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    lint ll[n][n],rr[n][n],cost[n][n];
    for(int i=0;i<n;i++){
        ll[i][i]=rr[i][i]=cost[i][i]=d[i];
    }
    for(int L=n-2;0<=L;L--){
        for(int R=L+1;R<n;R++){
            ll[L][R]=max<lint>(ll[L][R-1]+l[R-1],d[R]);
            rr[L][R]=max<lint>(rr[L+1][R]+l[L],d[L]);
            cost[L][R]=max<lint>(cost[L][R-1],ll[L][R-1]+l[R-1]+d[R]);
        }
    }
    lint ans=cost[0][n-1];
    for(int L=0;L<n-1;L++){
        ans=min(ans,max({cost[0][L],cost[L+1][n-1],ll[0][L]+rr[L+1][n-1]+min<lint>(c,l[L])}));
        for(int R=L+2;R<n;R++){
            lint all=max({cost[0][L],cost[L+1][R-1],cost[R][n-1]});
            all=max(all,ll[0][L]+rr[R][n-1]+c);
            all=max(all,rr[R][n-1]+min(l[R-1]+ll[L+1][R-1],c+l[L]+rr[L+1][R-1]));
            all=max(all,ll[0][L]+min(l[L]+rr[L+1][R-1],c+l[R-1]+ll[L+1][R-1]));
            ans=min(ans,all);
        }
    }
    return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 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