Submission #137418

#	Time	Username	Problem	Language	Result	Execution time	Memory
137418		Hassoony	Shortcut (IOI16_shortcut)	C++17	23 / 100	2059 ms	476 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const ll inf=(1ll<<61);
const int MX=3009;
ll Pref[MX],d[MX];
ll dis(ll x,ll y){
    if(x==y)return 0;
    if(x>y)swap(x,y);
    ll P=0;
    if(x)P=Pref[x-1];
    return Pref[y-1] - P;
}
ll find_shortcut(int N, vector<int> l, vector<int> D, int c){
    int n=N;
    for(int i=0;i<n;i++)d[i]=D[i];
    Pref[0]=l[0];
    for(int i=1;i<n;i++)Pref[i]=Pref[i-1]+l[i];
    ll ans=inf;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ll sum=0;
            for(int x1=0;x1<n;x1++){
                for(int x2=x1+1;x2<n;x2++){
                    ll d1=dis(x1,x2);
                    ll d2=dis(x1,i) + c + dis(x2,j);
                    ll d3=dis(x1,j) + c + dis(x2,i);
                    d1=min(d1,d2);
                    d1=min(d1,d3);
//                    cout<<x1<<" "<<x2<<" "<<d1<<endl;
                    sum=max(sum,d1 + d[x1] + d[x2]);
                }
            }
            ans=min(ans,sum);
        }
    }
    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