Submission #756612

#	Time	Username	Problem	Language	Result	Execution time	Memory
756612		pcc	Strah (COCI18_strah)	C++14	110 / 110	306 ms	35988 KiB

strah

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

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 2020;
ll arr[mxn][mxn];
ll ans = 0;
int n,m;
int dsu[mxn],sz[mxn],lef[mxn],rig[mxn];
ll dp[mxn];
ll tag = 0;

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
	a = root(a),b= root(b);
	if(a == b)return;
	tag = tag-dp[rig[a]-lef[a]+1];
	tag = tag-dp[rig[b]-lef[b]+1];
	if(sz[b]>sz[a])swap(a,b);
	dsu[b] = a;
	sz[a] += sz[b];
	lef[a] = min(lef[a],lef[b]);
	rig[a] = max(rig[a],rig[b]);
	tag = tag+dp[rig[a]-lef[a]+1];
}

void calc(int id){
	vector<int> v[mxn];
	tag = 0;
	for(int i = 1;i<=m;i++){
		v[arr[id][i]].push_back(i);
	}
	for(int i = 1;i<=m;i++){
		lef[i] = rig[i] = i;
		dsu[i] = i;
		sz[i] = 1;
	}
	for(int i = mxn-1;i>=1;i--){
		for(auto &j:v[i]){
			tag++;
			if(arr[id][j-1] >= i)onion(j-1,j);
			if(arr[id][j+1] >= i)onion(j,j+1);
			//cout<<j<<','<<i<<','<<lef[root(j)]<<' '<<rig[root(j)]<<endl;
		}
		ans += tag*i;
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)arr[i][0] = -1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			char c;
			cin>>c;
			if(c == '#')arr[i][j] = 0;
			else arr[i][j] = arr[i-1][j]+1;
		}
	}
	dp[1] = 1;
	ll tmp = 1;
	for(int i = 2;i<mxn;i++){
		tmp += i;
		dp[i] = dp[i-1]+tmp;
	}
	//for(int i = 1;i<10;i++)cout<<dp[i]<<' ';cout<<endl;
	for(int i = 1;i<=n;i++){
		calc(i);
		//cout<<i<<":"<<ans<<','<<endl;
	}
	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: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11