제출 #251092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251092		dvdg6566	Strah (COCI18_strah)	C++14	88 / 110	1096 ms	46456 KiB

strah

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=2100;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

ll cost[MAXN];
ll R,C;
ll A[MAXN][MAXN];
queue<ll> ep[MAXN];
stack<ll> rm[MAXN];
set<ll> S;
ll cur,ans;

void ins(ll x){
	ll r=*(S.lb(x));
	ll l=*(--S.lb(x));
	S.insert(x);
	cur-=cost[r-l-1];
	cur+=cost[r-x-1];
	cur+=cost[x-l-1];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>R>>C;
	for(ll i=1;i<=C;++i){
		for(ll j=1;j<=i;++j){
			cost[i]+=j*(i-j+1);
		}
	}
	for(ll i=0;i<R;++i){
		string S;cin>>S;
		for(ll j=0;j<C;++j){
			if(S[j]=='#'){
				A[i][j]=1;
				ep[j].push(i);
			}
		}
	}

	// for(ll i=R-1;i>=0;--i){
	// 	for(ll j=0;j<C;++j)cerr<<A[i][j];
	// 	cerr<<'\n';
	// }

	for(ll lowp=0;lowp<R;++lowp){
		S.clear();
		S.insert(-1);S.insert(C);
		cur=cost[C];

		// cerr<<"Low row "<<lowp<<'\n';
		for(ll j=0;j<C;++j)if(SZ(ep[j])&&ep[j].front()<lowp){
			// cerr<<"Removing "<<j<<'\n';
			ep[j].pop();
		}

		for(ll j=0;j<C;++j)if(SZ(ep[j])){
			rm[ep[j].front()].push(j);
		}

		for(ll topr=lowp;topr<R;++topr){
			while(SZ(rm[topr])){
				ins(rm[topr].top());
				rm[topr].pop();
			}
			ans+=cur*(topr-lowp+1);
			// cerr<<"Bottom "<<lowp<<" top "<<topr<<" cost "<<cur*(topr-lowp+1)<<'\n';
		}
	}
	cout<<ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 0 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11