Submission #388580

#	Time	Username	Problem	Language	Result	Execution time	Memory
388580		alishahali1382	Shortcut (IOI16_shortcut)	C++14	71 / 100	2077 ms	3276 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const ll INF=10000001000000000ll;
const int MAXN=100010;

int n, m, k;
ll L[MAXN], D[MAXN], X[MAXN], C, ans;
ll prefD[MAXN], suffD[MAXN];
ll X1, Y1, X2, Y2;

void AddRect(ll x, ll y, ll xx, ll yy){
	X1=max(X1, x);
	Y1=max(Y1, y);
	X2=min(X2, xx);
	Y2=min(Y2, yy);
}
bool Check(ll val){
	X1=Y1=-INF;
	X2=Y2=INF;
	for (int i=1; i<=n; i++) for (int j=1; j<i; j++){
		if (D[i]+D[j]+X[i]-X[j]<=val) continue ;
		ll x=X[j], y=X[i], z=val-C-D[i]-D[j];
		// cerr<<x<<" "<<y<<" "<<z<<"\n";
		// debug(D[i]+D[j]+y-x)
		AddRect(x+y-z, x-y-z, x+y+z, x-y+z);
	}
	for (int i=1; i<=n; i++) for (int j=1; j<i; j++){
		ll x=X[j], y=X[i];
		ll xx=x+y, yy=x-y;
		if (X1<=xx && xx<=X2 && Y1<=yy && yy<=Y2){
			// debug2(i, j)
			return 1;
		}
	}
	return 0;
}

ll find_shortcut(int _n, vector<int> l, vector<int> d, int _C){
	n=_n;
	C=_C;
	for (int i=1; i<n; i++) L[i]=l[i-1], X[i+1]=X[i]+L[i];
	for (int i=1; i<=n; i++) D[i]=d[i-1];
	for (int i=1; i<=n; i++) prefD[i]=max(D[i], L[i-1]+prefD[i-1]);
	for (int i=n; i; i--) suffD[i]=max(D[i], suffD[i+1]+L[i]);
	/*
	debug(Check(50))
	return 0;
	*/
	ll dwn=-1, up=INF;
	while (up-dwn>1){
		ll mid=(dwn+up)>>1;
		if (Check(mid)) up=mid;
		else dwn=mid;
	}
	return up;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3