Submission #563097

#	Time	Username	Problem	Language	Result	Execution time	Memory
563097		amunduzbaev	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	155 ms	468 KiB

arranging_tickets

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<int> l(m), r(m), c(m);
	for(int i=0;i<m;i++){
		cin>>l[i]>>r[i]>>c[i];
		if(l[i] > r[i]) swap(l[i], r[i]);
		r[i]--;
	}
	
	int pref[25] {}, res = m;
	for(int mask=0;mask < (1 << m);mask++){
		memset(pref, 0, sizeof pref);
		for(int i=0;i<m;i++){
			if(mask >> i & 1) pref[l[i]]++, pref[r[i] + 1]--;
			else {
				pref[0]++, pref[l[i]]--, pref[r[i] + 1]++;
			}
		}
		
		for(int i=1;i<=n;i++){
			pref[i] += pref[i-1];
		}
		res = min(res, *max_element(pref, pref + 24));
	}
	
	cout<<res<<"\n";
}
 

• Subtask 1: 10 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15