Submission #331606

#	Time	Username	Problem	Language	Result	Execution time	Memory
331606		oolimry	조개 줍기 (KOI17_shell)	C++14	100 / 100	1157 ms	44652 KiB

shell

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int,int> ii;
typedef long long lint;

int n, Q;
struct segment{
	int tree[3005];
	int N;
	void init(int _N){
		N = _N;
		fill(tree,tree+2*N, 0);
	}
	void update(int l, int r, int v){
		for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
			if(l&1) tree[l++] += v;
			if(r&1) tree[--r] += v;
		}
	}
	int query(int i){
		int res = 0;
		for(i += N;i;i >>= 1) res += tree[i];
		return res;
	}
} seg[1505];

int arr[1505][1505];
int dp[1505][1505];

lint ans = 0;


void update(int R, int C, int v){
	int s = C, e = C;
	arr[R][C] += v;
	
	for(int r = R;r <= n;r++){
		while(s < e){
			int recalc = max(seg[r].query(s-1), seg[r-1].query(s)) + arr[r][s];
			int prev = seg[r].query(s);
			
			if(recalc != prev) break;
			s++;
		}
		seg[r].update(s, n, v);
		
		while(e <= n){
			int recalc = max(seg[r].query(e-1), seg[r-1].query(e)) + arr[r][e];
			int prev = seg[r].query(e) - v;
						
			if(recalc == prev) break;
			e++;
		}
		
		seg[r].update(e, n, -v);
		
		ans += v*(e-s);
		
		if(s == e) break;
	}
}

int main(){
	cin >> n; Q = n;
	
	for(int r = 1;r <= n;r++){
		for(int c = 1;c <= n;c++){
			cin >> arr[r][c];
			dp[r][c] = arr[r][c] + max(dp[r-1][c], dp[r][c-1]);
			ans += dp[r][c];
		}
	} 
		
	for(int r = 0;r <= n;r++) seg[r].init(n+1);
	for(int r = 1;r <= n;r++){
		for(int c = 1;c <= n;c++){
			seg[r].update(c,c,dp[r][c]);
		}
	}
	
	cout << ans << "\n";
	while(Q--){
		char cmd; int R, C; cin >> cmd >> R >> C;
		if(cmd == 'U') update(R, C, 1);
		if(cmd == 'D') update(R, C, -1);
		cout << ans << "\n";
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 34 / 34
• Subtask 3: 54 / 54