fork download 
  1. // author : anphung
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define file "GAME"
  5. #define int64 long long
  6. #define f0(i,a,b) for(int (i) = (a); (i) <= (b); ++i)
  7. #define inf 1e18
  8. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  9.  
  10. int n,k;
  11. vector<int> h;
  12. int64 ans = 1e18;
  13.  
  14. void Try(int pos, int64 d){
  15.     if(pos==n){
  16.         ans = min(ans, d);
  17.         return;
  18.     }
  19.     for(int i=1; i<=k && pos+i<=n;++i){
  20.         Try(pos+i, d+abs(h[pos]-h[i+pos]));
  21.     }
  22. }
  23.  
  24. void trau(){
  25.     Try(1,0);
  26.     cout<<ans;
  27. }
  28.  
  29. void sol(){
  30.     vector<int64> dp(n+1, inf);
  31.  
  32.     dp[1] = 0;
  33.     f0(i,1,n){
  34.         f0(j,i+1,min(n,i+k)){
  35.             dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j]));
  36.         }
  37.     }
  38.     cout<<dp[n];
  39. }
  40. int32_t main(){
  41.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  42.     freopen(file".inp","r",stdin);
  43.     freopen(file".out","w",stdout);
  44.  
  45.     cin>>n>>k;
  46.     h.resize(n+1);
  47.  
  48.     f0(i,1,n)cin>>h[i];
  49.     sol();
  50.     //cerr<<"\ntime elapsed: "<<TIME <<"s.\n";
  51. }
  52.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/iUPMTD
language:
C++14 (gcc 8.3)
created:
2 days 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!