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;
}