Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #define N 1111
- using namespace std;
- int up[N][N],left[N][N],down[N][N],right[N][N],l[N],r[N],n,m,ptr,mink,ans,kol;
- char c[N][N];
- int s[N];
- pair<int,int> times[N];
- inline int prev(int x){
- return x&(x-1);
- }
- inline int next(int x){
- return (x<<1)-(x&(x-1));
- }
- inline void modify(int pos,int value){
- for (;pos<N;pos=next(pos)) s[pos]+=value;
- }
- inline int get_sum(int l,int r){
- if (l>r) return 0;
- int k=0,p;
- for (p=r;p>0;p=prev(p)) k+=s[p];
- for (p=l-1;p>0;p=prev(p)) k-=s[p];
- return k;
- }
- inline void input(){
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- scanf("%d%d%d\n",&n,&m,&mink);
- mink=mink%4?mink/4+2:mink/4+1;
- for (int i=1;i<=n;i++){
- for (int j=1;j<=m;j++) scanf("%c",&c[i][j]);
- scanf("\n");
- }
- }
- inline void init(){
- for (int i=1;i<=n;i++)
- for (int j=1;j<=m;j++){
- up[i][j]=c[i][j]=='#'?0:up[i-1][j]+1;
- left[i][j]=c[i][j]=='#'?0:left[i][j-1]+1;
- }
- for (int i=n;i>=1;i--)
- for (int j=m;j>=1;j--){
- down[i][j]=c[i][j]=='#'?0:down[i+1][j]+1;
- right[i][j]=c[i][j]=='#'?0:right[i][j+1]+1;
- }
- }
- inline void upd_ans(){
- memset(s,0,sizeof(s));
- kol=0;
- for (int i=1;i<=ptr;i++){
- if (l[i]>=mink){
- modify(i,1);
- times[++kol]=make_pair(l[i]+i-1,i);
- }
- }
- sort(times+1,times+kol+1);
- int f=1;
- for (int i=1;i<=ptr;i++){
- ans+=get_sum(i-r[i]+1,i-mink+1);
- while (times[f].first==i && f<=kol){
- modify(times[f].second,-1);
- ++f;
- }
- }
- }
- int main(){
- input();
- init();
- for (int I=1;I<=n;I++){
- ptr=0;
- for (int i=I,j=1;i<=n && j<=m;i++,j++){
- l[++ptr]=min(right[i][j],down[i][j]);
- r[ptr]=min(left[i][j],up[i][j]);
- }
- upd_ans();
- }
- for (int I=2;I<=m;I++){
- ptr=0;
- for (int i=1,j=I;i<=n && j<=m;i++,j++){
- l[++ptr]=min(right[i][j],down[i][j]);
- r[ptr]=min(left[i][j],up[i][j]);
- }
- upd_ans();
- }
- printf("%d",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement