oj.uz

Submission #589824

# Submission time Handle Problem Language Result Execution time Memory
589824 2022-07-05T10:32:17 Z FedShat Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 324 KB 
#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};
        } else {
            dp[i] = {0, r.size()};
        }
        for (int j = 0; j < i; ++j) {
            auto [dpp, jj] = dp[j];
            int jjj = lower_bound(jj + 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 + 1;
                }
            }
        }
    }
    cout << max_element(all(dp))->first;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -