Submission #12125563

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }
template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int dp[2010][2010];

signed main(){
	int n,a[2010];
	vector<P> vec;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
		vec.emplace_back(a[i],i);
	}
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++) dp[i][j] = -INF;
	}
	dp[0][0] = 0;
	sort(all(vec),greater<P>());
	for(int i = 0;i < n;i++){
		int v = vec[i].second;
		for(int j = 0;j <= i;j++){
			chmax(dp[i + 1][j],dp[i][j] + abs(n - i + j - 1 - v) * a[v]);
			chmax(dp[i + 1][j + 1],dp[i][j] + abs(v - j) * a[v]);
		}
	}
	int ma = -INF;
	for(int i = 0;i <= n;i++) chmax(ma,dp[n][i]);
	cout << ma << endl;
}

Submission Info

Judge Result