Submission #589822

#	Time	Username	Problem	Language	Result	Execution time	Memory
589822		FedShat	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	320 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
using ll = long long;
constexpr int INF = (numeric_limits<int>::max()) / 2;
constexpr ll INFLL = (numeric_limits<ll>::max()) / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i: a) {
        is >> i;
    }
    return is;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(all(v), [&](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second || (a.second == b.second && a.first < b.first);
    });
    vector<int> r(m);
    cin >> r;
    sort(all(r));
    vector<pair<int, int>> dp(n);
    for (int i = 0; i < n; ++i) {
        int it = lower_bound(all(r), v[i].first) - r.begin();
        if (it != (int) r.size()) {
            dp[i] = {1, it};
        }
        for (int j = 0; j < i; ++j) {
            auto [dpp, jj] = dp[j];
            int jjj = lower_bound(jj + 1 + all(r), v[i].first) - r.begin();
            if (jjj != (int) r.size()) {
                if (dp[i].first < dpp + 1 || (dp[i].first == dpp + 1 && jjj < dp[i].second)) {
                    dp[i].first = dpp + 1;
                    dp[i].second = jjj;
                }
            }
        }
    }
    cout << max_element(all(dp))->first;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50