Submission #15771

#	Time	Username	Problem	Language	Result	Execution time	Memory
15771		comet	달리는 게임 (kriii3_E)	C++98	26 / 70	1000 ms	32968 KiB

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 / 26
• Subtask 2: 0 / 44