Submission #85195

#	Time	Username	Problem	Language	Result	Execution time	Memory
85195		kraljlavova1	Strah (COCI18_strah)	C++11	110 / 110	517 ms	53812 KiB

strah

#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
const int MAXN=2010;
llint n,m;
llint l[MAXN][MAXN];
llint sol;
char P[MAXN][MAXN];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>P[i];
	for(int i=0;i<n;i++){
		if(P[i][0]=='.') l[i][0]=1;
		for(int j=1;j<m;j++){
			if(P[i][j]=='#') l[i][j]=0;
			else l[i][j]=l[i][j-1]+1;
		}
	}
	for(int j=0;j<m;j++){
		vector<pair<llint,llint> >st;
		for(llint i=0;i<n;i++){
			if(P[i][j]=='#'){
				st.clear();
				continue;
			}
			// r=i,t=l[i][j];
			/*
			while(r>=0&&P[r][j]=='.'){
				t=min(t,l[r][j]);
				sol+=(i-r+1)*t*(t+1)/2;
				r--;
			}
			*/
			if(st.empty()){
				st.push_back({l[i][j],1});
			}
			else{
				llint sum=0;
				while(!st.empty()&&st.back().first>l[i][j]){
					sum+=st.back().second;
					st.pop_back();
				}
				//cout<<i<<" "<<j<<" "<<sum<<"\n";
				if(st.empty()) st.push_back({l[i][j],1+sum});
				else{
					if(st.back().first==l[i][j]) (st.back()).second+=1+sum;
					else st.push_back({l[i][j],1+sum});
				}
			}
			//cout<<"tu "<<i<<" "<<j<<" "<<st.size()<<"\n";
			llint s=0,x=0;
			for(int k=st.size()-1;k>=0;k--){
				s=x;
				llint w=st[k].first;
				x+=st[k].second;
				//cout<<i<<" "<<j<<" "<<w<<" "<<x<<" "<<s<<"\n";
				sol+=(x*(x+1)/2-s*(s+1)/2)*w*(w+1)/2;
			}
		}
	}
	cout<<sol<<"\n";
	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