제출 #71789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71789		KLPP	Shortcut (IOI16_shortcut)	C++14	0 / 100	23 ms	23800 KiB

shortcut

#include "shortcut.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long int lld;
typedef pair<int,long long int> pii;

vector<pii>nei[1000000];
lld max(lld x, lld y){
	if(x<y)return y;
return x;
	
}
lld min(lld x, lld y){
	if(x>y)return y;
return x;
	
}
class ST{
	lld maximo[100000];
	int n;
	public:
	void build(int a, int b, int node){
		maximo[node]=0;
		if(a==b)return;
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
	}
	void init(int N){
		n=N;
		build(0,n-1,1);
	}
	void update(int pos, lld val,int a, int b, int node){
		if(pos<a || pos>b)return;
		if(a==b){
			maximo[node]=val;
			return;
		}
		int mid=(a+b)/2;
		update(pos,val,a,mid,2*node);
		update(pos,val,mid+1,b,2*node+1);
		maximo[node]=max(maximo[2*node],maximo[2*node+1]);
	}
	void set(int pos,lld val){
		update(pos,val,0,n-1,1);
	}
	lld query(){
		return maximo[1];
	}
};
lld positive(lld values[],lld distances[],int n){
	int pnt=0;
	lld dist=0;
	lld sum=0;
	lld DP[n];
	DP[0]=0;
	for(int i=0;i<n-1;i++)DP[i+1]=DP[i]+distances[i];
	for(int i=0;i<n;i++)sum+=distances[i];
	//cout<<sum<<endl;
	ST *s=new ST();
	s->init(n);
	lld ans=0;
	for(int i=0;i<n;i++){
		while(pnt<n && 2*(dist+distances[pnt])<=sum){
			dist+=distances[pnt];
			pnt++;
			if(pnt<n)s->set(pnt,DP[pnt]+values[pnt]);
		}//cout<<i<<" "<<pnt<<" "<<dist<<endl;
		s->set(i,0);
		ans=max(ans,s->query()-DP[i]+values[i]);
		ans=max(ans,values[i]);
		dist-=distances[i];
	}
	return ans;
}
lld negative(lld values[],lld distances[],int n){
	int pnt=0;
	lld dist=0;
	lld sum=0;
	lld DP[n];
	DP[0]=0;
	for(int i=0;i<n-1;i++)DP[i+1]=DP[i]+distances[i];
	for(int i=0;i<n;i++)sum+=distances[i];
	//cout<<sum<<endl;
	//for(int i=0;i<n;i++)cout<<distances[i]<<" "<<values[i]<<endl;
	ST *s=new ST();
	s->init(n);
	for(int i=0;i<n;i++)s->set(i,sum-DP[i]+values[i]);
	lld ans=0;//cout<<endl;
	for(int i=0;i<n;i++){
		while(pnt<n && 2*dist<=sum){s->set(pnt,0);
			dist+=distances[pnt];
			pnt++;
		}//cout<<i<<" "<<pnt<<" "<<dist<<endl;
		//s->set(i,0);
		if(pnt<n)ans=max(ans,s->query()+DP[i]+values[i]);
		ans=max(ans,values[i]);
		dist-=distances[i];
		//cout<<values[i]<<" ";
	}//cout<<endl<<endl;
	return ans;
}
long long find_shortcut(int n,	vector<int> l, vector<int> d, int c)
{
	lld ans=1000000000000000;
	lld left[n];
	left[0]=d[0];
	for(int i=1;i<n;i++){
		left[i]=left[i-1];
		lld dist=0;
		for(int j=i-1;j>-1;j--){
			dist+=l[j];
			left[i]=max(left[i],dist+d[j]+d[i]);
		}
		//cout<<left[i]<<" ";
	}//cout<<endl;
	lld right[n];
	right[n-1]=d[n-1];
	for(int i=n-2;i>-1;i--){
		right[i]=right[i+1];
		lld dist=0;
		for(int j=i;j<n-1;j++){
			dist+=l[j];
			right[i]=max(right[i],dist+d[j+1]+d[i]);
		}
		//cout<<right[i]<<" ";
	}//cout<<endl;
	/*
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			lld values[j-i+1];
			lld distances[j-i+1];
			int size=j-i+1;
			for(int h=0;h<j-i;h++){
				distances[h]=l[i+h];
			}
			distances[j-i]=c;
			for(int h=i+1;h<j;h++){
				values[h-i]=d[h];
			}
			lld dist=0;
			values[0]=d[i];
			for(int h=i-1;h>-1;h--){
				dist+=l[h];
				values[0]=max(values[0],dist+d[h]);
			}
			values[j-i]=d[j];
			
			dist=0;
			for(int h=j;h<n-1;h++){
				dist+=l[h];
				values[j-i]=max(values[j-i],dist+d[h+1]);
			}
			
			lld r=positive(values,distances,size);
			//cout<<i<<" A "<<j<<" "<<r<<endl;
			r=max(r,negative(values,distances,size));
			//cout<<i<<" B "<<j<<" "<<r<<endl;
			//cout<<values[0]<<" "<<values[j-i]<<endl;
			r=max(r,left[i]);
			r=max(r,right[j]);
			//cout<<max(left[i],right[j])<<endl;
			ans=min(ans,r);
		}
	}*/
	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