Submission #166949

#	Time	Username	Problem	Language	Result	Execution time	Memory
166949		muhi1112	Strah (COCI18_strah)	C++17	110 / 110	846 ms	82192 KiB

strah

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

#define f1 first
#define s2 second
#define mp make_pair
#define pb push_back
#define ll long long 
#define fri(a) freopen(a,"r",stdin);
#define fro(a) freopen(a,"w",stdout);
const ll N=3e3+5;
const ll K=30;

ll n,m,dp[N][N],hist[N],ans;
pair<ll,ll>st[N][K];
char grid[N][N];

ll calc(ll i,ll j){
	return ((i*(i+1)*j*(j+1))/4);
}
void calctable(){
	for(ll i=1;i<N;i++){
		for(ll j=1;j<N;j++){
			dp[i][j]=dp[i-1][j]+calc(i,j);
		}
	}
}
void build(){
	for(ll i=1;i<=m;i++){
		st[i][0]={hist[i],i};
	}
	for(ll j=1;j<K;j++){
		for(ll i=1;i+(1<<j)<=N;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
pair<ll,ll> qmin(ll l,ll r){
	ll j=log2(r-l+1);
	return min(st[l][j],st[r-(1<<j)+1][j]);
}
ll solve(ll l,ll r){
	if(l>r){
		return 0;
	}
	//cout<<l<<" "<<r<<endl;
	if(l==r){
		//cout<<l<<"  "<<r<<endl;
		//cout<<calc(1,hist[l])<<endl;
		return calc(1,hist[l]);
	}
	pair<ll,ll> x=qmin(l,r);
	//cout<<l<<" "<<r<<" "<<x.f1<<" "<<x.s2<<endl;
	ll ans=0;
	ll left=solve(l,x.s2-1);
	ll right=solve(x.s2+1,r);
	ans=left+right;
	//cout<<ans<<endl;
	ans+=(dp[r-l+1][x.f1]-dp[x.s2-l][x.f1]-dp[r-x.s2][x.f1]);
	//cout<<r-l+1<<" "<<x.f1<<" "<<dp[r-l+1][x.f1]<<" "<<dp[x.s2-l][x.f1]<<" "<<dp[r-x.s2][x.f1]<<endl;
	//cout<<ans<<endl;
	return ans;
}
int32_t main(){
	//fri("in.txt");
	//fro("out.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	calctable();
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			cin>>grid[i][j];
			if(grid[i][j]=='#'){
				hist[j]=0;
			}
			else hist[j]++;
			//cout<<grid[i][j]<<endl;
			//cout<<hist[j]<<" ";
		}
		//cout<<endl;
		build();
		//cout<<st[2][1].s2<<endl;
		ans+=solve(1,m);
	}
	cout<<ans<<endl;
	return 0;
}

• 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: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11