Submission #15296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15296	2015-07-12T05:29:21 Z	tonyjjw	달리는 게임 (kriii3_E)	C++14	0 / 70	0 ms	28552 KB

E

#include<stdio.h>
#include<algorithm>
#include<vector>
#pragma warning(disable:4996)
#define MN 1000000
#define INF 1e12
#define mp make_pair
#define cs (convex.size())

typedef long long ll;
using namespace std;

int N;
int inp[MN];
ll A[MN+1];
ll S[MN+1];
ll D[MN+1];

typedef pair<double,double> pf;

vector<pf> convex;

double bsearch(double x){
	int l=0,m,r=cs-2;
	int p;
	while(l<=r){
		m=(l+r)>>1;
		double x0=convex[m+1].first,x1=convex[m].first;
		double y0=convex[m+1].second,y1=convex[m].second;
		if(x0<=x && x<=x1){
			return ((x1-x)*y0+(x-x0)*y1)/(x1-x0);
		}
		if(x<x0){
			l=m+1;
		}
		else{
			r=m-1;
		}
	}
}

int main(){
//	freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",&inp[i]);
	for(int i=N-1;i>=0;i--)A[i]=(i==N-1)?inp[N-1]:(A[i+1]+inp[i]);
	for(int i=N-1;i>=0;i--)S[i]=(i==N-1)?A[N-1]:(S[i+1]+A[i]);
	convex.push_back(mp(INF,S[0]));
	convex.push_back(mp(-INF,S[0]));
	D[0]=max(inp[0],0);
	for(int i=1;i<N;i++){
//		D[i-1]+S[i]-x*i
		double x0=convex[cs-1].first,y0=convex[cs-1].second;
		convex.pop_back();
		while(true){
			double x1=convex[cs-1].first;
			double y1=convex[cs-1].second;
			double x=((x1-x0)*(S[i]+D[i-1]-y0)+x0*(y1-y0))/((y1-y0)+i*(x1-x0));
			if(x<x1){
				convex.push_back(mp(x,((x1-x)*y0+(x-x0)*y1)/(x1-x0)));
				convex.push_back(mp(-INF,S[i]+D[i-1]+INF*i));
				break;
			}
			else{
				x0=x1,y0=y1;
				convex.pop_back();
			}
		}

		double v=bsearch(A[i+1])-S[i+1]-(i+1)*A[i+1];
		D[i]=max((ll)(v+1e-7),D[i-1]);
	}
	printf("%lld\n",D[N-1]);
	return 0;
}

Subtask #1

0.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	28552 KB	Output is correct
2	Incorrect	0 ms	28552 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-