Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: wtfalex2
- LANG: C++14
- PROB: castle
- */
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:256000000")
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <vector>
- #include <ctime>
- #include <map>
- #include <set>
- #include <string>
- #include <queue>
- #include <deque>
- #include <cassert>
- #include <cstdlib>
- #include <bitset>
- #include <algorithm>
- #include <string>
- #include <list>
- #include <fstream>
- #include <cstring>
- #include <climits>
- #include <stack>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef pair<string, int> psi;
- typedef vector<string> vs;
- typedef pair<ll, ll> pll;
- typedef vector<ll> vll;
- typedef vector<char> vc;
- typedef vector<pii> vpii;
- typedef vector<pair<ll, ll> > vpll;
- typedef long double ld;
- #define forn(i, n) for (int i = 0; i < (int)n; i++)
- #define for1(i, n) for (int i = 1; i <= (int)n; i++)
- #define forq(i, s, t) for (int i = s; i <= t; i++)
- #define ford(i, s, t) for (int i = s; i >= t; i--)
- #define mk make_pair
- #define inb push_back
- #define outb pop_back
- #define all(v) v.begin(), v.end()
- #define X first
- #define Y second
- #define TIME clock() * 1.0 / CLOCKS_PER_SEC
- #define sqr(x) (x) * (x)
- #define y1 amdknkgsdaasdwapgnpikn
- //
- #define mp make_pair
- #define pb push_back
- #define XX first
- #define YY second
- //
- const ld EPS = 1e-9;
- const ld pi = acos(-1.0);
- const int MAXN = (int)4e5 + 7;
- const ll INF = (ll)(1ll << 31ll) - 1ll;
- const ll LINF = (ll)7e18;
- const ll MOD = (ll)1e9 + 7;
- const int CHASH = (ll)239017;
- const ld DINF = (ld)1000000000000000.0;
- void mkfile();
- int solve();
- int main()
- {
- #define TASK "ufo"
- #ifdef _DEBUG
- mkfile();
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- freopen("test.txt", "w", stderr);
- ld tstart = TIME;
- srand(2299);
- #else
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout), freopen("test.txt", "w", stderr);
- srand(time(0));
- #endif
- solve();
- #ifdef _DEBUG
- ld tend = TIME;
- cerr << tend - tstart << " s.\n";
- #endif
- return 0;
- }
- void mkfile()
- {
- freopen("input.txt", "a+", stdout);
- srand(time(0));
- return;
- }
- bool equal(double a, double b)
- {
- return abs(a - b) < EPS;
- }
- const int MM = (int)4e8 + 7;
- int n, m, p, r, k;
- vector<vi> a;
- vector<vi> dp;
- vector<vi> t[2];
- int ans;
- void buildRow(int id, int v, int tl, int tr)
- {
- if (tl == tr)
- t[0][id][v] = a[id][tl];
- else
- {
- int tm = tl + tr >> 1;
- buildRow(id, (v << 1) + 1, tl, tm);
- buildRow(id, (v << 1) + 2, tm + 1, tr);
- t[0][id][v] = max(t[0][id][(v << 1) + 1], t[0][id][(v << 1) + 2]);
- }
- }
- void buildCol(int id, int v, int tl, int tr)
- {
- if (tl == tr)
- t[1][v][id] = a[tl][id];
- else
- {
- int tm = tl + tr >> 1;
- buildCol(id, (v << 1) + 1, tl, tm);
- buildCol(id, (v << 1) + 2, tm + 1, tr);
- t[1][v][id] = max(t[1][(v << 1) + 1][id], t[1][(v << 1) + 2][id]);
- }
- }
- int findLRow(int id, int v, int tl, int tr, int pos, int val)
- {
- if (tr < pos || t[0][id][v] < val)
- return -1;
- if (tl == tr)
- return tl;
- int tm = tl + tr >> 1;
- int ql = findLRow(id, (v << 1) + 1, tl, tm, pos, val);
- if (ql == -1)
- return findLRow(id, (v << 1) + 2, tm + 1, tr, pos, val);
- return ql;
- }
- int findRRow(int id, int v, int tl, int tr, int pos, int val)
- {
- if (tl > pos || t[0][id][v] < val)
- return -1;
- if (tl == tr)
- return tl;
- int tm = tl + tr >> 1;
- int qr = findRRow(id, (v << 1) + 2, tm + 1, tr, pos, val);
- if (qr == -1)
- return findRRow(id, (v << 1) + 1, tl, tm, pos, val);
- return qr;
- }
- int findUCol(int id, int v, int tl, int tr, int pos, int val)
- {
- if (tr < pos || t[1][v][id] < val)
- return -1;
- if (tl == tr)
- return tl;
- int tm = tl + tr >> 1;
- int ql = findUCol(id, (v << 1) + 1, tl, tm, pos, val);
- if (ql == -1)
- return findUCol(id, (v << 1) + 2, tm + 1, tr, pos, val);
- return ql;
- }
- int findDCol(int id, int v, int tl, int tr, int pos, int val)
- {
- if (tl > pos || t[1][v][id] < val)
- return -1;
- if (tl == tr)
- return tl;
- int tm = tl + tr >> 1;
- int qr = findDCol(id, (v << 1) + 2, tm + 1, tr, pos, val);
- if (qr == -1)
- return findDCol(id, (v << 1) + 1, tl, tm, pos, val);
- return qr;
- }
- void updateRow(int id, int v, int tl, int tr, int pos)
- {
- if (tl > pos || tr < pos)
- return;
- if (tl == tr)
- {
- --t[0][id][v];
- return;
- }
- int tm = tl + tr >> 1;
- updateRow(id, (v << 1) + 1, tl, tm, pos);
- updateRow(id, (v << 1) + 2, tm + 1, tr, pos);
- t[0][id][v] = max(t[0][id][(v << 1) + 1], t[0][id][(v << 1) + 2]);
- }
- void updateCol(int id, int v, int tl, int tr, int pos)
- {
- if (tl > pos || tr < pos)
- return;
- if (tl == tr)
- {
- --t[1][v][id];
- return;
- }
- int tm = tl + tr >> 1;
- updateCol(id, (v << 1) + 1, tl, tm, pos);
- updateCol(id, (v << 1) + 2, tm + 1, tr, pos);
- t[1][v][id] = max(t[1][(v << 1) + 1][id], t[1][(v << 1) + 2][id]);
- }
- void getRow(int id, int v, int tl, int tr)
- {
- if (tl == tr)
- a[id][tl] = t[0][id][v];
- else
- {
- int tm = tl + tr >> 1;
- getRow(id, (v << 1) + 1, tl, tm);
- getRow(id, (v << 1) + 2, tm + 1, tr);
- }
- }
- int solve()
- {
- scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
- a.resize(n);
- t[0].resize(n);
- t[1].resize(4 * n);
- forn(i, 4 * n)
- t[1][i].resize(m);
- forn(i, n)
- {
- t[0][i].resize(4 * m);
- a[i].resize(m);
- forn(j, m)
- scanf("%d", &a[i][j]);
- }
- forn(i, n)
- buildRow(i, 0, 0, m - 1);
- forn(i, m)
- buildCol(i, 0, 0, n - 1);
- forn(IT, k)
- {
- char c;
- int x, h;
- scanf(" %c %d %d", &c, &x, &h);
- --x;
- if (c == 'N')
- {
- int i = 0;
- int pos = -2;
- while (i < r && pos != -1)
- {
- pos = findUCol(x, 0, 0, n - 1, pos + 1, h);
- if (pos != -1)
- {
- updateCol(x, 0, 0, n - 1, pos);
- updateRow(pos, 0, 0, m - 1, x);
- }
- ++i;
- }
- }
- if (c == 'S')
- {
- int i = 0;
- int pos = n;
- while (i < r && pos != -1)
- {
- pos = findDCol(x, 0, 0, n - 1, pos - 1, h);
- if (pos != -1)
- {
- updateCol(x, 0, 0, n - 1, pos);
- updateRow(pos, 0, 0, m - 1, x);
- }
- ++i;
- }
- }
- if (c == 'W')
- {
- int i = 0;
- int pos = -2;
- while (i < r && pos != -1)
- {
- pos = findLRow(x, 0, 0, m - 1, pos + 1, h);
- if (pos != -1)
- {
- updateRow(x, 0, 0, m - 1, pos);
- updateCol(pos, 0, 0, n - 1, x);
- }
- ++i;
- }
- }
- if (c == 'E')
- {
- int i = 0;
- int pos = m;
- while (i < r && pos != -1)
- {
- pos = findRRow(x, 0, 0, m - 1, pos - 1, h);
- if (pos != -1)
- {
- updateRow(x, 0, 0, m - 1, pos);
- updateCol(pos, 0, 0, n - 1, x);
- }
- ++i;
- }
- }
- }
- forn(i, n)
- getRow(i, 0, 0, m - 1);
- dp.resize(n);
- forn(i, n)
- {
- dp[i].resize(m);
- forn(j, m)
- {
- dp[i][j] = a[i][j];
- if (i && j)
- dp[i][j] = (((((dp[i][j] + dp[i - 1][j]) % MM + dp[i][j - 1]) % MM) - dp[i - 1][j - 1]) % MM + MM) % MM;
- if (i && !j)
- dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MM;
- if (!i && j)
- dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MM;
- if (i >= p && j >= p)
- ans = max(ans, (((((((((dp[i][j] + dp[i - p][j - p]) % MM) - dp[i - p][j]) % MM) + MM) % MM) - dp[i][j - p]) % MM) + MM) % MM);
- if (i >= p && j == p - 1)
- ans = max(ans, ((dp[i][j] - dp[i - p][j]) % MM + MM) % MM);
- if (i == p - 1 && j >= p)
- ans = max(ans, ((dp[i][j] - dp[i][j - p]) % MM + MM) % MM);
- if (i == p - 1 && j == p - 1)
- ans = max(ans, dp[i][j]);
- }
- }
- printf("%d", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement