Codeforces Round #153 Table with Letters - 2

Problem Statement

You are given a rectangular of the size (n, m), at each cell of which an English lower-letter is located. Count the number of rectangulars in the original rectangular that satisfy the both of the following conditions:
1. The number of 'a' in the rectangle is less than k.
2. All the letters located at the four corners are the same.

Approach

First I tried a stupid bruteforce solution, which failed as I expected. Then an approach that uses binary search algorithm came to my mind, and I tried it. Failed again... It was very close, but I got a TLE. I thought through a proper approach, but it didn't hit me unfortunately. So I peeked someone's solution, and it seemed like he used a technique what you call "two-poiter" -- guess it's called "しゃくとり法" in Japanese --. Good thing that I found the solution, otherwise I would sleep on it :p

Source Code

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

int n, m, k;
string bd[400];
int ac[400][400+1];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n >> m >> k;
    REP (i, n) 
        cin >> bd[i];

    REP (i, n) REP (j, m) ac[i][j+1] = ac[i][j] + (bd[i][j] == 'a');

    long long ret = 0;
    REP (q1, m) FOR (q2, q1+1, m) {
        int atot = 0;
        int cnt[26] = {0};

        for (int p1 = 0, p2 = 0; p2 < n; p2++) {
            atot += ac[p2][q2+1] - ac[p2][q1];
            if (bd[p2][q1] != bd[p2][q2])
                continue;
            int c = bd[p2][q1]-'a'; 
            ++cnt[c];    
            while(atot > k && p1 < p2) {
                atot -= ac[p1][q2+1] - ac[p1][q1];
                if (bd[p1][q1] == bd[p1][q2])
                    --cnt[bd[p1][q1]-'a'];
                ++p1;
            }

            if (atot <= k)
                ret += max(0, cnt[c]-1);
        }
    }

    cout << ret << endl;

    return 0;
}