Submission #165443

#	Time	Username	Problem	Language	Result	Execution time	Memory
165443		Segtree	Shortcut (IOI16_shortcut)	C++14	23 / 100	2061 ms	504 KiB

shortcut

#include<iostream>
#include<algorithm>
#include<vector>
#include"shortcut.h"
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 110
ll r[N],d[N],n,cost;
ll solve(ll p,ll q){
    ll ma=-1e17;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
	ll mi=r[j]-r[i];
	chmin(mi,abs(r[p]-r[i])+abs(r[q]-r[j])+cost);
	mi+=d[i]+d[j];
	chmax(ma,mi);
    }
    return ma;
}
ll find_shortcut(int nn,vector<int> l,vector<int> dd,int cc){
    n=nn,cost=cc;
    for(int i=0;i<n;i++)d[i]=dd[i];
    r[0]=0;
    for(int i=0;i<n-1;i++)r[i+1]=r[i]+l[i];
    ll ans=1e17;
    for(int p=0;p<n;p++)for(int q=p+1;q<n;q++){
	chmin(ans,solve(p,q));
    }
    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