Cod sursă (job #228760)

#include <cstdio>
#include <cstring>

FILE* in=fopen("ssdj.in","r");
FILE* out=fopen("ssdj.out","w");

const int Q=1007;

int n;

char v[Q][Q];

char a[Q][Q];
short int up[Q][Q];
int rez=0;

void roller()
{
    int uper;
    int frm=n+1;

    for(int i=2; i<=n; i++)
    {
        int j=n;

        while(j>0 && a[i][j]==0)
            j--;

        for(; j>0; j--)
        {
            if(a[i][j]!=0)
            {
                frm=j;
                uper=up[i][j];
            }
            else
            {
                if(up[i][j]<uper)
                {
                    uper=up[i][j];
                    if(a[i-up[i][j]-1][j]==1 || a[i][frm]==1)
                        rez++;
                }
            }
        }
    }
}

void main2()
{

    for(int k='b'; k<='z'; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(v[i][j]<k)
                    a[i][j]=0;
                if(v[i][j]==k)
                    a[i][j]=1;
                if(v[i][j]>k)
                    a[i][j]=2;
            }
        }

        for(int j=1; j<=n; j++)
        {
            for(int i=2; i<=n; i++)
            {
                if(a[i-1][j]==0)
                    up[i][j]=up[i-1][j]+1;
            }
        }

        roller();
    }

    fprintf(out,"%d\n",rez);

}


int main()
{
    fscanf(in,"%d\n",&n);

    for(int i=1; i<=n; i++)
    {
        fread(v[i]+1,n,1,in);
        fscanf(in,"\n");
    }

    main2();


    return 0;
}