Submission #345827

#	Time	Username	Problem	Language	Result	Execution time	Memory
345827		kshitij_sodani	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	1184 ms	504 KiB

arranging_tickets

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n,m;
int aa[200001];
int bb[200001];
int cc[200001];
int co[200001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>aa[i]>>bb[i]>>cc[i];
		aa[i]--;
		bb[i]--;
	}
	int ans=m;
	for(int i=0;i<(1<<m);i++){
		for(int j=0;j<n;j++){
			co[j]=0;
		}
		for(int j=0;j<m;j++){
			if(i&(1<<j)){
				int cur=aa[j];
				while(cur!=bb[j]){
					co[cur]++;
					cur=(cur+1)%n;
				}
			}
			else{
				int cur=bb[j];
				while(cur!=aa[j]){
					co[cur]++;
					cur=(cur+1)%n;
				}
			}
		}
		int ma=0;
		for(int j=0;j<n;j++){
			ma=max(ma,co[j]);
		}
		ans=min(ans,ma);
	}

	cout<<ans<<endl;



 
	return 0;
}

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