Submission #12114674


Source Code Expand

Copy
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-8;

long long int N, M, K, L, R, H, W;
//int N, M, K, L, R, H, W;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<pair<long long int, int>>v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i].first;
		v[i].second = i + 1;
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	vector<vector<long long int>>dp(N + 2, vector<long long int>(N + 2));
	for (int i = 0; i < N; i++) {
		int len = N - i + 1;
		for (int j = 0; j + len < N + 2; j++) {
			dp[j + 1][j + len] = max(dp[j + 1][j + len], dp[j][j + len] + v[i].first*abs(v[i].second - (j + 1)));
			dp[j][j + len - 1] = max(dp[j][j + len - 1], dp[j][j + len] + v[i].first*abs(v[i].second - (j + len - 1)));
		}
	}
	long long int ans = 0;
	for (int i = 0; i < N + 1; i++) {
		ans = max(ans, dp[i][i + 1]);
	}
	cout << ans << endl;
}

Submission Info

Submission Time
Task E - Active Infants
User olphe
Language C++ (GCC 9.2.1)
Score 500
Code Size 1456 Byte
Status AC
Exec Time 56 ms
Memory 34616 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 3 ms 3516 KB
Sample_02.txt AC 2 ms 3612 KB
Sample_03.txt AC 2 ms 3568 KB
maxhand_01.txt AC 51 ms 34584 KB
maxhand_02.txt AC 56 ms 34600 KB
maxhand_03.txt AC 51 ms 34448 KB
maxhand_04.txt AC 50 ms 34544 KB
maxhand_05.txt AC 55 ms 34612 KB
maxrand_01.txt AC 56 ms 34616 KB
maxrand_02.txt AC 50 ms 34456 KB
maxrand_03.txt AC 50 ms 34616 KB
maxrand_04.txt AC 51 ms 34560 KB
maxrand_05.txt AC 48 ms 34516 KB
minhand_01.txt AC 1 ms 3504 KB
minhand_02.txt AC 2 ms 3576 KB
minhand_03.txt AC 2 ms 3576 KB
minhand_04.txt AC 2 ms 3648 KB
minrand_01.txt AC 3 ms 3512 KB
minrand_02.txt AC 2 ms 3512 KB
minrand_03.txt AC 2 ms 3508 KB
minrand_04.txt AC 2 ms 3512 KB
ni_01.txt AC 2 ms 3572 KB
rand_01.txt AC 18 ms 10736 KB
rand_02.txt AC 49 ms 30880 KB
rand_03.txt AC 31 ms 21136 KB
rand_04.txt AC 7 ms 4400 KB