Submission #9903532


Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;

template<typename T>
struct Imos2D {
    vector<vector<T>> imos;
    Imos2D(int h = 0, int w = 0) : imos(h + 2, vector<T>(w + 2)) { }
    void add(int i, int j, T x) { imos[i + 1][j + 1] += x; }
    void add_rect(int i1, int j1, int i2, int j2, T x = 1) {
        add(i1, j1, +x); add(i1, j2, -x); add(i2, j1, -x); add(i2, j2, +x);
    }
    void build() {
        int H = imos.size(), W = imos[0].size();
        for (int i = 1; i < H; i++) for (int j = 1; j < W; j++) {
            imos[i][j] += imos[i][j - 1] + imos[i - 1][j] - imos[i - 1][j - 1];
        }
    }
    T get(int i, int j) { return imos[i + 1][j + 1]; }
    T diff(int si, int sj, int ti, int tj) {        // [si, ti) x [sj, tj)
        return imos[ti][tj] - imos[ti][sj] - imos[si][tj] + imos[si][sj];
    }
};

int main() {
    long long h, w; cin >> h >> w;
    long long n, m; cin >> n >> m;
    vector<string> hanko(n);
    for (auto &s: hanko) cin >> s;
    int sz_h = min(h, n * 2), sz_w = min(w, m * 2);
    Imos2D<int> imos(sz_h, sz_w);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        if (hanko[i][j] != '#') continue;
        int i2 = i + (sz_h - n) + 1, j2 = j + (sz_w - m) + 1;
        imos.add_rect(i, j, i2, j2);
    }
    imos.build();
    long long ans = 0;
    for (int i = 0; i < sz_h; i++) for (int j = 0; j < sz_w; j++) {
        if (imos.get(i, j)) ans++;
    }
    int top = INF, bottom = INF, left = INF, right = INF;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        if (hanko[i][j] != '#') continue;
        top = min<int>(top, i);
        bottom = min<int>(bottom, n - 1 - i);
        left = min<int>(left, j);
        right = min<int>(right, m - 1 - j);
    }
    if (top != INF) {
        ans += (h - sz_h) * (w - left - right);
        ans += (w - sz_w) * (h - top - bottom);
        ans -= (h - sz_h) * (w - sz_w);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task D - ハンコ
User kyuna
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2073 Byte
Status AC
Exec Time 57 ms
Memory 17024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 5
AC × 28
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt AC 30 ms 7296 KB
02.txt AC 6 ms 1664 KB
03.txt AC 3 ms 512 KB
04.txt AC 36 ms 4992 KB
05.txt AC 2 ms 384 KB
06.txt AC 36 ms 5376 KB
07.txt AC 2 ms 512 KB
08.txt AC 2 ms 512 KB
09.txt AC 1 ms 256 KB
10.txt AC 16 ms 4352 KB
11.txt AC 2 ms 512 KB
12.txt AC 5 ms 1280 KB
13.txt AC 33 ms 8576 KB
14.txt AC 1 ms 256 KB
15.txt AC 2 ms 384 KB
16.txt AC 18 ms 1920 KB
17.txt AC 4 ms 640 KB
18.txt AC 4 ms 768 KB
19.txt AC 3 ms 512 KB
20.txt AC 30 ms 8576 KB
21.txt AC 3 ms 512 KB
22.txt AC 10 ms 2816 KB
23.txt AC 57 ms 17024 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB
sample-05.txt AC 1 ms 256 KB