Submission #2602620

---

Source Code Expand

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

constexpr size_t sz = 1010;
long long int H, W, N, M, an, A[sz][sz], B[sz][sz], R[sz], C[sz], sid[4][sz], S;
char s[1011];

long long int access(long long int idx, long long int idy, long long int a[sz][sz]){
    idx = min(max(0LL, idx), N + 1);
    idy = min(max(0LL, idy), M + 1);
    return a[idx][idy];
}

long long int access(long long int idx, long long int mx, long long int a[sz]){
    idx = min(max(0LL, idx), mx + 1);
    return a[idx];
}

int main(){
    scanf("%lld%lld%lld%lld", &H, &W, &N, &M);
    fill(sid[0], sid[4], -1);
    for(int i = 0; i < N; ++i){
        scanf("%s", s);
        for(int j = 0; j < M; ++j){
            A[i + 1][j + 1] = s[j] & 1;
            R[i + 1] += s[j] & 1;
            C[j + 1] += s[j] & 1;
            S += s[j] & 1;
            if(s[j] & 1){
                sid[0][j + 1] == -1 ? sid[0][j + 1] = i : 0;
                sid[1][i + 1] == -1 ? sid[1][i + 1] = j : 0;
                sid[2][j + 1] = N - i - 1;
                sid[3][i + 1] = M - j - 1;
            }
        }
    }
    if(S == 0)return 0 & puts("0");
    for(int i = 0; i <= N + 1; ++i){
        if(sid[1][i] == -1){
            sid[1][i] = W;
            sid[3][i] = W;
        }
    }
    for(int i = 0; i <= M + 1; ++i){
        if(sid[0][i] == -1){
            sid[0][i] = H;
            sid[2][i] = H;
        }
    }
    /*
    cout << " ";
    for(int i = 1; i <= M; ++i)cout << " " << C[i];
    cout << endl;
    for(int i = 1; i <= N; ++i){
        cout << R[i];
        for(int j = 1; j <= M; ++j)cout << " " << access(i, j, A);
        cout << endl;
    }*/
    for(int i = 1; i <= N + 1; ++i){
        for(int j = 1; j <= M + 1; ++j){
            B[i][j] = access(i, j, A) - access(i - 1, j - 1, B) + access(i - 1, j, B) + access(i, j - 1, B);
        }
    }/*
    for(int i = 0; i <= N + 1; ++i){
        for(int j = 0; j <= M + 1; ++j)cout << " " << B[i][j];
        cout << endl;
    }
    for(int i = 1; i <= N; ++i){
        cout << sid[0][i] << ", " << sid[2][i] << endl;
    }
    for(int i = 1; i <= M; ++i){
        cout << sid[1][i] << ", " << sid[3][i] << endl;
    }*/

    if(H < 2 * N && W < 2 * M){
        for(int i = 1; i <= H; ++i){
            for(int j = 1; j <= W; ++j){
                an += access(i, j, B) + access(i + N - H - 1, j + M - W - 1, B) > access(i + N - H - 1, j, B) + access(i, j + M - W - 1, B);
                //cout << i << ", " << j << " : " << an << endl;
            }
        }
        cout << an << endl;
        return 0;
    }
    an = H * W;
    if(H >= 2 * N){
        if(W < 2 * M){
            for(long long int i = 1, c, d; i <= W; ++i){
                c = 1248973438;
                d = 1935847431;
                for(long long int j = 0; j < W - M + 1; ++j){
                    c = min(c, access(i - j, M, sid[0]));
                    d = min(d, access(i - j, M, sid[2]));
                }
                if(c + d == 2 * H)d = 0;
                //cout << i << " : " << c << " " << d << endl;
                an -= c + d;
            }
            cout << an << endl;
            return 0;
        }
        long long int I = 0, J = 0, K = 0, L = 0;
        for(long long int i = 1; R[i] == 0; ++i)++I;
        for(long long int i = 1; C[i] == 0; ++i)++J;
        for(long long int i = N; R[i] == 0; --i)++K;
        for(long long int i = M; C[i] == 0; --i)++L;
        //cout << I << " " << J << " " << K << " " << L << endl;
        an -= (I + K) * W + (J + L) * H - (I + K) * (J + L);
        //cout << an << endl;
        long long int c = 124588491524, d = 124958742313;
        for(long long int i = J + 1; i <= M - L; ++i){
            c = min(access(i, M, sid[0]), c);
            d = min(access(i, M, sid[2]), d);
            //cout << i << " : " << sid[0][i] << " " << c << ",  " << sid[2][i] << " " << d << " : " << an << endl;
            an -= c - I + d - K;
        }
        c = 124588491524;
        d = 124958742313;
        for(long long int i = M - L; i > J; --i){
            c = min(access(i, M, sid[0]), c);
            d = min(access(i, M, sid[2]), d);
            //cout << i << " : " << sid[0][i] << " " << c << ",  " << sid[2][i] << " " << d << " : " << an << endl;
            an -= c - I + d - K;
        }
        cout << an << endl;
        return 0;
    }
    for(long long int i = 1, c, d; i <= H; ++i){
        c = 1248973438;
        d = 1935847431;
        for(long long int j = 0; j < H - N + 1; ++j){
            c = min(c, access(i - j, N, sid[1]));
            d = min(d, access(i - j, N, sid[3]));
        }
        if(c + d == 2 * W)d = 0;
        an -= c + d;
    }
    cout << an << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:20:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld", &H, &W, &N, &M);
                                              ^
./Main.cpp:23:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s);
                       ^

Judge Result