Submission #334431

#	Time	Username	Problem	Language	Result	Execution time	Memory
334431		Pety	UFO (IZhO14_ufo)	C++14	100 / 100	1930 ms	140848 KiB

ufo

#include <bits/stdc++.h>


using namespace std;

int n, m, k, r, p, i, j;
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;
  vector<int > kasa;
  while (r1 && aint_lin[poz][1] >= lvl) {
    int x = queryLin(ok, 1, 1 , dr, poz, lvl);
    a[poz][x]--;
    kasa.push_back(x);
    updateLin(poz, 1, 1, m, x, 0);
    r1--;
  }
  for (auto it : kasa) {
    updateLin(poz, 1, 1, m, it, a[poz][it]);
    updateCol(it, 1, 1, n, poz, a[poz][it]);
  }
}

void Lasercol (int dr, bool ok, int poz, int lvl) {
  int r1 = r;
  vector<int > kasa;
  while (r1 && aint_col[poz][1] >= lvl) {
    int x = queryCol(ok, 1, 1, dr, poz, lvl);
    a[x][poz]--;
    kasa.push_back(x);
    updateCol(poz, 1, 1, n, x, 0);
    r1--;
  }
  for (auto it : kasa) {
    updateLin(it, 1, 1, m, poz, a[it][poz]);
    updateCol(poz, 1, 1, n, it, a[it][poz]);
  }
}
void buildLin (int x, int nod, int st, int dr) {
  if (st == dr) {
    aint_lin[x][nod] = a[x][st];
    return;
  }
  int mij = (st + dr) / 2;
  buildLin(x, 2 * nod, st, mij);
  buildLin(x, 2 * nod + 1, mij + 1, dr);
  aint_lin[x][nod] = max(aint_lin[x][2 * nod], aint_lin[x][2 * nod + 1]);
}

void buildCol (int x, int nod, int st, int dr) {
  if (st == dr) {
    aint_col[x][nod] = a[st][x];
    return;
  }
  int mij = (st + dr) / 2;
  buildCol(x, 2 * nod, st, mij);
  buildCol(x, 2 * nod + 1, mij + 1, dr);
  aint_col[x][nod] = max(aint_col[x][2 * nod], aint_col[x][2 * nod + 1]);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m >> r >> k >> p;
  init();
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      cin >> a[i][j];
  for (i = 1; i <= n; i++)
    buildLin(i, 1, 1, m);
  for (i = 1; i <= m; i++)
    buildCol(i, 1, 1, n);
  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 (i = 1; i <= n; i++)
    for (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 (i = p; i <= n; i++)
    for (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: 100 / 100