Submission #12125563


Source Code Expand

Copy
#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

Submission Time
Task E - Active Infants
User hoget157
Language C++ (GCC 9.2.1)
Score 500
Code Size 1576 Byte
Status AC
Exec Time 31 ms
Memory 35128 KB

Judge Result

Set Name Sample FULL
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 26
Set Name Test Cases
Sample Sample_01.txt, Sample_02.txt, Sample_03.txt
FULL Sample_01.txt, Sample_02.txt, Sample_03.txt, maxhand_01.txt, maxhand_02.txt, maxhand_03.txt, maxhand_04.txt, maxhand_05.txt, maxrand_01.txt, maxrand_02.txt, maxrand_03.txt, maxrand_04.txt, maxrand_05.txt, minhand_01.txt, minhand_02.txt, minhand_03.txt, minhand_04.txt, minrand_01.txt, minrand_02.txt, minrand_03.txt, minrand_04.txt, ni_01.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 2 ms 3576 KB
Sample_02.txt AC 1 ms 3524 KB
Sample_03.txt AC 2 ms 3520 KB
maxhand_01.txt AC 28 ms 35016 KB
maxhand_02.txt AC 29 ms 34988 KB
maxhand_03.txt AC 31 ms 34992 KB
maxhand_04.txt AC 28 ms 34988 KB
maxhand_05.txt AC 30 ms 34984 KB
maxrand_01.txt AC 29 ms 34992 KB
maxrand_02.txt AC 31 ms 35096 KB
maxrand_03.txt AC 31 ms 35124 KB
maxrand_04.txt AC 30 ms 35128 KB
maxrand_05.txt AC 29 ms 34908 KB
minhand_01.txt AC 2 ms 3544 KB
minhand_02.txt AC 2 ms 3668 KB
minhand_03.txt AC 2 ms 3568 KB
minhand_04.txt AC 2 ms 3476 KB
minrand_01.txt AC 2 ms 3464 KB
minrand_02.txt AC 2 ms 3600 KB
minrand_03.txt AC 2 ms 3604 KB
minrand_04.txt AC 2 ms 3636 KB
ni_01.txt AC 2 ms 3436 KB
rand_01.txt AC 14 ms 15164 KB
rand_02.txt AC 27 ms 33192 KB
rand_03.txt AC 24 ms 27344 KB
rand_04.txt AC 6 ms 6404 KB