Submission #836208

#	Time	Username	Problem	Language	Result	Execution time	Memory
836208		oscar1f	Shortcut (IOI16_shortcut)	C++17	31 / 100	2043 ms	384 KiB

shortcut

#include<bits/stdc++.h>
#include "shortcut.h"

using namespace std;
using ll=long long;

const ll MAX_SOM=3000+5,INFINI=(ll)1000*1000*1000*1000*1000*1000;
ll nbSom,prixNouv,rep,diam;
ll cumu[MAX_SOM];
ll distStat[MAX_SOM];

ll calcDist(ll a,ll b) {
    if (a>b) {
        swap(a,b);
    }
    return cumu[b]-cumu[a];
}

ll find_shortcut(int n,vector<int> l,vector<int> d,int c) {
    nbSom=n;
    prixNouv=c;
    for (ll i=1;i<nbSom;i++) {
        cumu[i]=cumu[i-1]+l[i-1];
    }
    for (ll i=0;i<nbSom;i++) {
        distStat[i]=d[i];
    }
    rep=INFINI;
    for (ll i=0;i<nbSom;i++) {
        for (ll j=i+1;j<nbSom;j++) {
            diam=0;
            for (ll a=0;a<nbSom;a++) {
                for (ll b=a+1;b<nbSom;b++) {
                    diam=max(diam,min(calcDist(a,b),calcDist(a,i)+calcDist(b,j)+prixNouv)+distStat[a]+distStat[b]);
                }
            }
            rep=min(rep,diam);
        }
    }
    return rep;
}

• 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