提出 #68773155

---

ソースコード 拡げる

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<random>
#include<cassert>
using namespace std;
int N,M,K;
string S[5<<17];
const int L=2237;
int up[L];
int H[L];
int can[L];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	{
		cin>>N>>M>>K;
		for(int i=0;i<N;i++)cin>>S[i];
	}
	/*
	{
		mt19937 rng;
		N=L-1;
		M=(int)5e6/N;
		for(int i=0;i<N;i++)
		{
			S[i]=string(M,'.');
			for(int j=0;j<M;j++)if(rng()%100==0)S[i][j]='#';
		}
		K=rng()%(N*M)+1;
	}
	*/
	if(N<M)
	{//transpose
		for(int i=N;i<M;i++)S[i].resize(N);
		for(int i=0;i<N;i++)for(int j=i+1;j<M;j++)swap(S[i][j],S[j][i]);
		for(int i=0;i<N;i++)S[i].resize(N);
		swap(N,M);
	}
	for(int l=1;l<=M;l++)can[l]=K/l;
	long ans=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(S[i][j]=='#')up[j]=0;
			else up[j]++;
			const int x=up[j];
			for(int k=0;k<j;k++)H[k]=min(H[k],x);
			H[j]=x;
			for(int k=0;k<=j;k++)ans+=min(H[k],can[j-k+1]);
		}
	}
	cout<<ans<<endl;
}

提出情報

ジャッジ結果