Submission #3595348

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ll> llll;
typedef pair<double, double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a) int((a).size())
#define pb push_back
#define FOR(var, from, to) for (int var = (from); var <= (to); ++var)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define rep1(var, n) for (int var = 1; var <= (n); ++var)
#define repC2(vari, varj, n)                 \
    for (int vari = 0; vari < (n)-1; ++vari) \
        for (int varj = vari + 1; varj < (n); ++varj)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define tr(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define found(s, e) ((s).find(e) != (s).end())
#define mset(arr, val) memset(arr, val, sizeof(arr))
#define mid(x, y) ((x) + ((y) - (x)) / 2)
#define IN(x, a, b) ((a) <= (x) && (x) <= (b))
#define cons make_pair

ll gcd(ll a, ll b) {
    while (a) swap(a, b %= a);
    return b;
}

const ll MOD = 1000000007LL;

ll ADD(ll x, ll y) { return (x + y) % MOD; }
ll SUB(ll x, ll y) { return (x - y + MOD) % MOD; }
ll MUL(ll x, ll y) { return x * y % MOD; }
ll POW(ll x, ll e) {
    ll v = 1;
    for (; e; x = MUL(x, x), e >>= 1)
        if (e & 1) v = MUL(v, x);
    return v;
}
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/
    return MUL(x, POW(y, MOD - 2));
}

vi accum(vi& a) {
    int L = a.size();
    vi aA(L + 1, 0);
    rep(i, L) aA[i + 1] = aA[i] + a[i];
    return aA;
}

int accumed(vi& accum, int from, int to) {
    int M = accum.size() - 1;
    return accum[min(M, to)] - accum[max(0, from)];
}

void see(vvi& a, FILE* fp) {
    int R = a.size(), C = a[0].size();
    fprintf(fp, "# see(%d, %d)...\n", R, C);
    assert(R <= 300 && C <= 300);
    rep(r, R) {
        rep(c, C) { fputc(a[r][c] ? '#' : '.', fp); }
        fputc('\n', fp);
    }
}

ll solve(int H, int W, vector<string>& s) {
    int L = H + W - 1;
    vvi up(L, vi(W)), down(L, vi(W));
    rep(r, L) rep(c, W) {
        up[r][c] = IN(r - c, 0, H - 1) ? (s[r - c][c] == '#') : 0;
        down[r][W-1-c] = IN(r - c, 0, H - 1) ? (s[r-c][W-1-c] == '#') : 0;
    }
    vvi upA(L), downA(L);
    rep(r, L) {
        upA[r] = accum(up[r]);
        downA[r] = accum(down[r]);
    }

    ll ans = 0, double_counted = 0;

    rep(r, L) {
        repC2(i, j, W) {
            if (up[r][i] && up[r][j]) {
                int d = j - i;
                int above = r-2*d;
                if (0 <= above) {
                    ans += accumed(upA[above], i-d, i+1);
                    if (IN(i-d, 0, W-1) && up[above][i-d]) ++double_counted;
                    if (IN(i, 0, W-1) && up[above][i]) ++double_counted;
                }
                int below = r+2*d;
                if (below < L) {
                    ans += accumed(upA[below], j, j+d+1);
                    if (IN(j, 0, W-1) && up[below][j]) ++double_counted;
                    if (IN(j+d, 0, W-1) && up[below][j+d]) ++double_counted;
                }
            }
        }
    }


    rep(r, L) {
        repC2(i, j, W) {
            if (down[r][i] && down[r][j]) {
                int d = j - i;
                int above = r - 2*d;
                if (0 <= above) {
                    ans += accumed(downA[above], j, j+d+1);
                    if (IN(j, 0, W-1) && down[above][j]) ++double_counted;
                    if (IN(j+d, 0, W-1) && down[above][j+d]) ++double_counted;
                }
                int below = r + 2*d;
                if (below < L) {
                    ans += accumed(downA[below], i-d, i+1);
                    if (IN(i-d, 0, W-1) && down[below][i-d]) ++double_counted;
                    if (IN(i, 0, W-1) && down[below][i]) ++double_counted;
                }
            }
        }
    }
    return ans - double_counted/2;
}

vector<string> transpose(vector<string>& m) {
    int R = m.size(), C = m[0].size();
    vector<string> mT(C);
    rep(i, C) {
        vector<char> row(R);
        rep(j, R) row[j] = m[j][i];
        mT[i] = string(ALL(row));
    }
    return mT;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    rep(i, H) cin >> s[i];

    if (H < W) {
        s = transpose(s);
        swap(H, W);
    }
    cout << solve(H, W, s) << endl;

    return 0;
}

Submission Info

Judge Result