oj.uz

Submission #334228

# Submission time Handle Problem Language Result Execution time Memory
334228 2020-12-08T17:15:28 Z Pety UFO (IZhO14_ufo) C++14
55 / 100
 1497 ms 141864 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m, k, r, p;
vector<vector<int>>aint_lin, aint_col, a;
vector<vector<long long>>sum;

void init () {
  aint_lin.resize(n + 2);
  aint_col.resize(m + 2);
  a.resize(n+2);
  sum.resize(n+2);
  for (int i = 0; i <= n + 1; i++) {
    a[i].resize(m + 2);
    sum[i].resize(m + 2);
    aint_lin[i].resize(4 * m + 2);
  }
  for (int i = 0; i <= m + 1; i++)
    aint_col[i].resize(4 * n + 2);
}

void updateLin (int poz, int nod, int st, int dr, int pozhatz, int val) {
  if (st == dr) {
    aint_lin[poz][nod] = val;
    return;
  }
  int mid = (st + dr) / 2;
  if (pozhatz <= mid)
    updateLin(poz, 2 * nod, st, mid, pozhatz, val);
  else
    updateLin(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
  aint_lin[poz][nod] = max(aint_lin[poz][2 * nod], aint_lin[poz][2 * nod + 1]);
}

void updateCol (int poz, int nod, int st, int dr, int pozhatz, int val) {
  if (st == dr) {
    aint_col[poz][nod] = val;
    return;
  }
  int mid = (st + dr) / 2;
  if (pozhatz <= mid)
    updateCol(poz, 2 * nod, st, mid, pozhatz, val);
  else
    updateCol(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
  aint_col[poz][nod] = max(aint_col[poz][2 * nod], aint_col[poz][2 * nod + 1]);
}

int queryLin (bool ok, int nod, int st, int dr, int poz, int lvl) {
  if (st == dr)
    return st;
  int mid = (st + dr) / 2;
  if (!ok) {
    if (aint_lin[poz][2 * nod] >= lvl)
      return queryLin(ok, 2* nod, st, mid, poz, lvl);
    else
      return queryLin(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
  }
  else {
    if (aint_lin[poz][2 * nod + 1] >= lvl)
      return queryLin(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
    else
      return queryLin(ok, 2 * nod, st, mid, poz, lvl);
  }
}
int queryCol (bool ok, int nod, int st, int dr, int poz, int lvl) {
  if (st == dr)
    return st;
  int mid = (st + dr) / 2;
  if (!ok) {
    if (aint_col[poz][2 * nod] >= lvl)
      return queryCol(ok, 2* nod, st, mid, poz, lvl);
    else
      return queryCol(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
  }
  else {
    if (aint_col[poz][2 * nod + 1] >= lvl)
      return queryCol(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
    else
      return queryCol(ok, 2 * nod, st, mid, poz, lvl);
  }
}

void Laserlin (int dr, bool ok, int poz, int lvl) {
  int r1 = r;
  while (r1 && aint_lin[poz][1] >= lvl) {
    int x = queryLin(ok, 1, 1, dr, poz, lvl);
    a[poz][x]--;
    updateLin(poz, 1, 1, m, x, a[poz][x]);
    updateCol(x, 1, 1, n, poz, a[poz][x]);
    r1--;
  }
}

void Lasercol (int dr, bool ok, int poz, int lvl) {
  int r1 = r;
  while (r1 && aint_col[poz][1] >= lvl) {
    int x = queryCol(ok, 1, 1, dr, poz, lvl);
    a[x][poz]--;
    updateCol(poz, 1, 1, n, x, a[x][poz]);
    updateLin(x, 1, 1, m, poz, a[x][poz]);
    r1--;

  }
}

int main()
{
  cin >> n >> m >> r >> k >> p;
  init();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      cin >> a[i][j];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      updateLin(i, 1, 1, m, j, a[i][j]);
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      updateCol(i, 1, 1, n, j, a[j][i]);
  char ch;
  int poz, lvl;
  for (int i = 1; i <= k; i++) {
    cin >> ch >> poz >> lvl;
    if (ch == 'N') Lasercol(n, 0, poz, lvl);
    if (ch == 'S') Lasercol(n, 1, poz, lvl);
    if (ch == 'W') Laserlin(m, 0, poz, lvl);
    if (ch == 'E') Laserlin(m, 1, poz, lvl);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  long long ans = 0;
  for (int i = p; i <= n; i++)
    for (int j = p; j <= m; j++)
      ans = max(ans, sum[i][j] - sum[i - p][j] - sum[i][j - p] + sum[i - p][j - p]);
  cout << ans;
  return 0;
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 3 ms 492 KB Output isn't correct
4 Incorrect 31 ms 876 KB Output isn't correct
5 Incorrect 142 ms 3692 KB Output isn't correct
6 Incorrect 381 ms 24940 KB Output isn't correct
7 Incorrect 751 ms 60836 KB Output isn't correct
8 Correct 603 ms 57244 KB Output is correct
9 Correct 896 ms 51692 KB Output is correct
10 Correct 1098 ms 56340 KB Output is correct
11 Correct 829 ms 56428 KB Output is correct
12 Correct 1103 ms 56684 KB Output is correct
13 Correct 1324 ms 65200 KB Output is correct
14 Correct 947 ms 56300 KB Output is correct
15 Incorrect 1024 ms 58092 KB Output isn't correct
16 Correct 630 ms 58348 KB Output is correct
17 Incorrect 1497 ms 69612 KB Output isn't correct
18 Correct 600 ms 61292 KB Output is correct
19 Incorrect 785 ms 67308 KB Output isn't correct
20 Correct 1461 ms 141864 KB Output is correct