Submission #12133334


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=2003;
int a[N],n;
vpi v;
ll dp[N][N];
ll solv(int i,int l)
{
    if(i>n) return 0;
    if(dp[i][l]!=-1) return dp[i][l];
    ll ans=0;
    int r=l+(n-i);
    ans =1ll*v[i-1].first*abs(v[i-1].second-l)+solv(i+1,l+1);
    ans = max(ans,1ll*v[i-1].first*abs(v[i-1].second-r)+solv(i+1,l));
    dp[i][l]=ans;
    return ans;
}
int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            dp[i][j]=-1;
        cin>>a[i];
        v.pb({a[i],i});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(),v.end());
    cout<<solv(1,1)<<"\n";
    
    return 0;
}

Submission Info

Submission Time
Task E - Active Infants
User sarwarkhan
Language C++ (GCC 9.2.1)
Score 500
Code Size 891 Byte
Status AC
Exec Time 66 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 3 ms 3544 KB
Sample_02.txt AC 2 ms 3552 KB
Sample_03.txt AC 2 ms 3600 KB
maxhand_01.txt AC 66 ms 35020 KB
maxhand_02.txt AC 63 ms 34888 KB
maxhand_03.txt AC 65 ms 35016 KB
maxhand_04.txt AC 64 ms 35128 KB
maxhand_05.txt AC 62 ms 34884 KB
maxrand_01.txt AC 65 ms 35084 KB
maxrand_02.txt AC 64 ms 34904 KB
maxrand_03.txt AC 65 ms 35060 KB
maxrand_04.txt AC 63 ms 35088 KB
maxrand_05.txt AC 63 ms 34948 KB
minhand_01.txt AC 2 ms 3652 KB
minhand_02.txt AC 2 ms 3628 KB
minhand_03.txt AC 3 ms 3408 KB
minhand_04.txt AC 2 ms 3572 KB
minrand_01.txt AC 2 ms 3632 KB
minrand_02.txt AC 2 ms 3436 KB
minrand_03.txt AC 2 ms 3608 KB
minrand_04.txt AC 2 ms 3576 KB
ni_01.txt AC 2 ms 3456 KB
rand_01.txt AC 20 ms 15116 KB
rand_02.txt AC 57 ms 33188 KB
rand_03.txt AC 41 ms 27396 KB
rand_04.txt AC 7 ms 6548 KB