fork download
copy 
  1. /*
  2. ye mera template hai
  3. apna khud likho bc :P
  4. */
  5.  
  6. /*
  7. Author : Sarvagya Agarwal
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12.  
  13. //defines
  14. #define openin freopen("input.txt","r",stdin)
  15. #define openout freopen("output.txt","w",stdout)
  16. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  17. #define ll long long
  18. #define int long long
  19. #define mod 1000000007
  20. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  21. #define all(c) (c).begin(),(c).end()
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. int power(int a , int b)
  28. {
  29.     int res = 1 ;
  30.     while(b)
  31.     {
  32.         if(b%2) {
  33.             res = (res * a)%mod ;
  34.         }
  35.         b/=2 ;
  36.         a = (a*a)%mod ;
  37.     }
  38.     return res ;
  39. }
  40.  
  41. //debug
  42. #define TRACE
  43.  
  44. #ifdef TRACE
  45. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  46. template <typename Arg1>
  47. void __f(const char* name, Arg1&& arg1){
  48. 		cerr << name << " : " << arg1 << std::endl;
  49. }
  50. template <typename Arg1, typename... Args>
  51. void __f(const char* names, Arg1&& arg1, Args&&... args){
  52. 		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  53. }
  54. #else
  55. #define trace(...)
  56. #endif
  57. int n , k ;
  58. const int inf = 1e18 ;
  59. int dp[10005][2] , dp2[10005][2] ,arr[10005] ;
  60. int32_t main()
  61. {
  62.     fast;
  63.     cin >> n >> k ;
  64.     rep(i,1,n)cin >> arr[i] ;
  65.     dp[0][0] = dp[0][1] = 0 ;
  66.     for(int i = 1 ; i <= n ;++i) {
  67.         int min_cost = inf ;
  68.         for(int j = max(1ll,i-k) ; j < i ; ++j) {
  69.             min_cost = min(min_cost,dp[j][1]) ;
  70.         }
  71.         dp[i][0] = min_cost ;
  72.         dp[i][1] = arr[i] ;
  73.         if(i-k > 1ll) {
  74.             dp[i][1] += min(dp[i-k-1][0],dp[i-k-1][1]) ;
  75.         }
  76.     }
  77.     dp2[n+1][0] = dp2[n+1][1] = 0 ;
  78.     for(int i = n ; i >= 1 ;--i)
  79.     {
  80.         int min_cost = inf ;
  81.         for(int j = i + 1 ; j <= min(i+k,n);++j) {
  82.             min_cost = min(min_cost,dp2[j][1]) ;
  83.         }
  84.         dp2[i][0] = min_cost ;
  85.         dp2[i][1] = arr[i] ;
  86.         if(i+k < n) {
  87.             dp2[i][1] += min(dp2[i+k+1][0],dp2[i+k+1][1]) ;
  88.         }
  89.     }
  90.     int ans = inf ;
  91.     for(int i = 1 ; i <= n ; ++i) {
  92.         int cost = arr[i] ;
  93.         if(i-k > 1)cost += min(dp[i-k-1][0],dp[i-k-1][1]) ;
  94.         if(i+k < n)cost += min(dp2[i+k+1][0],dp2[i+k+1][1]) ;
  95.         ans = min(ans,cost) ;
  96.     }
  97.     cout << ans << endl;
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0s 3856KB
comments (?)
stdin
copy 
3 1
1 1 1
stdout
copy 
1
https://ideone.com/G8BsB3
language:
C++14 (gcc 8.3)
created:
7 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!