fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define N int(200)
  4. using namespace std;
  5. ll dp[N+10][N+10][3];
  6. vector<ll>v;
  7. ll n, pos;
  8. int main()
  9. {
  10.     ios::sync_with_stdio(0);
  11.     cin.tie(0);
  12.     cout.tie(0);
  13.  
  14.     cin>>n;
  15.     for(int i=1; i<=n; i++)
  16.     {
  17.         ll x;
  18.         cin>>x;
  19.         v.push_back(x);
  20.     }
  21.     v.push_back(0);
  22.     sort(v.begin(),v.end());
  23.     ll pos = lower_bound(v.begin(), v.end(), 0) - v.begin();
  24.     for(int i=0; i<=n; i++)
  25.         for(int j=0; j<=n; j++)
  26.         {
  27.             dp[i][j][0]=1e9;
  28.             dp[i][j][1]=1e9;
  29.         }
  30.     dp[pos][pos][0]=dp[pos][pos][1]=0;
  31.     ll l=n+1;
  32.     for(int len=1; len<=l; len++)
  33.     {
  34.         for(int i=0; i<(l-len+1); i++)
  35.         {
  36.             ll j=i+len-1;
  37.             ll cl=l-len;
  38.             if(dp[i][j][0]<1e9)
  39.             {
  40.  
  41.                 if(i>0)
  42.                 {
  43.                     ll dif=abs(v[i]-v[i-1]);
  44.                     ll them=dif*cl;
  45.                     dp[i-1][j][0]=min( dp[i-1][j][0], dp[i][j][0]+them);
  46.                 }
  47.                 if(j<l)
  48.                 {
  49.                     ll dif=abs(v[i]-v[j+1]);
  50.                     ll them=dif*cl;
  51.                     dp[i][j+1][1]=min( dp[i][j+1][1],dp[i][j][0]+them);
  52.                 }
  53.             }
  54.             if(dp[i][j][1]<1e9)
  55.             {
  56.                 if(i>0)
  57.                 {
  58.                     ll dif=abs(v[j]-v[i-1]);
  59.                     ll them=dif*cl;
  60.                     dp[i-1][j][0]=min( dp[i-1][j][0], dp[i][j][1]+them);
  61.                 }
  62.                 if(j<l)
  63.                 {
  64.                     ll dif=abs(v[j]-v[j+1]);
  65.                     ll them=dif*cl;
  66.                     dp[i][j+1][1]=min( dp[i][j+1][1],dp[i][j][1]+them);
  67.                 }
  68.             }
  69.         }
  70.     }
  71.     cout<<min(dp[0][n][0],dp[0][n][1]);
  72.     return 0;
  73. }
  74.  
  75.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/TAXmgf
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!