#include "bits/stdc++.h"
using namespace std;
#define ll long long
vector <vector <int>> a, st[4];
int n, m, R, k, p, ind;
int bld(int nd, int l, int r, int t, int rc){
if(l == r) {
if(t == 0) st[t][rc][nd] = a[l][rc];
else st[t][rc][nd] = a[rc][l];
return st[t][rc][nd];
}
int md = (l + r) / 2;
return st[t][rc][nd] = max(bld(nd*2,l,md,t,rc), bld(nd*2+1,md+1,r,t,rc));
}
int fnd(int nd, int l, int r, int rc, int t1, int t2, int x){
if((st[t1][rc][nd] < x) or (r <= ind and t2 == 0) or (l >= ind and t2 == 1)) return 0;
if(l == r) return l;
int md = (l + r) / 2;
if(t2 == 0){
int in = fnd(nd*2,l,md,rc,t1,t2,x);
if(in != 0) return in;
return fnd(nd*2+1,md+1,r,rc,t1,t2,x);
}
int in = fnd(nd*2+1,md+1,r,rc,t1,t2,x);
if(in != 0) return in;
return fnd(nd*2,l,md,rc,t1,t2,x);
}
int upd(int nd, int l, int r, int t, int rc, int in){
if(l > in or r < in) return st[t][rc][nd];
if(l == r) return st[t][rc][nd] = st[t][rc][nd]-1;
int md = (l + r) / 2;
return st[t][rc][nd] = max(upd(nd*2,l,md,t,rc,in), upd(nd*2+1,md+1,r,t,rc,in));
}
void fn(int nd, int l, int r, int t, int rc){
if(l == r){
a[rc][l] = st[t][rc][nd];
return;
}
int md = (l + r) / 2;
fn(nd*2,l,md,t,rc), fn(nd*2+1,md+1,r,t,rc);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> R >> k >> p;
a.resize(n+1, vector <int> (m+1));
st[0].resize(m+1), st[1].resize(n+1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
for(int i = 1; i <= m; i++){
st[0][i].resize((n+1)*4);
bld(1,1,n,0,i);
}
for(int i = 1; i <= n; i++){
st[1][i].resize((m+1)*4);
bld(1,1,m,1,i);
}
for(int i = 1; i <= k; i++){
char c;
int rc, x;
cin >> c >> rc >> x;
int c1, c2;
if(c == 'N') c1 = 0, c2 = 0;
if(c == 'W') c1 = 1, c2 = 0;
if(c == 'S') c1 = 0, c2 = 1;
if(c == 'E') c1 = 1, c2 = 1;
if(c2 == 0) ind = 0;
else ind = max(n,m)+1;
for(int j = 1; j <= R; j++){
ind = fnd(1,1,(!c1 ? n : m),rc,c1,c2,x);
if(ind == 0) break;
if(c1 == 0){
upd(1,1,n,0,rc,ind);
upd(1,1,m,1,ind,rc);
}
else {
upd(1,1,m,1,rc,ind);
upd(1,1,n,0,ind,rc);
}
}
}
for(int i = 1; i <= n; i++){
fn(1,1,m,1,i);
}
ll ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
ll x = 0;
if(i+p-1 > n or j+p-1 > m) continue;
for(int i1 = i; i1 < i+p; i1++){
for(int j1 = j; j1 < j+p; j1++){
x += a[i1][j1];
}
}
ans = max(ans, x);
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |