제출 #351981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351981		amunduzbaev	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	364 KiB

shortcut

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

#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
//#define int long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 2e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

ll pref[N], suf[N];
ll ans;
ll dd[N];



ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
	int dis = 0;
	for(int i=0;i<n;i++){
		pref[i] = max(d[i], dis);
		if(i < n-1) dis = pref[i] + l[i];
		if(i) dd[i] = dd[i-1] + l[i-1];
	}
	dis = 0;
	for(int i=n-1;i>=0;i--){
		suf[i] = max(d[i], dis);
		if(i > 0) dis = suf[i] + l[i-1];
	}
	ll diam = 0;
	for(int i=0;i<n;i++) diam = max(diam, pref[i] + suf[i]);
	
	//for(int i=0;i<n;i++) cout<<pref[i]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<suf[i]<<" ";
	//cout<<"\n";
	
	ans = diam;
	//cout<<diam<<"\n";
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			diam = pref[i] + suf[j] + c;
			ll dis = dd[j] - dd[i];
			//cout<<diam<<"\n";
			for(int l=0;l<=i;l++) diam = max(diam, pref[l] + suf[l] - dis + c);
			{
				vector<ll> tp(n, 0), ts(n, 0);
				ll dds = 0;
				for(int k=0;k<j;k++){
					tp[k] = max((ll)d[k], dds);
					dds = tp[k] + l[k];
					
				}dds = 0;
				for(int k = j-1;k>=0;k--){
					ts[k] = max((ll)d[k], dds);
					if(k) dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
				tp.assign(n, 0);
				ts.assign(n, 0);
				dds = 0;
				for(int k=i+1;k<n;k++){
					tp[k] = max((ll)d[k], dds);
					if(k < n-1) dds = tp[k] + l[k];
				}dds = 0;
				for(int k = n-1;k>i;k--){
					ts[k] = max((ll)d[k], dds);
					dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
				tp.assign(n, 0);
				ts.assign(n, 0);
				dds = 0;
				for(int k=i+1;k<j;k++){
					tp[k] = max((ll)d[k], dds);
					dds = tp[k] + l[k];
				}dds = 0;
				for(int k = j-1;k>i;k--){
					ts[k] = max((ll)d[k], dds);
					dds = ts[k] + l[k-1];
				}
				//for(int k=0;k<n;k++) cout<<tp[k]<<" ";
				//cout<<"\n";
				//for(int k=0;k<n;k++) cout<<ts[k]<<" ";
				//cout<<"\n";
				for(int k=0;k<n;k++) diam = max(diam, tp[k] + ts[k]);
				
			}
			for(int l=j;l<n;l++) diam = max(diam, pref[l] + suf[l] - dis + c);
			
			//cout<<dis<<" "<<i<<" "<<j<<" "<<diam<<"\n______\n";
			ans = min(ans, diam);
		}
	}
    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