CF573E Bear and Bowling

Codeforces 原题

Plus:这是一条水黑， $O(n^{2})$ 可过，但是我 Wrong answer on test 22

#include<iostream>
int n;//dp(i,j)表示前i个数选j个数组成子序列的最大答案,类似于背包，倒序更新可以优化成一维
long long a[100005],dp[100005],ans; 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		dp[i]=-1145141919810;
	} 
	for(int i=1;i<=n;i++){
		for(int j=i;j>=1;j--) (dp[j]<dp[j-1]+a[i]*j)?dp[j]=dp[j-1]+j*a[i]:dp[j]=dp[j];//这句话等价于 dp[j]=max(dp[j],dp[j-1]+a[i]*j);
	} //ans初值为0，相当于一个不选的情况
	for(int i=1;i<=n;i++) (ans<dp[i])?ans=dp[i]:ans=ans;//这句话等价于ans=max(ans,dp[i]);
	printf("%lld\n",ans);
	return 0;
}

输出比答案小，请求各位大佬救救孩子吧！