제출 #336436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336436		arujbansal	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	384 KiB

joi2019_ho_t2

#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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50