Submission #334253

#	Time	Username	Problem	Language	Result	Execution time	Memory
334253		Pety	UFO (IZhO14_ufo)	C++14	90 / 100	2056 ms	137452 KiB

ufo

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")

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);
}

int mid;

void updateLin (int poz, int nod, int st, int dr, int pozhatz, int val) {
  if (st == dr) {
    aint_lin[poz][nod] = val;
    return;
  }
  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;
  }
  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;
  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;
   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;
  int x;
  int last = 0;
  vector<int > kasa;
  while (r1) {
     x = queryLin(ok, 1, 1 , dr, poz, lvl);
    a[poz][x]--;
    kasa.push_back(x);
    last = 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;
  int last = 0;
  int x;
  vector<int > kasa;
  while (r1) {
    x = queryCol(ok, 1, 1, dr, poz, lvl);
    a[x][poz]--;
    kasa.push_back(x);
    last = 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]);
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  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;
}

Compilation message (stderr)

ufo.cpp: In function 'void Laserlin(int, bool, int, int)':
ufo.cpp:90:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   90 |   int last = 0;
      |       ^~~~
ufo.cpp: In function 'void Lasercol(int, bool, int, int)':
ufo.cpp:108:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  108 |   int last = 0;
      |       ^~~~

• Subtask 1: 90 / 100