結果
問題 | No.2573 moving up |
ユーザー |
![]() |
提出日時 | 2023-11-30 03:35:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 949 bytes |
コンパイル時間 | 6,500 ms |
コンパイル使用メモリ | 334,068 KB |
実行使用メモリ | 7,248 KB |
最終ジャッジ日時 | 2025-06-20 10:23:49 |
合計ジャッジ時間 | 7,941 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; int main() { int h, w; cin >> h >> w; vector<int> x(w), y(w); for(int i = 0; i < w; i++) { cin >> x[i] >> y[i]; x[i]--; y[i]--; } mcf_graph<int, int> g(2 * w + 2); int s = 2 * w; int t = 2 * w + 1; for(int i = 0; i < w; i++) { for(int j = 0; j < w; j++) { if(y[i] - x[i] <= j && j <= y[i]) { g.add_edge(i, j + w, 1, 0); } else if(y[i] - x[i] > j) { g.add_edge(i, j + w, 1, y[i] - x[i] - j); } else { g.add_edge(i, j + w, 1, j - y[i]); } } } for(int i = 0; i < w; i++) { g.add_edge(s, i, 1, 0); g.add_edge(i + w, t, 1, 0); } int ans = g.flow(s, t, w).second; for(int i = 0; i < w; i++) { ans += x[i]; } cout << ans << endl; }