Submission #1204102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204102		Muhammad_Aneeq	Arranging Tickets (JOI17_arranging_tickets)	C++20	In queue	0 ms	0 KiB

arranging_tickets

#include <iostream>
using namespace std;
int const N=3e3+10;
int n,m;
int a[N],b[N],c[N];
// int St[4*N]={};
// int lazy[4*N]={};
// int fen[N]={};
// void push(int i)
// {
// 	for (int j=2*i;j<=2*i+1;j++)
// 	{
// 		lazy[j]+=lazy[i];
// 		St[j]+=lazy[i];
// 	}
// 	lazy[i]=0;
// }
// void reset(int i,int st,int en)
// {
// 	St[i]=lazy[i]=0;
// 	if (st==en)
// 		return;
// 	int mid=(st+en)/2;
// 	reset(i*2,st,mid);
// 	reset(i*2+1,mid+1,en);
// }
// void update(int i,int st,int en,int l,int r,int val)
// {
// 	if (l>r)
// 		return;
// 	if (st>=l&&en<=r)
// 	{
// 		lazy[i]+=val;
// 		St[i]+=val;
// 		return;
// 	}
// 	if (st>r||en<l)
// 		return;
// 	int mid=(st+en)/2;
// 	push(i);
// 	update(i*2,st,mid,l,r,val);
// 	update(i*2+1,mid+1,en,l,r,val);
// 	St[i]=max(St[i*2],St[i*2+1]);
// }
// int get(int i,int st,int en,int l,int r)
// {
// 	if (l>r)
// 		return 0;
// 	if (st>=l&&en<=r)
// 		return St[i];
// 	if (st>r||en<l)
// 		return 0;
// 	push(i);
// 	int mid=(st+en)/2;
// 	return max(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
// }
inline void solve()
{
	cin>>n>>m;
	for (int i=0;i<m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		a[i]--;b[i]--;
	}
	int mx=1e3;
	int cnt[n]={};
	for(int i=0;i<(1<<m);i++)
	{
		for (int i=0;i<n;i++)
			cnt[i]=0;
		int mf=0;
		for (int j=0;j<m;j++)
		{
			if((1<<j)&i)
			{
				if (a[j]<b[j])
				{
					for (int k=a[j];k<b[j];k++)
						cnt[k]++;
				}
				else
				{
					for (int k=a[j];k<n;k++)
						cnt[k]++;
					for (int k=0;k<b[j];k++)
						cnt[k]++;
				}
			}
			else
			{
				if (a[j]<b[j])
				{
					for (int k=0;k<a[j];k++)
						cnt[k]++;
					for (int k=b[j];k<n;k++)
						cnt[k]++;
				}
				else
				{
					for (int k=b[j];k<a[j];k++)
						cnt[k]++;
				}
			}
		}
		for (int j=0;j<n;j++)
			mf=max(mf,cnt[j]);
		mx=min(mx,mf);
	}
	cout<<mx<<endl;
	// for (int i=0;i<m;i++)
	// {
	// 	if (a[i]<b[i])
	// 	{
	// 		int z=get(1,0,n-1,a[i],b[i]-1);
	// 		int f=max(get(1,0,n-1,0,a[i]-1),get(1,0,n-1,b[i],n-1));
	// 		if (z==f)
	// 		{
	// 			if (b[i]-a[i]>=a[i]+(n-1-b[i]+1))
	// 			{
	// 				cout<<i<<endl;
	// 				update(1,0,n-1,a[i],b[i]-1,c[i]);
	// 			}
	// 			else
	// 			{
	// 				update(1,0,n-1,0,a[i]-1,c[i]);
	// 				update(1,0,n-1,b[i],n-1,c[i]);
	// 			}
	// 		}
	// 		else
	// 		{
	// 			if (z<f)
	// 			{
	// 				cout<<i<<endl;
	// 				update(1,0,n-1,a[i],b[i]-1,c[i]);
	// 			}
	// 			else
	// 			{
	// 				update(1,0,n-1,0,a[i]-1,c[i]);
	// 				update(1,0,n-1,b[i],n-1,c[i]);
	// 			}
	// 		}
	// 	}
	// 	else
	// 	{
	// 		int z=get(1,0,n-1,b[i],a[i]-1);
	// 		int f=max(get(1,0,n-1,0,b[i]-1),get(1,0,n-1,a[i],n-1));
	// 		if (z==f)
	// 		{
	// 			if (a[i]-b[i]>b[i]+(n-1-a[i]+1))
	// 				update(1,0,n-1,b[i],a[i]-1,c[i]);
	// 			else
	// 			{
	// 				update(1,0,n-1,0,b[i]-1,c[i]);
	// 				update(1,0,n-1,a[i],n-1,c[i]);
	// 			}
	// 		}
	// 		else
	// 		{
	// 			if (z<f)
	// 				update(1,0,n-1,b[i],a[i]-1,c[i]);
	// 			else
	// 			{
	// 				update(1,0,n-1,0,b[i]-1,c[i]);
	// 				update(1,0,n-1,a[i],n-1,c[i]);
	// 			}
	// 		}
	// 	}
	// }
	// for (int i=0;i<n;i++)
	// {
	// 	cout<<get(1,0,n-1,i,i)<<endl;
	// }
	// cout<<get(1,0,n-1,0,n-1)<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}