Submission #942186

#	Time	Username	Problem	Language	Result	Execution time	Memory
942186		Nika533	Shortcut (IOI16_shortcut)	C++14	31 / 100	2017 ms	604 KiB

shortcut

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "shortcut.h"
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=3005;
long long m,T,k;
long long ans;
long long pref[N]; 
long long ansPref[N],ansSuf[N];
long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
	for (int i=1; i<n; i++) pref[i]=pref[i-1]+L[i-1];
	for (int j=0; j<n; j++) {
		long long mx=0;
		for (int i=0; i<j; i++) {
			long long len=pref[j]-pref[i];
			len+=D[i]+D[j];
			mx=max(mx,len);
		}
		for (int i=j; i<n; i++) ansPref[i]=max(ansPref[i],mx);
	}
	for (int i=0; i<n; i++) {
		long long mx=0;
		for (int j=i+1; j<n; j++) {
			long long len=pref[j]-pref[i];
			len+=D[i]+D[j];
			mx=max(mx,len);
		}
		for (int j=0; j<=i; j++) ansSuf[j]=max(ansSuf[j],mx);
	}
	/*
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			long long len=pref[j]-pref[i];
			len+=D[i]+D[j];
			diameter=max(diameter,len);
		}
	}
	for (int i=r; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			long long len=pref[j]-pref[i];
			len+=D[i]+D[j];
			diameter=max(diameter,len);
		}
	}
	*/
	ans=1e18;
	for (int l=0; l<n; l++) {
		for (int r=l+1; r<n; r++) {
			long long LEN=0;
			for (int o=l; o<r; o++) LEN+=L[o];
			vector<long long> dd;
			for (auto x:D) dd.pb(x);
			long long sum1=0,sum2=0;
			for (int i=l-1; i>=0; i--) {
				sum1+=L[i];
				dd[l]=max(dd[l],sum1+D[i]);
			}
			for (int i=r+1; i<n; i++) {
				sum2+=L[i-1];
				dd[r]=max(dd[r],sum2+D[i]);
			}
			long long diameter=0;
			for (int i=l; i<=r; i++) {
				for (int j=i+1; j<=r; j++) {
					long long len=pref[j]-pref[i];
					len=min(len,LEN-len+C);
					len+=dd[i]+dd[j];
					diameter=max(diameter,len);
				}
			}
			diameter=max(diameter,max(ansPref[l],ansSuf[r]));
			ans=min(ans,diameter);
			//cout<<l<<" "<<r<<" "<<diameter<<endl<<ansPref[l]<<" "<<ansSuf[r]<<endl;
		}
	}
	return ans;
}

Compilation message (stderr)

shortcut.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~

• 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