cpp_library

競技プログラミングのライブラリ

This project is maintained by tsutaj

:warning: algorithm/verify/verify_algo_003_2D_accumulation.cpp

Back to top page

Depends on

Code

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cassert>
using namespace std;
#include "../algo_003_2D_accumulation.cpp"

void ARC025_B() {
    int H, W; cin >> H >> W;
    vector< vector<int> > mat(H, vector<int>(W));

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            int val; cin >> val;
            if((i + j) % 2) mat[i][j] += val;
            else mat[i][j] -= val;
        }
    }

    Accumulation2D<int> acc(mat, 0,
                            [](int a, int b) { return a + b; },
                            [](int a, int b) { return a - b; });

    int ans = 0;
    for(int lx=0; lx<H; lx++) {
        for(int rx=lx+1; rx<=H; rx++) {
            for(int ly=0; ly<W; ly++) {
                for(int ry=ly+1; ry<=W; ry++) {
                    if(acc.range_val(lx, ly, rx, ry) == 0) {
                        int cand = (rx - lx) * (ry - ly);
                        ans = max(ans, cand);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

void ARC025_B_alter() {
    int H, W; cin >> H >> W;
    Accumulation2D<int> acc(H, W, 0,
                            [](int a, int b) { return a + b; },
                            [](int a, int b) { return a - b; });

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            int val; cin >> val;
            if((i + j) % 2) acc.range_add(i, j, i+1, j+1, val);
            else acc.range_add(i, j, i+1, j+1, -val);
        }
    }
    acc.build(); // imos
    acc.build(); // accumulation

    int ans = 0;
    for(int lx=0; lx<H; lx++) {
        for(int rx=lx+1; rx<=H; rx++) {
            for(int ly=0; ly<W; ly++) {
                for(int ry=ly+1; ry<=W; ry++) {
                    if(acc.range_val(lx, ly, rx, ry) == 0) {
                        int cand = (rx - lx) * (ry - ly);
                        ans = max(ans, cand);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
    // ARC025_B();
    ARC025_B_alter();
    return 0;
}

#line 1 "algorithm/verify/verify_algo_003_2D_accumulation.cpp"
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cassert>
using namespace std;
#line 1 "algorithm/verify/../algo_003_2D_accumulation.cpp"
// 二次元累積演算 (0-indexed)
// 単位元と二項演算・その逆演算を与える
// 二次元 imos にも対応

template <typename MonoidType>
struct Accumulation2D {
    // 持つ矩形領域のサイズ
    // 縦横とも、acc はこれより 2 大きくしておく
    int n, m;
    MonoidType E;
    vector< vector<MonoidType> > acc;
    using MMtoM = function< MonoidType(MonoidType, MonoidType) >;
    MMtoM op, rop;

    void build() {
        for(int i=0; i<=n; i++) {
            for(int j=0; j<m; j++) {
                acc[i][j+1] = op(acc[i][j+1], acc[i][j]);
            }
        }
        for(int j=0; j<=m; j++) {
            for(int i=0; i<n; i++) {
                acc[i+1][j] = op(acc[i+1][j], acc[i][j]);
            }
        }
    }

    Accumulation2D() {}
    Accumulation2D(int n_, int m_, int E_, MMtoM op_, MMtoM rop_) :
        n(n_), m(m_), E(E_), acc(n_+2, vector<MonoidType>(m_+2, E_)),
        op(op_), rop(rop_) {}
    Accumulation2D(vector< vector<MonoidType> > mat, int E_,
                   MMtoM op_, MMtoM rop_,
                   bool need_build = true) :
        E(E_), op(op_), rop(rop_) {
        assert(mat.size() > 0);
        n = mat.size(), m = mat[0].size();
        acc = vector< vector<MonoidType> >(n+2, vector<MonoidType>(m+2, E_));
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                acc[i+1][j+1] = mat[i][j];
            }
        }
        if(need_build) build();
    }

    // [lx, rx), [ly, ry) の矩形領域に val を適用
    void range_add(int lx, int ly, int rx, int ry, MonoidType val) {
        if(lx < 0 or ly < 0 or rx > n or ry > m) return;
        lx++, ly++; rx++; ry++;
        acc[lx][ly] = op(acc[lx][ly], val);
        acc[rx][ry] = op(acc[rx][ry], val);
        acc[lx][ry] = rop(acc[lx][ry], val);
        acc[rx][ly] = rop(acc[rx][ly], val);
    }

    // [lx, rx), [ly, ry) の矩形領域の値
    MonoidType range_val(int lx, int ly, int rx, int ry) {
        if(lx < 0 or ly < 0 or rx > n or ry > m) return E;
        MonoidType res = E;
        res = op(res, acc[lx][ly]);
        res = op(res, acc[rx][ry]);
        res = rop(res, acc[lx][ry]);
        res = rop(res, acc[rx][ly]);
        return res;
    }
};
#line 8 "algorithm/verify/verify_algo_003_2D_accumulation.cpp"

void ARC025_B() {
    int H, W; cin >> H >> W;
    vector< vector<int> > mat(H, vector<int>(W));

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            int val; cin >> val;
            if((i + j) % 2) mat[i][j] += val;
            else mat[i][j] -= val;
        }
    }

    Accumulation2D<int> acc(mat, 0,
                            [](int a, int b) { return a + b; },
                            [](int a, int b) { return a - b; });

    int ans = 0;
    for(int lx=0; lx<H; lx++) {
        for(int rx=lx+1; rx<=H; rx++) {
            for(int ly=0; ly<W; ly++) {
                for(int ry=ly+1; ry<=W; ry++) {
                    if(acc.range_val(lx, ly, rx, ry) == 0) {
                        int cand = (rx - lx) * (ry - ly);
                        ans = max(ans, cand);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

void ARC025_B_alter() {
    int H, W; cin >> H >> W;
    Accumulation2D<int> acc(H, W, 0,
                            [](int a, int b) { return a + b; },
                            [](int a, int b) { return a - b; });

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            int val; cin >> val;
            if((i + j) % 2) acc.range_add(i, j, i+1, j+1, val);
            else acc.range_add(i, j, i+1, j+1, -val);
        }
    }
    acc.build(); // imos
    acc.build(); // accumulation

    int ans = 0;
    for(int lx=0; lx<H; lx++) {
        for(int rx=lx+1; rx<=H; rx++) {
            for(int ly=0; ly<W; ly++) {
                for(int ry=ly+1; ry<=W; ry++) {
                    if(acc.range_val(lx, ly, rx, ry) == 0) {
                        int cand = (rx - lx) * (ry - ly);
                        ans = max(ans, cand);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
    // ARC025_B();
    ARC025_B_alter();
    return 0;
}

Back to top page