Submission #15770

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15770	2015-07-22T09:06:23 Z	comet	달리는 게임 (kriii3_E)	C++	0 / 70	1000 ms	32968 KB

E

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
ll a[1000010],d[1000010],p[1000010],p2[1000010];
int main(){
	ll n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]=p[i-1]+a[i];
		p2[i]=p2[i-1]+i*a[i];
	}
	for(ll i=1;i<=n;i++){
		d[i]=p2[i];
		for(ll j=1;j<i;j++){
			d[i]=max(d[i],d[j]+(p2[i]-p2[j+1])-(j+1)*(p[i]-p[j+1]));
		}
	}
	cout<<d[n];
}

Subtask #1

0.0 / 26.0

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

Subtask #2

0.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	32964 KB	Program timed out
2	Halted	0 ms	0 KB	-