結果
問題 | No.2573 moving up |
ユーザー |
👑 |
提出日時 | 2024-01-19 21:06:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,010 ms / 2,000 ms |
コード長 | 1,963 bytes |
コンパイル時間 | 4,621 ms |
コンパイル使用メモリ | 265,448 KB |
最終ジャッジ日時 | 2025-02-18 20:29:36 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;using namespace atcoder;typedef long long ll;typedef vector<int> vi;typedef vector<long long> vl;typedef vector<vector<int>> vvi;typedef vector<vector<long long>> vvl;typedef long double ld;typedef pair<int, int> P;ostream& operator<<(ostream& os, const modint& a) {os << a.val(); return os;}template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); returnos;}template <typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : "");return os;}int main(){int h, w;cin >> h >> w;int n = h * (h + w);mcf_graph<int, int> graph(n + 2);int sv = n;int tv = n + 1;rep(y, h) rep(x, h + w){int from = y * (h + w) + x;if(y < h - 1){int to = (y + 1) * (h + w) + x;graph.add_edge(from, to, 100, 1);graph.add_edge(to, from, 100, 1);}if(x < h + w - 1){int to = y * (h + w) + (x + 1);graph.add_edge(from, to, 100, 1);graph.add_edge(to, from, 100, 1);}if(y < h - 1 and x < h + w - 1){int to = (y + 1) * (h + w) + (x + 1);graph.add_edge(from, to, 100, 1);graph.add_edge(to, from, 100, 1);}}rep(i, w){int y, x;cin >> y >> x;x--; y--;graph.add_edge(sv, y * (h + w) + x, 1, 0);}rep(x, w){graph.add_edge(x, tv, 1, 0);}auto [cap, cost] = graph.flow(sv, tv);// cout << cap << ' ' << cost << "\n";cout << cost << "\n";return 0;}