Submission

Status:

(PPPP)(PPP)(PPPP)(PPPPPPP)(PPPPPPP)(PPPPPPPPPPP)(PPPPPPPPPPPPPPxSSSSSSSSSSSSSSSSSSSSSSSSSSSSS)

Subtask/Task Score:

{9/9}{5/5}{6/6}{11/11}{14/14}{25/25}{0/30}

Score: 70

User: pxsit

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

Language: cpp

Time: 0.844 second

Submitted On: 2025-06-19 18:53:30

#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 ppower
    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, ppower] = arr[i];
        auto &route = routes[lane];
        int pos = upper_bound(route.begin(), route.end(), ppower) - route.begin();
        if (pos >= (int)route.size()) route.push_back(ppower);
        else route[pos] = ppower;
        
        for(ll j = 0; j < U; ++j) {
            if (j == lane) continue;
            auto &another_route = routes[j];
            if(pos-k<0) continue;
            if (pos-k < (int)another_route.size()) 
            another_route[pos-k] = min(another_route[pos-k], ppower);
            else if (pos-k == (int)another_route.size()) another_route.push_back(ppower);
        }
    }
    
    int ans = 0;
    for(int i = 0; i < U; ++i) {
        ans = max(ans, (int)routes[i].size());
    }
    cout << ans;
    
}