fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. long long int dpsolve(std::vector<int> dec, int n){
  7.  
  8.         sort(dec.begin(), dec.end());
  9.  
  10.  
  11.  
  12.         // for(auto d: dec) cout << d <<endl; cout << "------------"<<endl;
  13.  
  14.         long long int dp[n][n];
  15.  
  16.         for (int i = 0; i < n; ++i)
  17.  
  18.                 dp[i][i] = 0LL;
  19.  
  20.         // i - row is the lower index
  21.  
  22.         // j - col is the higher one
  23.  
  24.         // dp is sum of discrepancy from i to j
  25.  
  26.         // dp[0][n-1] = arr[n-1] - arr[0] + min(dp[0][n-2], dp[1][n-1])
  27.  
  28.         // dp[i][j] = arr[j] - arr[i] + min(dp[i][j-1], dp[i+1][j])
  29.  
  30.         for (int i = n-1; i >= 0; --i)
  31.  
  32.         {
  33.  
  34.                 for (int j = i+1; j < n; ++j)
  35.  
  36.                 {
  37.  
  38.                         dp[i][j] = dec[j] - dec[i] + min(dp[i][j-1], dp[i+1][j]);
  39.  
  40.                 }
  41.  
  42.         }/*
  43.  
  44.         int r = 0;
  45.  
  46.         int c = n-1;
  47.  
  48.         for (int i = 0; i < n; ++i)
  49.  
  50.         {
  51.  
  52.                 if(dp[r][c-1] < dp[r+1][c])
  53.  
  54.                         cout << c <<endl;
  55.  
  56.                 else cout << r <<endl;
  57.  
  58.                 if(dp[r][c-1] < dp[r+1][c])
  59.  
  60.                         c--;
  61.  
  62.                 else r++;
  63.  
  64.         }*/
  65.  
  66.         return dp[0][n-1] ;
  67.  
  68. }
  69.  
  70.  
  71. long long int grsolve(std::vector<int> dec, int n){
  72.  
  73.  
  74.  
  75.         sort(dec.begin(), dec.end());
  76.  
  77.  
  78.  
  79.         std::vector<long int> arr(n);
  80.  
  81.         int l = 0;
  82.  
  83.         int h = n-1;
  84.  
  85.  
  86.         for (int i = 0; i < n; ++i)
  87.  
  88.         {
  89.  
  90.  
  91.                 if((dec[h] - dec[l+1]) > (dec[h-1] - dec[l])){
  92.  
  93.                         arr[n-1-i] = dec[h];
  94.  
  95.                         h--;
  96.  
  97.                 }
  98.  
  99.                 else{
  100.  
  101.                         arr[n-1-i] = dec[l];
  102.  
  103.                         l++;
  104.  
  105.                 }
  106.  
  107.         }
  108.  
  109.  
  110.         long int maximum = arr[0];
  111.  
  112.         long int minimum = arr[0];
  113.  
  114.         long long int sum = 0;
  115.  
  116.         for (int i = 0; i < n; ++i)
  117.  
  118.         {
  119.  
  120.                 maximum = max(maximum, arr[i]);
  121.  
  122.                 minimum = min(minimum, arr[i]);
  123.  
  124.                 sum += maximum - minimum;
  125.  
  126.         }
  127.  
  128.         // cout << sum << endl;
  129.  
  130.         return sum;
  131.  
  132. }
  133.  
  134.  
  135. std::vector<int> randomarray(int n){
  136.  
  137.         std::vector<int> v(n);
  138.  
  139.         for (int i = 0; i < n; ++i)
  140.  
  141.         {
  142.  
  143.                 v[i] = rand()%100;
  144.  
  145.         }
  146.  
  147.         return v;
  148.  
  149. }
  150.  
  151.  
  152. int main(){
  153.  
  154.         int t = 100;
  155.  
  156.         while(t--){
  157.  
  158.                 int n = rand() % 6;
  159.  
  160.                 std::vector<int> arr = randomarray(n);
  161.  
  162.                 long long int res1 = dpsolve(arr, n);
  163.  
  164.                 long long int res2 = grsolve(arr, n);
  165.  
  166.  
  167.                 if(res1 == res2) {cout << "match" <<endl;}
  168.  
  169.                 else{
  170.  
  171.                         cout << "no match" << endl;
  172.  
  173.                         for(auto d: arr){
  174.  
  175.                                 cout  << d <<endl;
  176.  
  177.                         }
  178.  
  179.                         cout << "------------------" << endl;
  180.  
  181.                         break;
  182.  
  183.                 }
  184.  
  185.         }
  186.  
  187. }
Success #stdin #stdout 0s 5524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
match
match
match
match
match
match
no match
68
67
29
82
30
------------------
https://ideone.com/3Pgr1c
language:
C++ (gcc 8.3)
created:
3 years 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!