結果
問題 | No.1703 Much Matching |
ユーザー |
|
提出日時 | 2021-10-08 22:15:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 387 ms / 2,000 ms |
コード長 | 2,908 bytes |
コンパイル時間 | 2,338 ms |
コンパイル使用メモリ | 202,948 KB |
最終ジャッジ日時 | 2025-01-24 22:23:52 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;const int MOD = 1000000007;// const int MOD = 998244353;int main() {int N, M, Q;cin >> N >> M >> Q;vector<vector<int>> e1(N), e2(M);rep(i, Q) {int u, v;cin >> u >> v;u--, v--;e1[u].eb(v), e2[v].eb(u);}rep(i, N) sort(all(e1[i]));rep(i, M) sort(all(e2[i]));vector<vector<int>> dp(N + 1, vector<int>(M + 1, -inf));dp[0][0] = 0;rep(i, N + 1) {rep(j, M + 1) {if (i < N) {chmax(dp[i + 1][j], dp[i][j]);auto it = lower_bound(all(e1[i]), j);if (it != end(e1[i])) chmax(dp[i + 1][*it + 1], dp[i][j] + 1);}if (j < M) {chmax(dp[i][j + 1], dp[i][j]);auto it = lower_bound(all(e2[j]), i);if (it != end(e2[j])) chmax(dp[*it + 1][j + 1], dp[i][j] + 1);}}}cout << dp[N][M] << '\n';}