Submission

Score: 100

User: navysrimuang

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

Language: cpp

Time: 0.292 second

Submitted On: 2026-04-26 23:33:55

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

int dp[100001]; 
int BIT[1001][100001];
int U,K,N;

void update(int i, int x, int u){
    for(;i<=N;i+=i&-i) BIT[u][i] = max(BIT[u][i], x);
}

int qr(int i, int u){
   int sum = INT_MIN; 
   for(;i > 0;i-=i&-i) sum = max(sum, BIT[u][i]);
   return sum;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> U >> K >> N;
    vector<tuple<int,int,int>> v(N); //t, p, u
    for(int i = 0;i<N;i++){
        int p,w,t;
        cin >> p >> w >> t;
        v[i] = {t,p,w};
    }    

    sort(v.begin(), v.end());

    int ii = 1;
    for(auto& [t,p,w] : v) t = ii++;

    sort(v.begin(), v.end() ,[](auto a, auto b){
        return get<1>(a) < get<1>(b);
    });

    int ans = 0;

    for(auto [t,p,w] : v){

        int dp = max(qr(t, w), qr(t, U) - K) + 1;         
        ans = max(ans, dp);

        update(t, dp, w);
        update(t, dp, U);

    }

    cout << ans << "\n";
    return 0;
}