답안 #684045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684045 2023-01-20T07:39:58 Z pragmatist UFO (IZhO14_ufo) C++17
85 / 100
2000 ms 121652 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) 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) 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) s = get3(i, v * 2 + 1, mid + 1, tr, 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') {
			for(int i = n, cnt = r; i >= 1 && cnt; --i) {
				if(a[i][x] >= y) {
				    a[i][x]--;					
				    upd(i, 1, 1, m, x, a[i][x]);
			        upd2(x, 1, 1, n, i, a[i][x]);
					cnt--;
				}
			}
		}
	}
	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 34 ms 70732 KB Output is correct
2 Correct 35 ms 70872 KB Output is correct
3 Correct 33 ms 70780 KB Output is correct
4 Correct 48 ms 71116 KB Output is correct
5 Correct 138 ms 72532 KB Output is correct
6 Correct 204 ms 88068 KB Output is correct
7 Correct 234 ms 107580 KB Output is correct
8 Correct 175 ms 107528 KB Output is correct
9 Correct 465 ms 106840 KB Output is correct
10 Correct 617 ms 107588 KB Output is correct
11 Correct 411 ms 106488 KB Output is correct
12 Correct 661 ms 107580 KB Output is correct
13 Execution timed out 2093 ms 112972 KB Time limit exceeded
14 Correct 693 ms 106496 KB Output is correct
15 Correct 794 ms 107684 KB Output is correct
16 Correct 196 ms 106376 KB Output is correct
17 Execution timed out 2091 ms 113008 KB Time limit exceeded
18 Execution timed out 2091 ms 108236 KB Time limit exceeded
19 Correct 324 ms 109152 KB Output is correct
20 Correct 1070 ms 121652 KB Output is correct