Submission

Score: 0

User: qweqwe

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

Language: cpp

Time: 2.095 second

Submitted On: 2026-03-26 17:59:42

#include <bits/stdc++.h>
#define qweqwe cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

struct State{
	int c,uni,idx;
	bool operator<(const State& o) const{
		return tie(idx,uni,c)<tie(o.idx,o.uni,o.c);
	}
};

int main(){
	qweqwe;
	int u,k,n;cin >> u >> k >> n;
	vector<State> arr(n);
	for (int i=0;i<n;i++){
		cin >> arr[i].c >> arr[i].uni >> arr[i].idx;
	}
	sort(arr.begin(),arr.end());
	
	vector<int> tails;
	vector<vector<pii>> unis;
	
	for (int i=0;i<n;i++){
		int pos = lower_bound(tails.begin(),tails.end(),arr[i].c)-tails.begin();
		if (pos >= tails.size()){
			tails.push_back(arr[i].c);
			unis.push_back({{arr[i].uni,arr[i].idx}});
		} 
		else{
			tails[pos]=arr[i].c;
			unis[pos].push_back({arr[i].uni,arr[i].idx});
		}
	}
	/*
	for (int i:tails){
		cout << i << " ";
	}
	for (vector<pii> i:unis){
		for (pii j:i){
			cout << j.first << " " << j.second << "\n";
		}cout << "\n";
	}
	*/
	/*
	int cnt=0,prev=unis[0];
	for (int i=0;i<unis.size();i++){
		if (unis[i]!=prev){
			cnt+=k;
		}prev=unis[i];
	}
	*/
	
	ll mx=0;
	for (int a=unis.size()-1;a>=0;a--){
		for (pii i:unis[a]){
			stack<pair<pii,pii>> st;st.push({i,{a,0}});
			unordered_map<int,bool> vis;
			while (!st.empty()){
				pair<pii,pii> t=st.top();st.pop();
				
				ll uni=t.first.first,idx=t.first.second,cur=t.second.first,cnt=t.second.second;
				
				//cout << uni << " " << idx << " " << cur << " " << cnt << '\n';
				
				if (cur<=0){
					//cout << a+1 << " " << cnt << "\n";
					mx=max(mx,a+1-cnt*k);continue;
				}
				
				if (vis.count(idx)) continue;
				vis[idx]=1;
				
				for (pii j:unis[cur-1]){
					
					if (vis.count(j.second) || j.second > idx) continue;
					//vis[j.second]=1;
					
					if (uni!=j.first)st.push({{j.first,j.second},{cur-1,cnt+1}});
					else st.push({{uni,j.second},{cur-1,cnt}});
				}
			}//cout << mx << "\n----------------\n";
		}
	}
	//cout << mx;
	cout << mx;
	return 0;
}