| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 92774 | SamAnd | UFO (IZhO14_ufo) | C++17 | 2069 ms | 59036 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
#define m_p make_pair
const int N = 1000006;
int n, m, r, k, P;
int** a;
int fun()
{
long long** p;
p = new long long*[n + 1];
for (int i = 0; i <= n; ++i)
p[i] = new long long[m + 1];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
p[i][j] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
long long ans = 0;
for (int x1 = 1; x1 <= n - P + 1; ++x1)
{
int x2 = x1 + P - 1;
for (int y1 = 1; y1 <= m - P + 1; ++y1)
{
int y2 = y1 + P - 1;
//long long t = p[x2][y2] - p[x2][y1 - 1] - p[x1 - 1][y2] + p[x1 - 1][y1 - 1];
long long t = 0;
for (int i = x1; i <= x2; ++i)
{
for (int j = y1; j <= y2; ++j)
{
t += a[i][j];
}
}
ans = max(ans, t);
}
}
return ans;
}
int *tx[N], *ty[N];
void bilx(int i, int tl, int tr, int pos)
{
if (tl == tr)
{
tx[i][pos] = a[i][tl];
return;
}
int m = (tl + tr) / 2;
bilx(i, tl, m, pos * 2);
bilx(i, m + 1, tr, pos * 2 + 1);
tx[i][pos] = max(tx[i][pos * 2], tx[i][pos * 2 + 1]);
}
void bily(int j, int tl, int tr, int pos)
{
if (tl == tr)
{
ty[j][pos] = a[tl][j];
return;
}
int m = (tl + tr) / 2;
bily(j, tl, m, pos * 2);
bily(j, m + 1, tr, pos * 2 + 1);
ty[j][pos] = max(ty[j][pos * 2], ty[j][pos * 2 + 1]);
}
void ubdx(int i, int tl, int tr, int x, int pos)
{
if (tl == tr)
{
tx[i][pos]--;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubdx(i, tl, m, x, pos * 2);
else
ubdx(i, m + 1, tr, x, pos * 2 + 1);
tx[i][pos] = max(tx[i][pos * 2], tx[i][pos * 2 + 1]);
}
void ubdy(int j, int tl, int tr, int x, int pos)
{
if (tl == tr)
{
ty[j][pos]--;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubdy(j, tl, m, x, pos * 2);
else
ubdy(j, m + 1, tr, x, pos * 2 + 1);
ty[j][pos] = max(ty[j][pos * 2], ty[j][pos * 2 + 1]);
}
int qryx(int i, int tl, int tr, int l, int r, int pos)
{
if (tl == l && tr == r)
return tx[i][pos];
int m = (tl + tr) / 2;
if (r <= m)
return qryx(i, tl, m, l, r, pos * 2);
if (l > m)
return qryx(i, m + 1, tr, l, r, pos * 2 + 1);
return max(qryx(i, tl, m, l, m, pos * 2), qryx(i, m + 1, tr, m + 1, r, pos * 2 + 1));
}
int qryy(int j, int tl, int tr, int l, int r, int pos)
{
if (tl == l && tr == r)
return ty[j][pos];
int m = (tl + tr) / 2;
if (r <= m)
return qryy(j, tl, m, l, r, pos * 2);
if (l > m)
return qryy(j, m + 1, tr, l, r, pos * 2 + 1);
return max(qryy(j, tl, m, l, m, pos * 2), qryy(j, m + 1, tr, m + 1, r, pos * 2 + 1));
}
void pre()
{
for (int i = 1; i <= n; ++i)
tx[i] = new int[m * 4 + 1];
for (int j = 1; j <= m; ++j)
ty[j] = new int[n * 4 + 1];
for (int i = 1; i <= n; ++i)
bilx(i, 1, m, 1);
for (int j = 1; j <= m; ++j)
bily(j, 1, n, 1);
}
bool zz = true;
char tyz[N];
int xz[N], hz[N];
void solv1()
{
pre();
queue<pair<int, int> > q;
for (int jj = 0; jj < k; ++jj)
{
char ty = tyz[jj];
int x = xz[jj], h = hz[jj];
if (ty == 'W')
{
int ll = 1;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = m;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryx(x, 1, m, ll, mid, 1) >= h)
r = mid;
else
l = mid;
}
bool z = false;
for (int mid = l; mid <= r; ++mid)
{
if (qryx(x, 1, m, ll, mid, 1) >= h)
{
ll = mid + 1;
q.push(m_p(x, mid));
z = true;
break;
}
}
if (!z)
break;
}
}
else if (ty == 'E')
{
int rr = m;
for (int ii = 0; ii < r; ++ii)
{
int l = 1, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryx(x, 1, m, mid, rr, 1) >= h)
l = mid;
else
r = mid;
}
bool z = false;
for (int mid = r; mid >= l; --mid)
{
if (qryx(x, 1, m, mid, rr, 1) >= h)
{
rr = mid - 1;
q.push(m_p(x, mid));
z = true;
break;
}
}
if (!z)
break;
}
}
else if (ty == 'N')
{
int ll = 1;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = n;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryy(x, 1, n, ll, mid, 1) >= h)
r = mid;
else
l = mid;
}
bool z = false;
for (int mid = l; mid <= r; ++mid)
{
if (qryy(x, 1, n, ll, mid, 1) >= h)
{
ll = mid + 1;
q.push(m_p(mid, x));
z = true;
break;
}
}
if (!z)
break;
}
}
else
{
int rr = n;
for (int ii = 0; ii < r; ++ii)
{
int l = 1, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryy(x, 1, n, mid, rr, 1) >= h)
l = mid;
else
r = mid;
}
bool z = false;
for (int mid = r; mid >= l; --mid)
{
if (qryy(x, 1, n, mid, rr, 1) >= h)
{
rr = mid - 1;
q.push(m_p(mid, x));
z = true;
break;
}
}
if (!z)
break;
}
}
while (!q.empty())
{
ubdx(q.front().first, 1, m, q.front().second, 1);
ubdy(q.front().second, 1, n, q.front().first, 1);
q.pop();
}
/*cout << endl;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
cout << qryx(i, 1, m, j, j, 1).maxu << ' ';
cout << endl;
}
cout << endl;*/
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
a[i][j] = qryx(i, 1, m, j, j, 1);
}
}
cout << fun() << endl;
}
void solv2()
{
pre();
queue<pair<int, int> > q;
for (int jj = 0; jj < k; ++jj)
{
char ty = tyz[jj];
int x = xz[jj], h = hz[jj];
if (ty == 'W')
{
int ll = 1, rr = m;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryx(x, 1, m, ll, mid, 1) >= h)
r = mid;
else
l = mid;
}
rr = r;
bool z = false;
for (int mid = l; mid <= r; ++mid)
{
if (qryx(x, 1, m, ll, mid, 1) >= h)
{
ll = mid + 1;
q.push(m_p(x, mid));
z = true;
break;
}
}
if (!z)
break;
}
}
else if (ty == 'E')
{
int ll = 1, rr = m;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryx(x, 1, m, mid, rr, 1) >= h)
l = mid;
else
r = mid;
}
ll = l;
bool z = false;
for (int mid = r; mid >= l; --mid)
{
if (qryx(x, 1, m, mid, rr, 1) >= h)
{
rr = mid - 1;
q.push(m_p(x, mid));
z = true;
break;
}
}
if (!z)
break;
}
}
else if (ty == 'N')
{
int ll = 1, rr = n;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryy(x, 1, n, ll, mid, 1) >= h)
r = mid;
else
l = mid;
}
rr = r;
bool z = false;
for (int mid = l; mid <= r; ++mid)
{
if (qryy(x, 1, n, ll, mid, 1) >= h)
{
ll = mid + 1;
q.push(m_p(mid, x));
z = true;
break;
}
}
if (!z)
break;
}
}
else
{
int ll = 1, rr = n;
for (int ii = 0; ii < r; ++ii)
{
int l = ll, r = rr;
while ((r - l) > 3)
{
int mid = (l + r) / 2;
if (qryy(x, 1, n, mid, rr, 1) >= h)
l = mid;
else
r = mid;
}
ll = l;
bool z = false;
for (int mid = r; mid >= l; --mid)
{
if (qryy(x, 1, n, mid, rr, 1) >= h)
{
rr = mid - 1;
q.push(m_p(mid, x));
z = true;
break;
}
}
if (!z)
break;
}
}
while (!q.empty())
{
ubdx(q.front().first, 1, m, q.front().second, 1);
ubdy(q.front().second, 1, n, q.front().first, 1);
q.pop();
}
/*cout << endl;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
cout << qryx(i, 1, m, j, j, 1).maxu << ' ';
cout << endl;
}
cout << endl;*/
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
a[i][j] = qryx(i, 1, m, j, j, 1);
}
}
cout << fun() << endl;
}
int main()
{
//freopen("ufo.in", "r", stdin);
//freopen("ufo.out", "w", stdout);
scanf(" %d %d %d %d %d", &n, &m, &r, &k, &P);
a = new int*[n + 1];
for (int i = 0; i <= n; ++i)
a[i] = new int[m + 1];
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
scanf(" %d", &a[i][j]);
}
}
for (int jj = 0; jj < k; ++jj)
{
scanf(" %c %d %d", &tyz[jj], &xz[jj], &hz[jj]);
if (hz[jj] != 1)
zz = false;
}
/////////////////////////////////
if (zz)
solv2();
else
solv1();
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||