Submission #91475

# Submission time Handle Problem Language Result Execution time Memory
91475 2018-12-27T16:27:31 Z Just_Solve_The_Problem UFO (IZhO14_ufo) C++11
40 / 100
766 ms 212360 KB
#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) {
		int mid = (tl + tr) >> 1;
		if (l <= tl && tr <= r) {
			if (tree[v] < val) return -1;
			if (tl == tr) return tl;
			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) {
		int mid = (tl + tr) >> 1;
		if (l <= tl && tr <= r) {
			if (tree[v] < val) return -1;
			if (tl == tr) return tl;
			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 + 1][m + 1];
	memset(sum, 0, sizeof sum);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			sum[i][j] = mat[i - 1][j - 1];
			sum[i][j] += sum[i - 1][j];
			sum[i][j] += sum[i][j - 1];
			sum[i][j] -= sum[i - 1][j - 1];
		}
	}
	ll ans = 0;
	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

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);
   ~~~~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 2 ms 688 KB Output is correct
3 Runtime error 3 ms 732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 12 ms 1084 KB Output is correct
5 Correct 56 ms 3296 KB Output is correct
6 Correct 182 ms 21904 KB Output is correct
7 Runtime error 282 ms 85228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 253 ms 85404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 277 ms 85404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 256 ms 85452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 388 ms 94008 KB Output is correct
12 Runtime error 248 ms 94008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 245 ms 94008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 469 ms 97084 KB Output is correct
15 Correct 553 ms 97304 KB Output is correct
16 Runtime error 262 ms 97304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 766 ms 97304 KB Output is correct
18 Runtime error 213 ms 97304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 248 ms 99520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 384 ms 212360 KB Execution killed with signal 11 (could be triggered by violating memory limits)