Submission #15771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15771	2015-07-22T09:09:23 Z	comet	달리는 게임 (kriii3_E)	C++	26 / 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=0;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

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	32968 KB	Output is correct
2	Correct	0 ms	32968 KB	Output is correct
3	Correct	3 ms	32968 KB	Output is correct
4	Correct	3 ms	32968 KB	Output is correct
5	Correct	0 ms	32968 KB	Output is correct
6	Correct	3 ms	32968 KB	Output is correct
7	Correct	0 ms	32968 KB	Output is correct
8	Correct	0 ms	32968 KB	Output is correct
9	Correct	0 ms	32968 KB	Output is correct
10	Correct	0 ms	32968 KB	Output is correct
11	Correct	0 ms	32968 KB	Output is correct
12	Correct	0 ms	32968 KB	Output is correct
13	Correct	0 ms	32968 KB	Output is correct
14	Correct	3 ms	32968 KB	Output is correct
15	Correct	0 ms	32968 KB	Output is correct
16	Correct	3 ms	32968 KB	Output is correct
17	Correct	3 ms	32968 KB	Output is correct
18	Correct	0 ms	32968 KB	Output is correct

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	-