Submission #12134005


Source Code Expand

Copy
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod=1e9+7;
int dp[2005][2005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  
    cout.tie(0);   
#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif

// -------------------------------------Code starts here---------------------------------------------------------------------     

  int n;
  cin>>n;
  pair<int,int>p[n+1];
  for(int i=1;i<=n;i++)
  {
    cin>>p[i].first;
    p[i].second=i;
  }
  fill_n(&dp[0][0],2005*2005,-1e17);
  dp[0][0]=0;
  sort(p+1,p+n+1,greater<>());
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<=n;j++)
    {
      int z;
      if(j!=0)
      {
        z=abs(j-p[i].second);
        dp[i][j]=max(dp[i][j],dp[i-1][j-1]+z*p[i].first);
      }
      if(j!=n)
      {
        z=abs(n-(i-j)+1-p[i].second);
        dp[i][j]=max(dp[i][j],dp[i-1][j]+z*p[i].first);
      }
    }
  }
  int mx=0;
  for(int i=0;i<=n;i++)
    mx=max(mx,dp[n][i]);
  cout<<mx;
 
// -------------------------------------Code ends here------------------------------------------------------------------
    clock_t clk;
  clk = clock();

    clk = clock() - clk;
  cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
  return 0;
}

Submission Info

Submission Time
Task E - Active Infants
User babayaga
Language C++ (GCC 9.2.1)
Score 500
Code Size 1698 Byte
Status AC
Exec Time 37 ms
Memory 35248 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 21 ms 35116 KB
Sample_02.txt AC 25 ms 35068 KB
Sample_03.txt AC 25 ms 35072 KB
maxhand_01.txt AC 35 ms 35152 KB
maxhand_02.txt AC 34 ms 35156 KB
maxhand_03.txt AC 35 ms 35108 KB
maxhand_04.txt AC 33 ms 35220 KB
maxhand_05.txt AC 34 ms 35212 KB
maxrand_01.txt AC 37 ms 35236 KB
maxrand_02.txt AC 36 ms 35112 KB
maxrand_03.txt AC 34 ms 35220 KB
maxrand_04.txt AC 36 ms 35248 KB
maxrand_05.txt AC 37 ms 35104 KB
minhand_01.txt AC 20 ms 35064 KB
minhand_02.txt AC 22 ms 35200 KB
minhand_03.txt AC 22 ms 35068 KB
minhand_04.txt AC 21 ms 35072 KB
minrand_01.txt AC 24 ms 35172 KB
minrand_02.txt AC 22 ms 35076 KB
minrand_03.txt AC 22 ms 35116 KB
minrand_04.txt AC 23 ms 35120 KB
ni_01.txt AC 21 ms 35072 KB
rand_01.txt AC 24 ms 35228 KB
rand_02.txt AC 34 ms 35104 KB
rand_03.txt AC 29 ms 35148 KB
rand_04.txt AC 22 ms 35220 KB