Submission #129681

#	Time	Username	Problem	Language	Result	Execution time	Memory
129681		jhnah917	조개 줍기 (KOI17_shell)	C++14	100 / 100	604 ms	44696 KiB

shell

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

struct BIT{
	ll tree[1515];
	
	void update(int l, int r, int v){
		for(; l<=n; l+=l&-l) tree[l] += v;
		for(r++; r<=n; r+=r&-r) tree[r] -= v;
	}
	
	ll query(int x){
		ll ret = 0;
		for(; x; x^=x&-x) ret += tree[x];
		return ret;
	}
} tree[1515];

int arr[1515][1515];
int dp[1515][1515];
ll ans = 0;
int s[1515], e[1515];

inline ll get(int i, int j){
	return dp[i][j] + tree[i].query(j);
}

void getDP(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
			ans += dp[i][j];
		}
	}
}

void query(int a, int b, int c){
	s[a] = e[a] = b;
	for(int i=a+1; i<=n; i++) s[i] = n+1, e[i] = 0;
	
	for(int i=a, j=b;;){
		if(j < n && max(get(i-1, j+1), get(i, j)) + c == max(get(i-1, j+1), get(i, j) + c)) j++;
		else i++;
		if(i > n) break;
		e[i] = j;
	}
	for(int i=a, j=b;;){
		if(i < n && max(get(i+1, j-1), get(i, j)) + c == max(get(i+1, j-1), get(i, j) + c)) i++;
		else j++;
		if(j > n || e[i] < j) break;
		s[i] = min(s[i], j);
	}
	
	for(int i=a; i<=n; i++){
		if(s[i] > e[i]) continue;
		tree[i].update(s[i], e[i], c);
		ans += c * (e[i] - s[i] + 1);
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> arr[i][j];
		}
	}
	getDP();
	cout << ans << "\n";
	
	for(int i=1; i<=n; i++){
		int a, b; char op;
		cin >> op >> a >> b;
		if(op == 'U') query(a, b, 1);
		else query(a, b, -1);
	}
}

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