oj.uz

Submission #85195

# Submission time Handle Problem Language Result Execution time Memory
85195 2018-11-18T22:08:08 Z kraljlavova1 Strah (COCI18_strah) C++11
110 / 110
 517 ms 53812 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3064 KB Output is correct
2 Correct 9 ms 3184 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3292 KB Output is correct
2 Correct 10 ms 3400 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3688 KB Output is correct
2 Correct 13 ms 3688 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 15412 KB Output is correct
2 Correct 252 ms 31352 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 31352 KB Output is correct
2 Correct 415 ms 44836 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 44836 KB Output is correct
2 Correct 286 ms 44836 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 44836 KB Output is correct
2 Correct 376 ms 51028 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 53720 KB Output is correct
2 Correct 377 ms 53812 KB Output is correct