Submission #116125

#	Time	Username	Problem	Language	Result	Execution time	Memory
116125		shayan_p	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	1761 ms	512 KiB

arranging_tickets

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=30,mod=1e9+7;
const ll inf=1e18;

int a[maxn],b[maxn];
ll c[maxn],val[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    int n,m; cin>>n>>m;

    for(int i=0;i<m;i++){
	cin>>a[i]>>b[i]>>c[i]; --a[i],--b[i];
    }
    ll ans=inf;
    for(int msk=0;msk<(1<<m);msk++){
	memset(val,0,sizeof val);
	for(int i=0;i<m;i++){
	    if(bit(msk,i)){
		for(int j=a[i];j!=b[i];j=(j+1)%n){
		    val[j]+=c[i];
		}
	    }
	    else{
		for(int j=b[i];j!=a[i];j=(j+1)%n){
		    val[j]+=c[i];
		}
	    }	 
	}
	ll mx=0;
	for(int i=0;i<n;i++){
	    mx=max(mx,val[i]);
	}
	ans=min(ans,mx);
    }
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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