Submission

Score: 70

User: pxsit

Problemset: ผลึกเวลา (Crystal)

Language: cpp

Time: 0.875 second

Submitted On: 2025-06-15 20:27:18

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

int U, k, n;

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> U >> k >> n;
    vector<tuple<ll, ll, ll>> arr(n); // time lane power
    ll p, w, t;
    for (int i = 0; i < n; ++i) {
        cin >> p >> w >> t;
        arr[i] = {t, w, p};
    }
    sort(arr.begin(), arr.end());

    vector<vector<ll>> routes(U);

    for (int i = 0; i < n; ++i) {
        auto &[tim, lane, power] = arr[i];
        auto &route = routes[lane];
        int pos = upper_bound(route.begin(), route.end(), power) - route.begin();
        if (pos >= (int)route.size())
            route.emplace_back(power);
        else
            route[pos] = power;

        for (ll j = 0; j < U; ++j) {
            if (j == lane)
                continue;
            auto &another_route = routes[j];
            if (pos - k >= 0 && pos - k < (int)another_route.size())
                another_route[pos - k] = min(another_route[pos - k], power);
            else if (pos - k >= (int)another_route.size())
                another_route.emplace_back(power);
        }
    }

    int ans = 0;
    for (int i = 0; i < U; ++i) {
        ans = max(ans, (int)routes[i].size());
    }
    cout << ans;
}