Submission #91439

#	Time	Username	Problem	Language	Result	Execution time	Memory
91439		Just_Solve_The_Problem	UFO (IZhO14_ufo)	C++11	40 / 100	895 ms	228296 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct T {
	vector < int > tree;
	T() {
	}
	T(int n) {
		tree.resize(4 * n + 7);
	}
	void upd(int pos, int val, int v, int l, int r) {
		if (l == r) {
			tree[v] = val;
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, l, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v] = max(tree[v + v], tree[v + v + 1]);
	}
	
	int findleft(int val, int l, int r, int v, int tl, int tr) {
		if (tl == tr) return tl;
		int mid = (tl + tr) >> 1;
		if (l <= tl && tr <= r) {
			if (tree[v] < val) return -1;
			if (tree[v + v] >= val) {
				return findleft(val, l, r, v + v, tl, mid);
			}
			return findleft(val, l, r, v + v + 1, mid + 1, tr);
		} else {
			int ans = -1;
			if (l <= mid && tree[v + v] >= val) {
				ans = findleft(val, l, r, v + v, tl, mid);
			}
			if (mid + 1 <= r && ans == -1 && tree[v + v + 1] >= val) {
				ans = findleft(val, l, r, v + v + 1, mid + 1, tr);
			}
			return ans;
		}
	}
	
	int findright(int val, int l, int r, int v, int tl, int tr) {
		if (tl == tr) return tl;
		int mid = (tl + tr) >> 1;
		if (l <= tl && tr <= r) {
			if (tree[v] < val) return -1;
			if (tree[v + v + 1] >= val) {
				return findright(val, l, r, v + v + 1, mid + 1, tr);
			}
			return findright(val, l, r, v + v, tl, mid);
		} else {
			int ans = -1;
			if (mid + 1 <= r && tree[v + v + 1] >= val) {
				ans = findright(val, l, r, v + v + 1, mid + 1, tr);
			}
			if (l <= mid && ans == -1 && tree[v + v] >= val) {
				ans = findright(val, l, r, v + v, tl, mid);
			}
			return ans;
		}
	}
};

int n, m, k, r, p;
vector < vector < int > > mat;
vector < T > col, row;

main() {
	scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
	for (int i = 0; i < n; i++) {
		mat.push_back(vector < int > (m));
		for (int j = 0; j < m; j++) {
			scanf("%d", &mat[i][j]);
		}
	}
	for (int i = 0; i < n; i++) 
		row.push_back(T(m));
	for (int i = 0; i < m; i++) 
		col.push_back(T(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			row[i].upd(j, mat[i][j], 1, 0, m - 1);
			col[j].upd(i, mat[i][j], 1, 0, n - 1);
		}
	}
	while (k--) {
		char tp;
		tp = getchar();
		if (tp == '\n') tp = getchar();
		int in, h;
		scanf("%d %d", &in, &h);
		int i = 0;
		in--;
		if (tp == 'N') {
			int pos = -1;
			while (pos + 1 < n && i++ < r) {
				pos = col[in].findleft(h, pos + 1, n - 1, 1, 0, n - 1);
				if (pos == -1) break;
				mat[pos][in]--;
				col[in].upd(pos, mat[pos][in], 1, 0, n - 1);
				row[pos].upd(in, mat[pos][in], 1, 0, m - 1);
			}
		} else if (tp == 'S') {
			int pos = n;
			while (pos - 1 >= 0 && i++ < r) {
				pos = col[in].findright(h, 0, pos - 1, 1, 0, n - 1);
				if (pos == -1) break;
				mat[pos][in]--;
				col[in].upd(pos, mat[pos][in], 1, 0, n - 1);
				row[pos].upd(in, mat[pos][in], 1, 0, m - 1);
			}
		} else if (tp == 'W') {
			int pos = -1;
			while (pos + 1 < m && i++ < r) {
				pos = row[in].findleft(h, pos + 1, m - 1, 1, 0, m - 1);
				if (pos == -1) break;
				mat[in][pos]--;
				row[in].upd(pos, mat[in][pos], 1, 0, m - 1);
				col[pos].upd(in, mat[in][pos], 1, 0, n - 1);
			}
		} else {
			int pos = m;
			while (pos - 1 >= 0 && i++ < r) {
				pos = row[in].findright(h, 0, pos - 1, 1, 0, m - 1);
				if (pos == -1) break;
				mat[in][pos]--;
				row[in].upd(pos, mat[in][pos], 1, 0, m - 1);
				col[pos].upd(in, mat[in][pos], 1, 0, n - 1);
			}
		}
	}
	ll sum[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			sum[i][j] = mat[i][j];
			if (i)
				sum[i][j] += sum[i - 1][j];
			if (j)
				sum[i][j] += sum[i][j - 1];
			if (i && j)
				sum[i][j] -= sum[i - 1][j - 1];
		}
	}
	ll ans = 0;
	for (int i = p - 1; i < n; i++) {
		ll cost = sum[i][p - 1];
		if (i >= p) {
			cost -= sum[i - p][p - 1];
		}
		ans = max(ans, cost);
	}
	for (int i = p - 1; i < m; i++) {
		ll cost = sum[p - 1][i];
		if (i >= p) {
			cost -= sum[p - 1][i - p];
		}
		ans = max(ans, cost);
	}
	for (int i = p; i < n; i++) {
		for (int j = p; j < m; j++) {
			ans = max(ans, sum[i][j] - sum[i][j - p] - sum[i - p][j] + sum[i - p][j - p]);
		}
	}
	cout << ans;
}

Compilation message (stderr)

ufo.cpp:75:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
ufo.cpp: In function 'int main()':
ufo.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &mat[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~
ufo.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &in, &h);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100