oj.uz

답안 #341132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341132 2020-12-29T03:42:39 Z tengiz05 UFO (IZhO14_ufo) C++17
100 / 100
 1126 ms 97188 KB 
#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k, r, P;
vector<int> decreased;
struct segtree{
	int sz;
	vector<int> t;
	void build(int n, vector<int> v){
		assert((int)v.size() == n+1);
		sz=1;
		while(sz < n)sz<<=1;
		t.assign(sz*2, 0);
		for(int i=0;i<n;i++){
			t[i+sz] = v[i+1];
		}for(int i=sz-1;i>0;i--){
			t[i] = max(t[i<<1], t[i<<1|1]);
		}
	}
	void decrease_it(int pos){
		pos += sz;
		for(t[pos]--; pos > 1; pos >>= 1)t[pos>>1] = max(t[pos], t[pos^1]);
	}
	int remaining;
	int height;
	void going(int L, int R, int x){
		if(remaining == 0 || t[x] < height)return;
		if(R-L == 1){
			t[x]--;
			remaining--;
			decreased.pb(x-sz+1);
			return;
		}int mid = (L+R)/2;
		going(L, mid, x<<1);
		going(mid, R, x<<1|1);
		t[x] = max(t[x<<1], t[x<<1|1]);
	}
	void going_in_reverse(int L, int R, int x){
		if(remaining == 0 || t[x] < height)return;
		if(R-L == 1){
			t[x]--;
			remaining--;
			decreased.pb(x-sz+1);
			return;
		}int mid = (L+R)/2;
		going_in_reverse(mid, R, x<<1|1);
		going_in_reverse(L, mid, x<<1);
		t[x] = max(t[x<<1], t[x<<1|1]);
	}
	void decrease_them(int h){
		decreased.clear();
		remaining = r;
		height = h;
		going(0, sz, 1);
	}
	void decrease_them_in_reverse(int h){
		decreased.clear();
		remaining = r;
		height = h;
		going_in_reverse(0, sz, 1);
	}
	int get(int pos){
		return t[pos+sz];
	}
};
void solve(int test_case){
	int i, j;
	cin >> n >> m >> r >> k >> P;
	vector<vector<int>> a(n+1, vector<int> (m+1));
	vector<vector<int>> pr(n+1, vector<int> (m+1));
	vector<segtree> row(n+1);
	vector<segtree> col(m+1);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	for(i=1;i<=n;i++){
		row[i].build(m, a[i]);
	}
	for(j=1;j<=m;j++){
		vector<int> tmp;
		tmp.pb(0);
		for(i=1;i<=n;i++)tmp.pb(a[i][j]);
		col[j].build(n, tmp);
	}
	while(k--){
		char typ;
		cin >> typ;
		int pos, height;
		cin >> pos >> height;
		if(typ == 'N'){
			int x=1, y=pos;
			col[y].decrease_them(height);
			for(auto pos : decreased){
				row[pos].decrease_it(y-1);
			}
		}else if(typ == 'S'){
			int x=n, y=pos;
			col[y].decrease_them_in_reverse(height);
			for(auto pos : decreased){
				row[pos].decrease_it(y-1);
			}
		}else if(typ == 'E'){
			int x=pos, y=m;
			row[x].decrease_them_in_reverse(height);
			for(auto pos : decreased){
				col[pos].decrease_it(x-1);
			}
		}else {
			int x=pos, y=1;
			row[x].decrease_them(height);
			for(auto pos : decreased){
				col[pos].decrease_it(x-1);
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			a[i][j] = row[i].get(j-1);
		}
	}
		
/*	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cout << a[i][j] << ' ';
		}cout << '\n';
	}*/
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			pr[i][j] = pr[i][j-1] + a[i][j];
		}
		for(j=1;j<=m;j++){
			pr[i][j] += pr[i-1][j];
		}
	}
	int ans = 0;
	for(i=P;i<=n;i++){
		for(j=P;j<=m;j++){
			int area = pr[i][j] + pr[i-P][j-P];
			area -= pr[i-P][j];
			area -= pr[i][j-P];
			chmax(ans, area);
		}
	}cout << ans << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

ufo.cpp: In function 'void solve(int)':
ufo.cpp:105:8: warning: unused variable 'x' [-Wunused-variable]
  105 |    int x=1, y=pos;
      |        ^
ufo.cpp:111:8: warning: unused variable 'x' [-Wunused-variable]
  111 |    int x=n, y=pos;
      |        ^
ufo.cpp:117:15: warning: unused variable 'y' [-Wunused-variable]
  117 |    int x=pos, y=m;
      |               ^
ufo.cpp:123:15: warning: unused variable 'y' [-Wunused-variable]
  123 |    int x=pos, y=1;
      |               ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 9 ms 620 KB Output is correct
5 Correct 45 ms 2284 KB Output is correct
6 Correct 123 ms 15596 KB Output is correct
7 Correct 217 ms 38884 KB Output is correct
8 Correct 177 ms 38884 KB Output is correct
9 Correct 261 ms 34848 KB Output is correct
10 Correct 303 ms 37836 KB Output is correct
11 Correct 228 ms 31764 KB Output is correct
12 Correct 302 ms 37732 KB Output is correct
13 Correct 382 ms 49552 KB Output is correct
14 Correct 480 ms 31252 KB Output is correct
15 Correct 618 ms 38220 KB Output is correct
16 Correct 196 ms 34100 KB Output is correct
17 Correct 904 ms 51856 KB Output is correct
18 Correct 186 ms 44204 KB Output is correct
19 Correct 262 ms 46172 KB Output is correct
20 Correct 1126 ms 97188 KB Output is correct