oj.uz

Submission #166948

# Submission time Handle Problem Language Result Execution time Memory
166948 2019-12-04T19:25:16 Z muhi1112 Strah (COCI18_strah) C++17
44 / 110
 444 ms 24216 KB 
#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 int N=2e3+5;
const int K=20;

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

int calc(int i,int j){
	return ((i*(i+1)*j*(j+1))/4);
}
void calctable(){
	for(int i=1;i<N;i++){
		for(int j=1;j<N;j++){
			dp[i][j]=dp[i-1][j]+calc(i,j);
		}
	}
}
void build(){
	for(int i=1;i<=m;i++){
		st[i][0]={hist[i],i};
	}
	for(int j=1;j<K;j++){
		for(int i=1;i+(1<<j)<=N;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
pair<int,int> qmin(int l,int r){
	int j=log2(r-l+1);
	return min(st[l][j],st[r-(1<<j)+1][j]);
}
int solve(int l,int 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<int,int> x=qmin(l,r);
	//cout<<l<<" "<<r<<" "<<x.f1<<" "<<x.s2<<endl;
	int ans=0;
	int left=solve(l,x.s2-1);
	int 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;
}
int main(){
	//fri("in.txt");
	//fro("out.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	calctable();
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int 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.0 / 11.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16376 KB Output is correct
2 Correct 21 ms 16376 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 17016 KB Output is correct
2 Correct 49 ms 17016 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 17016 KB Output is correct
2 Correct 50 ms 17144 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 17116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 19032 KB Output is correct
2 Incorrect 322 ms 21648 KB Output isn't correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 21484 KB Output is correct
2 Incorrect 444 ms 23752 KB Output isn't correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 19576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 20248 KB Output is correct
2 Incorrect 360 ms 22948 KB Output isn't correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 444 ms 24216 KB Output isn't correct
2 Halted 0 ms 0 KB -