oj.uz

Submission #684039

# Submission time Handle Problem Language Result Execution time Memory
684039 2023-01-20T07:03:26 Z pragmatist UFO (IZhO14_ufo) C++17
85 / 100
 2000 ms 73960 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];
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 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]);
}

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;
}

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);
	}
	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]);
			}
		}
		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]);
			}
		}
		if(tp == 'N') {
			for(int i = 1, cnt = r; i <= n && cnt; ++i) {
				if(a[i][x] >= y) {
					a[i][x]--;
					upd(i, 1, 1, m, x, a[i][x]);
					cnt--;
				}
			}
		}
		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]);
					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;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47264 KB Output is correct
2 Correct 21 ms 47220 KB Output is correct
3 Correct 22 ms 47316 KB Output is correct
4 Correct 30 ms 47492 KB Output is correct
5 Correct 105 ms 48248 KB Output is correct
6 Correct 141 ms 56900 KB Output is correct
7 Correct 200 ms 66980 KB Output is correct
8 Correct 137 ms 66764 KB Output is correct
9 Correct 373 ms 66916 KB Output is correct
10 Correct 527 ms 66876 KB Output is correct
11 Correct 350 ms 66096 KB Output is correct
12 Correct 545 ms 66772 KB Output is correct
13 Execution timed out 2072 ms 73960 KB Time limit exceeded
14 Correct 559 ms 66036 KB Output is correct
15 Correct 653 ms 66876 KB Output is correct
16 Correct 158 ms 66100 KB Output is correct
17 Execution timed out 2090 ms 73844 KB Time limit exceeded
18 Execution timed out 2086 ms 71664 KB Time limit exceeded
19 Correct 308 ms 66828 KB Output is correct
20 Correct 997 ms 66852 KB Output is correct