fork download
copy 
  1. /*
  2.     I hate competitive programming.
  3.                     - sfsdaf_Orz -
  4. */
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <cmath>
  13. #include <cstring>
  14. #include <numeric>
  15. #include <queue>
  16. #include <iomanip>
  17. #include <climits>
  18. #include <algorithm>
  19. #include <deque>
  20.  
  21. using namespace std;
  22. using ll = long long;
  23. using db = double;
  24. using pll = pair<ll, ll> ;
  25. using tpll = tuple<ll, ll, ll> ;
  26. #define f(i, a, b) for(int i = (a); i <= (b); i++)
  27. #define rf(i, a, b) for(int i = (a); i >= (b); i--)
  28. #define af(i, a, b, x) for(int i = (a); i <= (b); i += x)
  29. #define fr(i, a, b, x) for(int i = (a); i >= (b); i -= x)
  30. #define test() int t; cin >> t; while(t--)
  31. #define all(a) (a).begin(), (a).end()
  32. #define rall(a) (a).rbegin(), (a).rend()
  33. #define sz(a) (int)(a).size()
  34. #define pb push_back
  35. #define rv reverse
  36. #define rs resize
  37. #define fi first
  38. #define se second
  39. #define endl '\n'
  40. #define yes "YES"
  41. #define no "NO"
  42. #define gcd __gcd
  43. const ll maxm = 2 * 1e5 + 1;
  44. const ll mod = 1e9 + 7;
  45. const int base = 31;
  46. int n, m, k, d;
  47. vector<ll> a(maxm);
  48. ll row[maxm];
  49. ll p[maxm];
  50. ll ans = LLONG_MAX;
  51. ll caculate(vector<ll> &a){
  52.     vector<ll> dp(m + 1);
  53.     deque<int> q;
  54.     dp[1] = a[1];
  55.     q.pb(1);
  56.     f(i, 2, m){
  57.         while(!q.empty() && q.front() < i - d){
  58.             q.pop_front();
  59.         }
  60.         dp[i] = dp[q.front()] + a[i];
  61.         while(!q.empty() && dp[i] <= dp[q.back()]){
  62.                 q.pop_back();
  63.         }
  64.         q.pb(i);
  65.     }
  66.     return dp[m];
  67. }
  68. void solve() {
  69.     scanf("%d%d%d%d", &n, &m, &k, &d);
  70.     f(i, 1, n){
  71.         f(j, 1, m) {
  72.             scanf("%lld", &a[j]);
  73.         }
  74.         row[i] = caculate(a);
  75.     }
  76.     f(i, 1, n){
  77.         p[i] = p[i - 1] + row[i];
  78.     }
  79.     deque<int> dq;
  80.     f(i, 1, k){
  81.         while(!dq.empty() && row[i] > row[dq.back()]){
  82.             dq.pop_back();
  83.         }
  84.         dq.pb(i);
  85.     }
  86.     ans = min(p[k] - p[1 - 1] - row[dq.front()], ans);
  87.     f(i, k + 1, n){
  88.         if(dq.front() <= i - k){
  89.             dq.pop_front();
  90.         }
  91.         while(!dq.empty() && row[i] > row[dq.back()]) dq.pop_back();
  92.         dq.pb(i);
  93.         ans = min(ans, p[i] - p[i - k] - row[dq.front()]);
  94.     }
  95.     printf("%lld", ans);
  96. }
  97. int main()
  98. {   
  99.     freopen("ENGLISH.INP", "r", stdin);
  100.     freopen("ENGLISH.OUT", "w", stdout);
  101.     solve();
  102. }
  103.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A00qHq
language:
C++14 (gcc 8.3)
created:
5 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!