fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long long   ll;
  3. #define endl        '\n'
  4. #define F           first
  5. #define S           second
  6. #define pb          push_back
  7. #define yes         cout<<"YES\n"
  8. #define no          cout<<"NO\n"
  9. #define all(x)      x.begin(),x.end()
  10. #define allr(x)     x.rbegin(),x.rend()
  11. #define error1(x)   cerr<<#x<<" = "<<(x)<<endl
  12. #define error2(a,b) cout<<"("<<#a<<", "<<#b<<") = ("<<(a)<<", "<<(b)<<")\n";
  13. #define coutall(v)  for(auto &it: v) cout<<it<<" "; cout<<endl;
  14. #define _ASRafi__   ios::sync_with_stdio(false); cin.tie(0);
  15. using namespace std;
  16.  
  17. void solve()
  18. {
  19.     ll n, m, k, d, ans = LLONG_MAX;
  20.     cin >> n >> m >> k >> d;
  21.     vector<vector<ll>> v(n, vector<ll> (m));
  22.     for(auto &i: v) {
  23.         for(auto &j: i) cin >> j;
  24.     }
  25.     ll dp[m][2];
  26.     function<ll(int, bool, int)> rec = [&](int i, bool haveToPickSupport, int row) -> ll
  27.     {
  28.         if(i == m) return 0;
  29.         if(i == m - 1) return 1;
  30.         if(dp[i][haveToPickSupport] != -1) return dp[i][haveToPickSupport];
  31.         ll cost = 1 + v[row][i] + rec(i + 1, 0, row);
  32.         if(haveToPickSupport) return dp[i][haveToPickSupport] = cost;
  33.         for(int dist = 0; dist < d; dist++)
  34.         {
  35.             if(i + dist + 1 >= m) break;
  36.             // error2(i + dist + 1, rec(i + dist + 1, 1, row));
  37.             cost = min(cost, rec(i + dist + 1, 1, row));
  38.         }
  39.         //   cout << i << " => " << cost << endl;
  40.         return dp[i][haveToPickSupport] = cost;
  41.     };
  42.     //  memset(dp, -1, sizeof dp);
  43.     //  cout << rec(0, 0, 0) << endl; 
  44.     deque<ll> dq;
  45.     ll cost = 0;
  46.     for(int i = 0; i < n; i++)
  47.     {
  48.         memset(dp, -1, sizeof dp);
  49.         dq.pb(rec(0, 1, i));
  50.         // cout << i + 1 << " -->> " << dq.back() << endl;
  51.         cost += dq.back();
  52.         if(dq.size() == k) 
  53.         {
  54.             ans = min(ans, cost);
  55.             cost -= dq.front();
  56.             dq.pop_front();
  57.             // cout << " =>> " << ans << endl;
  58.         }
  59.     }
  60.     cout << ans << endl;
  61.     return;
  62. }
  63.  
  64. int32_t main()
  65. {
  66.     _ASRafi__;
  67.     int tc = 1;
  68.     cin >> tc;
  69.     for (int t = 1; t <= tc; t++)
  70.     {
  71.         // cout << "Case " << t << ": ";
  72.         solve();
  73.     }
  74.     return 0;
  75. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
1
2 8 1 1
0 7 2 7 5 1 4 0
0 3 6 10 10 10 1 0
stdout
copy 
13
https://ideone.com/eyQa1v
language:
C++ (gcc 8.3)
created:
19 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!