Submission #55052

#	Time	Username	Problem	Language	Result	Execution time	Memory
55052		spencercompton	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	416 ms	716 KiB

arranging_tickets

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	pair<int, int> ranges[m];
	
	bool used[m];
	for(int i = 0; i<m; i++){
		used[i] = false;
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		int c;
		cin >> c;
		if(a>b){
			swap(a,b);
		}
		a++;
		ranges[i] = make_pair(a,b);
		// cout << "! " << a << " " << b << endl;
	}
	int ans = m;
	for(int i = 0; i<(1<<m); i++){
		int ar[n];
		for(int i = 0; i<=n; i++){
			ar[i] = 0;
		}
		int now = 0;
		for(int j = 0; j<m; j++){
			bool on = (i&(1<<j))!=0;
			if(on){
				for(int k = ranges[j].first; k<=ranges[j].second; k++){
					ar[k]++;
					now = max(now,ar[k]);
				}
			}
			else{
				for(int k = 0; k<ranges[j].first; k++){
					ar[k]++;
					now = max(now,ar[k]);
				}
				for(int k = ranges[j].second+1; k<n; k++){
					ar[k]++;
					now = max(now, ar[k]);
				}
			}
		}
		ans = min(ans,now);
	}
	// while(true){
	// 	bool did = false;
	// 	for(int i = 0; i<m; i++){
	// 		int outmax = 0;
	// 		int inmax = 0;
	// 		// cout << "A " << i << endl;
	// 		// cout << "B " << i << endl;
	// 		for(int j = 0; j<n; j++){
	// 			if(j>=ranges[i].first && j<=ranges[i].second){
	// 				inmax = max(inmax,ar[j]);
	// 			}
	// 			else{
	// 				outmax = max(outmax,ar[j]);
	// 			}
	// 		}
	// 		// cout << "X " << i << " " << inmax << " " << outmax << endl;
	// 		if(used[i]==false){
	// 			if(inmax-1 <= outmax){
	// 				continue;
	// 			}
	// 			// cout << "DOING " << i << endl;
	// 			did = true;
	// 			for(int j = 0; j<n; j++){
	// 				if(j>=ranges[i].first && j<=ranges[i].second){
	// 					ar[j]--;
	// 				}
	// 				else{
	// 					ar[j]++;
	// 				}
	// 			}
	// 		}
	// 		else{
	// 			if(outmax-1 <= inmax){
	// 				continue;
	// 			}
	// 			did = true;
	// 			for(int j = 0; j<n; j++){
	// 				if(j>=ranges[i].first && j<=ranges[i].second){
	// 					ar[j]++;
	// 				}
	// 				else{
	// 					ar[j]--;
	// 				}
	// 			}
	// 		}
	// 		used[i] = !used[i];
			
	// 	}
	// 	if(!did){
	// 		break;
	// 	}
	// }
	// int ans = 0;
	// for(int i = 0; i<n; i++){
	// 	ans = max(ar[i],ans);
	// }
	cout << ans << endl;
}

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