제출 #113167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113167		baluteshih	Shortcut (IOI16_shortcut)	C++14	38 / 100	2043 ms	640 KiB

shortcut

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll INF=1e18;
ll find_shortcut(int n,vector<int> l,vector<int> d, int c)
{
	ll mx=-INF,ans=0;
	vector<ll> sl(n,0),ldp(n,0),rdp(n,0),lf(n,0),rf(n,0),nd(n,0);
	for(int i=0;i<n;++i)
		nd[i]=d[i];
	for(int i=1;i<n;++i)
		sl[i]=sl[i-1]+l[i-1];
	for(int i=0;i<n;++i)
		ldp[i]=max((ll)d[i],sl[i]+mx),mx=max(mx,ldp[i]-sl[i]);
	for(int i=1;i<n;++i)
		lf[i]=max(lf[i-1],ldp[i-1]+d[i]+sl[i]-sl[i-1]);
	
	mx=-INF;
	for(int i=n-1;i>=0;--i)
		rdp[i]=max((ll)d[i],mx-sl[i]),mx=max(mx,rdp[i]+sl[i]);
	for(int i=n-2;i>=0;--i)
		rf[i]=max(rf[i+1],rdp[i+1]+d[i]+sl[i+1]-sl[i]);
	
	ans=lf[n-1];
	for(int i=0;i<n;++i)
		for(int j=i+1;j<n;++j)
		{
			if(sl[j]-sl[i]<=c) continue;
			ll tmp=max(lf[i],rf[j]),mx2=-INF,cir=sl[j]-sl[i]+c;
			nd[i]=ldp[i],nd[j]=rdp[j];
			deque<int> dq;
			for(int k=i+1;k<=j;++k)
			{
				while(dq.size()&&nd[dq.back()]-sl[dq.back()]<=nd[k-1]-sl[k-1])
					dq.pop_back();
				dq.pb(k-1);
				while(dq.size()&&(sl[k]-sl[dq[0]])*2>=cir)
					mx2=max(mx2,sl[dq[0]]+nd[dq[0]]),dq.pop_front();
				if(dq.size()) tmp=max(tmp,sl[k]+nd[k]+nd[dq[0]]-sl[dq[0]]);
				tmp=max(tmp,mx2+cir-sl[k]+nd[k]);
			}
			ans=min(tmp,ans),nd[i]=d[i],nd[j]=d[j];
		}
	return ans;
}

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