← Real problems

noip99p1

mediumlisdilworthStatement on DMOJ

CP Lang

6 lines0.3 spec
// noip99p1 Missile Interception: one system hits a non-increasing run of heights. How many missiles
// can one system hit (longest non-increasing subsequence), and how many systems hit them all
// (Dilworth: the longest strictly increasing subsequence)?
let h = read_all<0..=50_000>()
print(h.lis(strict: false, by: desc).len)
print(h.lis().len)

Accepted C++

70 lines · 0.01 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

void solve() {
    vector<int> arr;
    {
        int x;
        while (cin >> x) {
            arr.push_back(x);
        }
    }
    int n = sz(arr);
    {
        int dp[n] {};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] >= arr[i]) {
                    dp[i] = max(dp[i], dp[j]);
                }
            }
            dp[i]++;
        }
        cout << *max_element(dp, dp + n) << endl;
    }
    multiset<int> s;
    for (auto& a : arr) {
        auto it = s.lower_bound(a);
        if (it == s.end()) {
            s.insert(a);
        } else {
            it = s.erase(it);
            s.insert(it, a);
        }
    }
    cout << sz(s) << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
}