Submission #536678

#	Time	Username	Problem	Language	Result	Execution time	Memory
536678		nafis_shifat	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	135 ms	1364 KiB

event2

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=6e3+5;
const int inf=1e9;
int n, k;
int l[mxn], r[mxn];


bool blocked[mxn] = {};
vector<int> ord;
vector<int> en[mxn];

int ans[mxn] = {};

int get() {
	int dp[mxn] = {};
	for(int i = 1; i < mxn; i++) {
		dp[i] = dp[i - 1];

		for(int j : en[i]) if(!blocked[j]) dp[i] = max(dp[i], dp[l[j]] + 1);
	} 

    return dp[mxn - 1];
}


int main() {
	cin >> n >> k;
	vector<int> v;
	for(int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
		v.push_back(l[i]);
		v.push_back(r[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()), v.end());

	for(int i = 1; i <= n; i++) {
		l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin() + 1;
		r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin() + 1;
		en[r[i]].push_back(i);
	}

	int needed = k;

	
	for(int i = 1; i <= n; i++) {
		if(blocked[i]) continue;
		if(needed <= 0) break;

		bool pb[n + 1];
		for(int j = 1; j <= n; j++) pb[j] = blocked[j];
		blocked[i] = 1;

		for(int j = 1; j <= n; j++) if(!(r[j] <= l[i] || l[j] >= r[i])) blocked[j] = 1;

		if(get() >= needed - 1) {
			ans[i] = 1;
			needed--;
			continue;
		} else {
			for(int j = 1; j <= n; j++) blocked[j] = pb[j];
		}

	}

	if(needed > 0) cout<<-1<<endl;
	else {
		for(int i = 1; i <= n; i++) if(ans[i]) cout<<i<<endl;
	}




}

• Subtask 1: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 0 / 61