C. 討論室 (discussion) －Subtask 2

#include <bits/stdc++.h>
using namespace std;

template <size_t D, typename T>
struct Vec : public vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N, K; cin >> N >> K;

    Vec<2, int> cnt(13, 14, 0);
    for (int i = 0, l, r; i < N; ++i) cin >> l >> r, ++cnt[l-8][r-8];

    vector<pair<int, int>> itv;
    for (int L = 0; L <= 12; ++L) {
        int cntL = 0;
        for (int R = L+1; R <= 13; ++R) {
            while (cntL < K and cnt[L][R]) itv.emplace_back(L, R), ++cntL, --cnt[L][R];
        }
    }
    N = itv.size();

    Vec<5, int> dp(14, 14, 14, 14, 14, 0);

    auto get = [&](int t1, int t2, int t3, int t4, int t5) -> int {
        array<int, 5> _tmp{t1, t2, t3, t4, t5};
        sort(rbegin(_tmp), rend(_tmp));
        if (_tmp[4] < 0) return 0;
        return dp[_tmp[0]][_tmp[1]][_tmp[2]][_tmp[3]][_tmp[4]];
    };

    for (auto [L, R] : itv) {

        /// 11628 sol. to [13 >= t1 >= t2 >= t3 >= t4 >= t5 >= 0] ///

        for (int t1 = 13; t1 >= 0; --t1) for (int t2 = t1; t2 >= 0; --t2) for (int t3 = t2; t3 >= 0; --t3)
        for (int t4 = t3; t4 >= 0; --t4) for (int t5 = t4; t5 >= 0; --t5) {
            dp[t1][t2][t3][t4][t5] = max({
                dp[t1][t2][t3][t4][t5], /// self
                (t1 >= R ? get(L, t2, t3, t4, t5) + 1 : 0), /// put in 1
                (t2 >= R ? get(t1, L, t3, t4, t5) + 1 : 0), /// put in 2
                (t3 >= R ? get(t1, t2, L, t4, t5) + 1 : 0), /// put in 3
                (t4 >= R ? get(t1, t2, t3, L, t5) + 1 : 0), /// put in 4
                (t5 >= R ? get(t1, t2, t3, t4, L) + 1 : 0), /// put in 5
            });
        }

        for (int t5 =  0; t5 <= 13; ++t5) for (int t4 = t5; t4 <= 13; ++t4) for (int t3 = t4; t3 <= 13; ++t3)
        for (int t2 = t3; t2 <= 13; ++t2) for (int t1 = t2; t1 <= 13; ++t1) {
            dp[t1][t2][t3][t4][t5] = max({
                get(t1, t2, t3, t4, t5),   get(t1-1, t2, t3, t4, t5), get(t1, t2-1, t3, t4, t5),
                get(t1, t2, t3-1, t4, t5), get(t1, t2, t3, t4-1, t5), get(t1, t2, t3, t4, t5-1),
            }); /// do nothing
        }

    }

    if (K == 1) cout << dp[13][ 0][ 0][ 0][ 0] << "\n";
    if (K == 2) cout << dp[13][13][ 0][ 0][ 0] << "\n";
    if (K == 3) cout << dp[13][13][13][ 0][ 0] << "\n";
    if (K == 4) cout << dp[13][13][13][13][ 0] << "\n";
    if (K == 5) cout << dp[13][13][13][13][13] << "\n";

    return 0;
}