Submission

Score: 0

User: kungarooo

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

Language: cpp

Time: 2.085 second

Submitted On: 2025-11-17 00:34:41

#include<bits/stdc++.h>
using namespace std;
int u,k,n;
vector<vector<int>> dp,dp2;
vector<pair<int,int>> a[1000];
bool cmp(int a,int x){
    return a>x;
}
void udp(int idx){
    vector<int> st;
    for(auto i:a[idx]){
        //cout<<i.second<<" ";
        auto it=lower_bound(st.begin(),st.end(),i.second);
        dp[idx].push_back(it-st.begin()+1);
        if(it==st.end())st.push_back(i.second);
        else (*it)=i.second;
    }
    //cout<<"::\n";
}
void udp2(int idx){
    vector<int> st;
    for(int j=a[idx].size()-1;j>=0;j--){
        pair<int,int> i=a[idx][j];
        //cout<<i.second<<" ";
        auto it=lower_bound(st.begin(),st.end(),i.second,cmp);
        dp2[idx].push_back(it-st.begin()+1);
        if(it==st.end())st.push_back(i.second);
        else (*it)=i.second;
    }
    //cout<<"::\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //time power lens idx
    vector<tuple<int,int,int,int>> path;
    cin>>u>>k>>n;
    dp=vector<vector<int>>(u);
    dp2=vector<vector<int>>(u);
    for(int i=0;i<n;i++){
        int p,w,t;
        cin>>p>>w>>t;
        a[w].push_back({t,p});
    }
    for(int i=0;i<u;i++){
        sort(a[i].begin(),a[i].end());
        int ooo=0;
        for(auto j:a[i]){
            path.push_back({j.first,j.second,i,ooo});
            ooo++;
        }
    }
    sort(path.begin(),path.end());
    for(int i=0;i<u;i++){
        udp(i);
    }
    for(int i=0;i<u;i++){
        udp2(i);
    }
    for(int i=0;i<u;i++){
        reverse(dp2[i].begin(),dp2[i].end());
    }
    int ans=1,lftmx=1;
    int dpdp[n]={},pre[u]={};
    for(int i=0;i<u;i++)pre[i]=-1;
    for(int i=0;i<n;i++)dpdp[i]=1;
    for(int i=n-2;i>=0;i--){
        auto [time,power,lens,idx] = path[i];
        dpdp[i]=dp2[lens][idx];
        for(int j=i+1;j<n;j++){
            if(get<2>(path[j])>power){
                if(get<3>(path[j])==lens)dpdp[i]=max(dpdp[i],dpdp[j]+1);
                else dpdp[i]=max(dpdp[i],dpdp[j]+1-k);
            }
        }
        //if(pre[lens]!=-1)dpdp[i]=max(dpdp[i],1+dpdp[pre[lens]]);
        //pre[lens]=i;
    }

    for(int i=0;i<n;i++){
        auto [time,power,lens,idx] = path[i];
        ans=max(ans,dp[lens][idx]);
        ans=max(ans,dpdp[i]+dp[lens][idx]-1);
    }
    // for(int i=0;i<n;i++){
    //     cout<<dpdp[i]<<" ";    }
    // cout<<"\n";
    cout<<ans;
    return 0;
}
/*
1 0 10
1 0 1
23 0 2
12 0 3
13 0 4
6 0 5
16 0 6
700 0 7
81 0 8
90 0 9
10 0 10
*/