답안 #684042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684042 2023-01-20T07:24:13 Z pragmatist UFO (IZhO14_ufo) C++17
70 / 100
2000 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) 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 < i) 
        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);
    else 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, n, 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 36 ms 70740 KB Output is correct
2 Correct 36 ms 70752 KB Output is correct
3 Correct 32 ms 70740 KB Output is correct
4 Incorrect 45 ms 71028 KB Output isn't correct
5 Incorrect 113 ms 72596 KB Output isn't correct
6 Correct 183 ms 87944 KB Output is correct
7 Incorrect 214 ms 107476 KB Output isn't correct
8 Correct 173 ms 107596 KB Output is correct
9 Correct 426 ms 106884 KB Output is correct
10 Correct 616 ms 107584 KB Output is correct
11 Correct 386 ms 106488 KB Output is correct
12 Correct 673 ms 107596 KB Output is correct
13 Execution timed out 2064 ms 112960 KB Time limit exceeded
14 Correct 645 ms 106496 KB Output is correct
15 Correct 756 ms 107580 KB Output is correct
16 Correct 193 ms 106464 KB Output is correct
17 Execution timed out 2071 ms 113208 KB Time limit exceeded
18 Execution timed out 2083 ms 108236 KB Time limit exceeded
19 Correct 327 ms 109128 KB Output is correct
20 Correct 1045 ms 121648 KB Output is correct