結果
問題 | No.1479 Matrix Eraser |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:30:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 319 ms / 3,000 ms |
コード長 | 2,978 bytes |
コンパイル時間 | 2,490 ms |
コンパイル使用メモリ | 214,892 KB |
最終ジャッジ日時 | 2025-01-20 20:13:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <atcoder/maxflow>#include <bits/stdc++.h>using namespace std;using namespace atcoder;const long long INF_LL = 2000000000000000000LL;const int INF = 2000000000;const long long MOD = 1000000007;#define ll long long#define all(x) x.begin(), x.end()#define REP(i, a, b) for(int i = a; i < b; i++)#define rep(i, n) REP(i, 0, n)// typedef float double;// typedef priority_queue prique;typedef pair<ll, ll> P;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<P> vp;typedef vector<ll> vl;typedef vector<vi> matrix;int dx[4] = {0, -1, 0, 1};int dy[4] = {1, 0, -1, 0};int sign[2] = {1, -1};template <class T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}template <class T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}ll modpow(ll a, ll b, ll m) {if(b == 0)return 1;ll t = modpow(a, b / 2, m);if(b & 1) {return (t * t % m) * a % m;} else {return t * t % m;}}struct edge {int to;ll cost;edge(int t, ll c) { to = t, cost = c; }};typedef vector<vector<edge>> graph;// using mint = modint998244353;int main(){int h, w;cin >> h >> w;vector<vector<int>> a(h, vector<int>(w));rep(i, h) rep(j, w) cin >> a[i][j];vector<vector<pair<int, int>>> t(500000);rep(i, h){rep(j, w){if(a[i][j] > 0) {t[a[i][j] - 1].push_back({i, j});}}}int ans = 0;for(int i = 499999; i >= 0; i--){if(t[i].size() > 0){int tmp1;sort(all(t[i]));int tmp = t[i][0].first;t[i][0].first = 0;rep(j, t[i].size() - 1){if(tmp < t[i][j + 1].first){tmp = t[i][j + 1].first;t[i][j + 1].first = t[i][j].first + 1;}else{t[i][j + 1].first = t[i][j].first;}}tmp1 = t[i][t[i].size()-1].first + 1;int tmp2;sort(all(t[i]), [](auto x, auto y){return x.second < y.second;});tmp = t[i][0].second;t[i][0].second = 0;rep(j, t[i].size() - 1){if(tmp < t[i][j + 1].second){tmp = t[i][j + 1].second;t[i][j + 1].second = t[i][j].second + 1;}else{t[i][j + 1].second = t[i][j].second;}}tmp2 = t[i][t[i].size()-1].second + 1;mf_graph<int> g(tmp1 + tmp2 + 2);rep(j, tmp1) g.add_edge(tmp1 + tmp2, j, 1);rep(j, tmp2) g.add_edge(j + tmp1, tmp1 + tmp2 + 1, 1);rep(j, t[i].size()){g.add_edge(t[i][j].first, t[i][j].second + tmp1, 1);}ans += g.flow(tmp1 + tmp2, tmp1 + tmp2 + 1);}}cout << ans << endl;}