fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef unsigned long long ull;
  6. typedef long long ll;
  7. typedef pair<int, int> ii;
  8. typedef vector<ii> vii;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11.  
  12. #define PI (2*acos(0.0))
  13. #define eps 1e-9
  14. #define pcase cout<<"Case "<<++cs<<":"
  15. #define pb push_back
  16. #define endl "\n"
  17. #define watch(x) cout << (#x) << " is " << (x) << endl;
  18. #define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
  19. #define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
  20. #define mp make_pair
  21. #define ff first
  22. #define ss second
  23. #define fu cout << "lol" << endl;
  24. #define precision(n) cout << fixed << setprecision(n);
  25. #define lb lower_bound
  26. #define up upper_bound
  27. #define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
  28. #define all(a) a.begin(), a.end()
  29. #define min3(a,b,c) min(a,min(b,c))
  30. #define max3(a,b,c) max(a,max(b,c))
  31. #define mem(a,val) memset(a,val,sizeof(a))
  32. #define loop(i,n) for(i = 0; i < n; i++)
  33. #define TC() ull T; cin>>T; while(T--)
  34. #define IN(x) {scanf("%d",&x);}
  35. #define LL(x) {scanf("%lld",&x);}
  36. #define CC(x) {scanf("%c",&x);}
  37. #define pfl(x) printf("%d\n",x)
  38. #define pfll(x) printf("%lld\n",x)
  39. #define newl puts("")
  40. #define space printf(" ")
  41. #define MOD 1000000007
  42.  
  43. int main()
  44. {
  45.     int i = 0, j = 0, cs = 0, in;
  46.     int n; cin>>n;
  47.     vector<pair<ll,int>> v;
  48.     for(i = 0; i < n; i++){
  49.         ll a ; cin>>a;
  50.         v.pb({a,i});
  51.     }
  52.     sort(all(v));
  53.     ll dp[4][n+5];
  54.     for(i = 0; i < n+5; i++) dp[0][i] = dp[1][i] = dp[2][i] = 1000000000000000000;
  55.     dp[0][2] = v[2].ff - v[0].ff;
  56.     dp[1][3] = v[3].ff - v[0].ff;
  57.     dp[2][4] = v[4].ff - v[0].ff;
  58.     for(i = 5; i < n; i++){
  59.         dp[0][i] = min3(dp[0][i-3], dp[1][i-3], dp[2][i-3]) + v[i].ff - v[i-2].ff;
  60.         if(i - 4 >= 2) dp[1][i] = min3(dp[0][i-4], dp[1][i-4], dp[2][i-4]) + v[i].ff - v[i-3].ff;
  61.         if(i - 5 >= 2) dp[2][i] = min3(dp[0][i-5], dp[1][i-5], dp[2][i-5]) + v[i].ff - v[i-4].ff;
  62.     }
  63.     cout << min3(dp[0][n-1], dp[1][n-1], dp[2][n-1]) << endl;
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 4456KB
comments (?)
stdin
copy 
10
1 2 5 129 185 581 1041 1909 1580 8150
stdout
copy 
7486
https://ideone.com/5v9BTW
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!