oj.uz

Submission #336436

# Submission time Handle Problem Language Result Execution time Memory
336436 2020-12-15T10:28:00 Z arujbansal Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 5, INF = 1e9 + 5;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> pictures(n);
    for (auto &[val, sz] : pictures) {
        cin >> sz >> val;
    }

    vector<int> frames(m);
    for (auto &x : frames) {
        cin >> x;
    }

    sort(pictures.begin(), pictures.end());
    sort(frames.begin(), frames.end());

    // cout << "### PICTURES ###\n";
    // for (const auto &[val, sz] : pictures) {
    //     cout << sz << " " << val << "\n";
    // }

    // cout << "\n";

    // cout << "### FRAMES ###\n";
    // for (const auto &x : frames)
    //     cout << x << " ";

    // cout << "\n\n";

    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    // cout << "### EVALUTATE ###\n";

    int pointer = 0;
    for (const auto &[val, sz] : pictures) {
        while (pointer < m && frames[pointer] < sz) 
            pointer++;

        if (pointer < m && frames[pointer] >= sz) {
            pointer++;

            int j = upper_bound(dp.begin(), dp.end(), val) - dp.begin();
            if (dp[j - 1] <= val && val <= dp[j]) {
                // cout << j << " " << dp[j] << " " << val << "\n";

                dp[j] = val;
            }
        }
    }

    // cout << "\n";

    // for (int i = n; i >= 0; i--) {
    //     if (dp[i] < INF) {
    //         cout << i;
    //         return;
    //     }

    //     // cout << dp[i] << " ";
    // }

    // cout << "### DP ###\n";

    // for (int i = 0; i <= n; i++) {
    //     cout << i << ": " << dp[i] << "\n";
    // }

    // cout << "\n";

    // cout << "### Answer ###\n";

    for (int i = n; i >= 0; i--) {
        if (dp[i] < INF) {
            cout << i;
            return;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -