답안 #91514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91514 2018-12-28T03:08:21 Z Just_Solve_The_Problem UFO (IZhO14_ufo) C++11
100 / 100
905 ms 153356 KB
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
struct T {
	vector < int > tree;
	T() {
	}
	void init(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());
		row[i].init(m);
	}
		
	for (int i = 0; i < m; i++) {
		col.push_back(T());
		col[i].init(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;
		cin >> tp;
		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:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &in, &h);
   ~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Correct 16 ms 1048 KB Output is correct
5 Correct 87 ms 3792 KB Output is correct
6 Correct 226 ms 25940 KB Output is correct
7 Correct 366 ms 61900 KB Output is correct
8 Correct 339 ms 63764 KB Output is correct
9 Correct 576 ms 63764 KB Output is correct
10 Correct 618 ms 65188 KB Output is correct
11 Correct 439 ms 65852 KB Output is correct
12 Correct 665 ms 66744 KB Output is correct
13 Correct 731 ms 72060 KB Output is correct
14 Correct 556 ms 72060 KB Output is correct
15 Correct 630 ms 75980 KB Output is correct
16 Correct 330 ms 81260 KB Output is correct
17 Correct 905 ms 86084 KB Output is correct
18 Correct 280 ms 86084 KB Output is correct
19 Correct 440 ms 90740 KB Output is correct
20 Correct 853 ms 153356 KB Output is correct