Submission

Score: 11

User: qweqwe

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

Language: cpp

Time: 0.059 second

Submitted On: 2026-03-26 17:51:22

#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=4e18;
	for (pii i:unis[unis.size()-1]){
		stack<pair<pii,pii>> st;st.push({i,{unis.size()-1,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;
			
			if (cur<=1){
				mx=min(mx,cnt);break;
			}
			
			//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;
	cout << tails.size()-(mx*k);
	return 0;
}