tests/AtCoder/ABC_224_B_monge_checker.cpp

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Link: https://atcoder.jp/contests/abc224/tasks/abc224_b

Depends on

• Monge 性・anti-Monge 性の判定 (in O(HW)) (Optimization/monge_checker.hpp)
• STL コンテナの io ストリーム (vector, set など)] (Others/stl_container_stream.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc224/tasks/abc224_b"

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

#include "stl_container_stream.hpp"
#include "monge_checker.hpp"

int main() {
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0LL));
    cin >> A;
    auto f = [&](int i, int j) -> long long { return A[i][j]; };
    Yes(is_monge(H, W, f, false, false));
}

#line 1 "tests/AtCoder/ABC_224_B_monge_checker.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc224/tasks/abc224_b"

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

#line 3 "Others/stl_container_stream.hpp"
using namespace std;

// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }

// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }

// Yes/No
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
#line 4 "Optimization/monge_checker.hpp"
using namespace std;

// check whether N x M matrix f is Monge or not, in O(NM)
template<class FUNC> bool is_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 > f10 + f01) {
                if (output_detail) {
                    cout << "Not Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}

// check whether N x M matrix f is anti-Monge or not, in O(NM)
template<class FUNC> bool is_anti_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 < f10 + f01) {
                if (output_detail) {
                    cout << "Not anti-Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}
#line 8 "tests/AtCoder/ABC_224_B_monge_checker.cpp"

int main() {
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0LL));
    cin >> A;
    auto f = [&](int i, int j) -> long long { return A[i][j]; };
    Yes(is_monge(H, W, f, false, false));
}

Back to top page