Submission #15330

#	Time	Username	Problem	Language	Result	Execution time	Memory
15330		tonyjjw	달리는 게임 (kriii3_E)	C++14	0 / 70	0 ms	32460 KiB

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;
}

//*/
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

const int N = 1000005;
const double INF = 1.e15;

struct lineinfo {
	long long slope,yadd;
	double x_left,x_right;
	lineinfo() {}
	lineinfo(long long slope,long long yadd,double x_left,double x_right):
		slope(slope),yadd(yadd),x_left(x_left),x_right(x_right) {}
};

int n;
long long inp[N],A[N],S[N],D[N];
vector<lineinfo> convex;

long long bsearch(long long x) {
	int lo = 0,hi = (int)convex.size()-1,mid = -1;
	while(lo <= hi) {
		mid = (lo + hi)/2;
		double x_left = convex[mid].x_left;
		double x_right = convex[mid].x_right;
		if(x_left <= x && x <= x_right) {
			return
				(long long)convex[mid].slope * x + convex[mid].yadd;
		}
		else {
			if(x <= x_left) {
				lo = mid+1;
			}
			else {
				hi = mid-1;
			}
		}
	}
}

int main(void) {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for(int i = 0; i < n; i++) {
		scanf("%lld",&inp[i]);
	}
	A[n-1] = inp[n-1];
	for(int i = n-2; i >= 0; i--) A[i] = A[i+1] + inp[i];
	S[n-1] = A[n-1];
	for(int i = n-2; i >= 0; i--) S[i] = S[i+1] + A[i];

	if(n == 1) {
		printf("%lld\n",max(inp[0],0ll));
		return 0;
	}

	// input data processed
	convex.push_back(lineinfo(0,S[0],-INF,INF));
	D[0] = max(inp[0],0ll);
	for(int i = 1; i < n; i++) {
		long long a = -i,b = S[i] + D[i-1];
		while((int)convex.size() > 0) {
			long long c = convex.back().slope,d = convex.back().yadd;
			double intersect_x = (double)(b-d)/(c-a);
			if(convex.back().x_left <= intersect_x &&
				intersect_x <= convex.back().x_right) {
				convex.back().x_left = intersect_x;
				convex.push_back(
					lineinfo(a,b,-INF,intersect_x)
					);
				break;
			}
			convex.pop_back();
		}
		long long val = bsearch(A[i+1]) - S[i+1] - (i+1)*A[i+1];
		D[i] = max(D[i-1],val);
	}
	printf("%lld\n",D[n-1]);

	return 0;
}

• Subtask 1: 0 / 26
• Subtask 2: 0 / 44