Submission #12142231


Source Code Expand

Copy
#include<bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector<pair<unsigned long, unsigned long>> A;
    for(unsigned long i{0}, a; i < N; ++i){
        cin >> a;
        A.emplace_back(a, i);
    }
    sort(A.begin(), A.end(), greater<>());
    vector<unsigned long> dp(N + 1), prev(N + 1);
    for(unsigned long i{0}; i < N; ++i){
        dp.swap(prev);
        fill(dp.begin(), dp.end(), 0UL);
        const auto& [a, idx] = A[i];
        for(unsigned long j{0}; j <= i; ++j){
            unsigned long k{N + j - i - 1};
            dp[j] = max(dp[j], prev[j] + a * (max(idx, k) - min(idx, k)));
            dp[j + 1] = max(dp[j + 1], prev[j] + a * (max(idx, j) - min(idx, j)));
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Active Infants
User MMNMM
Language C++ (GCC 9.2.1)
Score 500
Code Size 840 Byte
Status AC
Exec Time 20 ms
Memory 3708 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 7 ms 3420 KB
Sample_02.txt AC 2 ms 3496 KB
Sample_03.txt AC 2 ms 3496 KB
maxhand_01.txt AC 16 ms 3488 KB
maxhand_02.txt AC 20 ms 3508 KB
maxhand_03.txt AC 14 ms 3628 KB
maxhand_04.txt AC 18 ms 3708 KB
maxhand_05.txt AC 15 ms 3604 KB
maxrand_01.txt AC 17 ms 3680 KB
maxrand_02.txt AC 16 ms 3704 KB
maxrand_03.txt AC 18 ms 3604 KB
maxrand_04.txt AC 17 ms 3632 KB
maxrand_05.txt AC 17 ms 3564 KB
minhand_01.txt AC 2 ms 3416 KB
minhand_02.txt AC 2 ms 3632 KB
minhand_03.txt AC 4 ms 3428 KB
minhand_04.txt AC 2 ms 3436 KB
minrand_01.txt AC 2 ms 3476 KB
minrand_02.txt AC 2 ms 3492 KB
minrand_03.txt AC 2 ms 3560 KB
minrand_04.txt AC 2 ms 3624 KB
ni_01.txt AC 2 ms 3632 KB
rand_01.txt AC 9 ms 3632 KB
rand_02.txt AC 15 ms 3664 KB
rand_03.txt AC 13 ms 3656 KB
rand_04.txt AC 3 ms 3436 KB