답안 #684047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684047 2023-01-20T07:45:55 Z pragmatist UFO (IZhO14_ufo) C++17
100 / 100
1062 ms 121648 KB
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define ld long double
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e3 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7; 
const double PI = acos(-1);
ll MOD = (ll)1e9 + 7; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, m, r, q, p;
vector<int> t[N], o[N];
vector<int> a[N];

void build(int i, int v, int tl, int tr) {
    if(tl == tr) {
        t[i][v] = a[i][tl];
        return;
    }
    int mid = (tl + tr) >> 1;
    build(i, v * 2, tl, mid);
    build(i, v * 2 + 1, mid + 1, tr);
    t[i][v] = max(t[i][v * 2], t[i][v * 2 + 1]);
}

void build2(int i, int v, int tl, int tr) {
    if(tl == tr) {
        o[i][v] = a[tl][i];
        return;
    }
    int mid = (tl + tr) >> 1;
    build2(i, v * 2, tl, mid);
    build2(i, v * 2 + 1, mid + 1, tr);
    o[i][v] = max(o[i][v * 2], o[i][v * 2 + 1]);
}

void upd(int i, int v, int tl, int tr, int id, int x) {
    if(tl == tr) {
        t[i][v] = x;
        return;
    }
    int mid = (tl + tr) >> 1;
    if(id <= mid)  
        upd(i, v * 2, tl, mid, id, x);
    else
        upd(i, v * 2 + 1, mid + 1, tr, id, x);
    t[i][v] = max(t[i][v * 2], t[i][v * 2 + 1]);
}

void upd2(int i, int v, int tl, int tr, int id, int x) {
    if(tl == tr) {
        o[i][v] = x;
        return;
    }
    int mid = (tl + tr) >> 1;
    if(id <= mid)
        upd2(i, v * 2, tl, mid, id, x);
    else
        upd2(i, v * 2 + 1, mid + 1, tr, id, x);
    o[i][v] = max(o[i][v * 2], o[i][v * 2 + 1]);
}

int get1(int i, int v, int tl, int tr, int l, int val) {
    if(tr < l) 
        return -1;
    if(tl == tr) {
        return (a[i][tl] >= val ? tl : -1);
    }
    int mid = (tl + tr) >> 1, s = -1;
    if(t[i][v * 2] >= val) s = get1(i, v * 2, tl, mid, l, val);
    if(s == -1 && t[i][v * 2 + 1] >= val) s = get1(i, v * 2 + 1, mid + 1, tr, l, val);
    return s;
}

int get2(int i, int v, int tl, int tr, int l, int val) {
    if(tl > l)
        return -1;
    if(tl == tr) {
        return (a[i][tl] >= val ? tl : -1);
    }
    int mid = (tl + tr) >> 1, s = -1;
    if(t[i][v * 2 + 1] >= val) s = get2(i, v * 2 + 1, mid + 1, tr, l, val);
    if(s == -1 && t[i][v * 2] >= val) s = get2(i, v *  2, tl, mid, l, val);
    return s;
}

int get3(int i, int v, int tl, int tr, int l, int val) {
    if(tr < l) 
        return -1;
    if(tl == tr) {
        return (a[tl][i] >= val ? tl : -1);
    }
    int mid = (tl + tr) >> 1, s = -1;
    if(o[i][v * 2] >= val) s = get3(i, v * 2, tl, mid, l, val);
    if(s == -1 && o[i][v * 2 + 1] >= val) s = get3(i, v * 2 + 1, mid + 1, tr, l, val);
    return s;
}

int get4(int i, int v, int tl, int tr, int l, int val) {
    if(tl > l)
        return -1;
    if(tl == tr) {
        return (a[tl][i] >= val ? tl : -1);
    }
    int mid = (tl + tr) >> 1, s = -1;
    if(o[i][v * 2 + 1] >= val) s = get4(i, v * 2 + 1, mid + 1, tr, l, val);
    if(s == -1 && o[i][v * 2] >= val) s = get4(i, v *  2, tl, mid, l, val);
    return s;
}

void solve() {
	cin >> n >> m >> r >> q >> p;
	for(int i = 1; i <= n; ++i) {
		a[i].resize(m + 1);
		t[i].resize(4 * m + 7);
		for(int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
		build(i, 1, 1, m);
	}
	for(int i = 1; i <= m; ++i) {
	    o[i].resize(4 * n + 1);
	    build2(i, 1, 1, n);
	}
	while(q--) {
		char tp;
		cin >> tp;
		int x, y;
		cin >> x >> y;
		if(tp == 'W') {
			int i = 0, cnt = r;
			while(cnt--) {
				if(i == m) break;
                i = get1(x, 1, 1, m, i + 1, y);
                if(i == -1) break;
                a[x][i]--;
                upd(x, 1, 1, m, i, a[x][i]);
			    upd2(i, 1, 1, n, x, a[x][i]);
			}
		}
		if(tp == 'E') {
			int i = m + 1, cnt = r;
			while(cnt--) {
			    if(i == 1) break;
			    i = get2(x, 1, 1, m, i - 1, y);
			    if(i == -1) break;
			    a[x][i]--;
			    upd(x, 1, 1, m, i, a[x][i]);
			    upd2(i, 1, 1, n, x, a[x][i]);
			}
		} 
		if(tp == 'N') {
			int i = 0, cnt = r;
			while(cnt--) {
			    if(i == n) break;
			    i = get3(x, 1, 1, n, i + 1, y);
			    if(i == -1) break;
			    a[i][x]--;
			    upd(i, 1, 1, m, x, a[i][x]);
			    upd2(x, 1, 1, n, i, a[i][x]);
			}
		}
		if(tp == 'S') {
			int i = n + 1, cnt = r;
			while(cnt--) {
			    if(i == 1) break;
			    i = get4(x, 1, 1, n, i - 1, y);
			    if(i == -1) break;
			    a[i][x]--;
			    upd(i, 1, 1, m, x, a[i][x]);
			    upd2(x, 1, 1, n, i, a[i][x]);
			}
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n - p + 1; ++i) {
		for(int j = 1; j <= m - p + 1; ++j) {
			ll cur = 0;
			for(int ii = i; ii <= i + p - 1; ++ii) {
				for(int jj = j; jj <= j + p - 1; ++jj) {
					cur += a[ii][jj];
				}
			}
			ans = max(ans, cur);
		}
	}
	cout << ans;
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen("g.in", "r", stdin);
//	freopen("g.out", "w", stdout);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70644 KB Output is correct
2 Correct 32 ms 70688 KB Output is correct
3 Correct 32 ms 70812 KB Output is correct
4 Correct 50 ms 71164 KB Output is correct
5 Correct 141 ms 72592 KB Output is correct
6 Correct 225 ms 88068 KB Output is correct
7 Correct 236 ms 107576 KB Output is correct
8 Correct 172 ms 107580 KB Output is correct
9 Correct 490 ms 106864 KB Output is correct
10 Correct 636 ms 107576 KB Output is correct
11 Correct 427 ms 106488 KB Output is correct
12 Correct 662 ms 107468 KB Output is correct
13 Correct 805 ms 113848 KB Output is correct
14 Correct 616 ms 106536 KB Output is correct
15 Correct 755 ms 107588 KB Output is correct
16 Correct 185 ms 106588 KB Output is correct
17 Correct 1062 ms 115400 KB Output is correct
18 Correct 198 ms 111580 KB Output is correct
19 Correct 329 ms 109196 KB Output is correct
20 Correct 1035 ms 121648 KB Output is correct