Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define _test int _TEST; cin>>_TEST; while(_TEST--)
- #define ff first
- #define ss second
- #define pb push_back
- int main()
- {
- _test
- {
- int n, m, k, d;
- cin>>n>>m>>k>>d;
- vector<vector<int>> a(n, vector<int> (m));
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- cin>>a[i][j];
- }
- multiset<ll int> mst;
- vector<ll int> val(m);
- vector<ll int> vals(n);
- for(int i=0; i<n; i++)
- {
- fill(val.begin(), val.end(), 0);
- mst.clear();
- mst.insert(1);
- for(int j=1; j<m; j++)
- {
- val[j] = *mst.begin() + a[i][j] + 1;
- mst.insert(val[j]);
- if(j-d > 1) mst.erase(mst.find(val[j-d-1]));
- if(j-d == 1) mst.erase(mst.find(1));
- }
- vals[i] = val.back();
- }
- for(int i=1; i<n; i++)
- vals[i] += vals[i-1];
- ll int ans = 1e18;
- for(int i=k-1; i<n; i++)
- {
- ll int l = 0;
- if(i-k>=0) l = vals[i-k];
- ans = min(ans, vals[i] - l);
- }
- cout<<ans<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement