Submission #2602964

---

Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
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;

#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))

vi www(vi& a, int w) {
    int wo = a.size(), d = w - wo + 1;
//    a.assign(w, 0);
    a.resize(w);
    int z = 0;
    vi b(w);
    rep(i, w){
        if (i < wo)
            z += a[i];
        if (i-d >= 0)
            z -= a[i-d];
        b[i] = z;
    }
    return b;
}

vvi transpose(vvi& x){
    int R=x.size(), C=x[0].size();
    vvi y(C, vi(R, 0));
    rep(r,R) rep(c,C){
        y[c][r] = x[r][c];
    }
    return y;
}

void _pp(vvi& a) {
#ifdef DEBUG
    rep(i, a.size()) {
        cout << i << " " << a[i] << endl;
    }
    cout << endl;
#endif
}

void bin(vvi& a){
    int h = a.size(), w = a[0].size();
    rep(r,h) rep(c,w) {
        if (a[r][c]) a[r][c] = 1;
    }
}

ll solve(int H,int W, int N, int M, vector<string>& _a) {
    vvi a(N, vi(M, 0));
    rep(r,N){
        rep(c,M){
            a[r][c] = (_a[r][c] == '#') ? 1 : 0;
        }
    }

    _pp(a);

    int _w = min(W, M*2-1);
    vvi ay(N);
    // 横ひきぼなし
    rep(r,N){
        ay[r] = www(a[r], _w);
    }
    bin(ay);
    _pp(ay);

    int _h = min(H, N*2-1);
    vvi ya = transpose(ay);
    vvi ta(_w);
    // 縦ひきのばし
    rep(r,_w){
        ta[r] = www(ya[r], _h);
    }
    vvi at = transpose(ta);

    bin(at);
    _pp(at);

    ll ans = 0;
    rep(r,_h) rep(c,_w) {
        ans += at[r][c];
    }

    ll rline=0, cline = 0;
    int rmid = _h/2;
    rep(i,_w) rline += at[rmid][i];
    int cmid = _w/2;
    rep(i,_h) cline += at[i][cmid];

    //printf(" ans pure = %lld\n", ans);
    if (H > _h) {
        ans += rline * (H - _h);
        //printf(" ans +1 = %lld x %d\n", rline, H-_h);
        if (W <= _w) {
        } else {
            ans += cline * (W - _w);
            //printf(" ans +2 = %lld x %d\n", cline, W-_w);
            ans += (ll)(H - _h)*(W - _w)*at[rmid][cmid];
            //printf(" ans +3 = %d x %d x %d\n", H-_h, W-_w, at[rmid][cmid]);
        }
    } else {
        if (W <= _w) {
            ;
        }  else {
            ans += cline * (W - _w);
            //printf(" ans +2 = %lld x %d\n", cline, W-_w);
        }
    }

    return ans;
}

int main() {
    int H,W, N,M;
    cin >> H >> W;
    cin >> N >> M;
    vector<string> a(N);
    rep(i,N) cin>>a[i];
    cout << solve(H,W,N,M,a) << endl;
    return 0;
}

Submission Info

Judge Result