Codeforces Round #219 (Div. 1) B - Counting Rectangles is Fun

#include<stdio.h>
#include<string.h>
int is[45][45][45][45]={0},add[45][45][45][45]={0},u[45][45][45][45]={0};
char s[45][45];
int main(){
    int n,m,q,i,j,x,y,k,a,b,c,d,l,r,ans;
    memset(u,-1,sizeof(u));
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=n;i++)
        scanf("%s",&s[i][1]);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){
        if(s[i][j]=='0'){
            is[i][j][0][0]=1;
            for(x=0;x<i;x++)
            for(y=0;y<j;y++){
                if(!x && !y) continue;
                if(x && !y) is[i][j][x][y]=is[i-1][j][x-1][y];
                if(!x && y) is[i][j][x][y]=is[i][j-1][x][y-1];
                if(x && y) is[i][j][x][y]=is[i][j-1][x][y-1] && is[i-1][j][x-1][y];
            }
        }
    }

    for(x=0;x<i;x++)
    for(y=0;y<j;y++)
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){
        add[i][j][x][y]=is[i][j][x][y]+add[i-1][j][x][y]+add[i][j-1][x][y]-add[i-1][j-1][x][y];
    }
    for(i=0;i<q;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(u[a][b][c][d]!=-1){
            printf("%d\n",u[a][b][c][d]);
            continue;
        }
        l=c-a,r=d-b;
        ans=0;
        for(x=0;x<=l;x++)
        for(y=0;y<=r;y++){
            ans+=add[c][d][x][y]-add[a-1+x][d][x][y]-add[c][b-1+y][x][y]+add[a-1+x][b-1+y][x][y];
        }
        printf("%d\n",ans);
        u[a][b][c][d]=ans;
    }

}