Submission #206383

#	Time	Username	Problem	Language	Result	Execution time	Memory
206383		TAISA_	Shortcut (IOI16_shortcut)	C++14	23 / 100	2082 ms	424 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1LL<<60;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	vector<ll> sum(n);
	for(int i=0;i+1<n;i++){
		sum[i+1]=sum[i]+l[i];
	}
	ll mi=INF;
	auto dist=[&](int u,int v){return u<v?sum[v]-sum[u]:sum[u]-sum[v];};
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			ll ma=0;
			for(int k=0;k<n;k++){
				for(int l=k+1;l<n;l++){
					ll s=d[k]+d[l]+dist(k,l);
					s=min(s,dist(i,k)+dist(j,l)+c+d[k]+d[l]);
					ma=max(ma,s);
				}
			}
			mi=min(mi,ma);
		}
	}
    return mi;
}

• 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