Submission #691171

#	Time	Username	Problem	Language	Result	Execution time	Memory
691171		amunduzbaev	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	181 ms	296 KiB

arranging_tickets

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define ar array
//~ #define int ll

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

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