Submission #1077161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077161		kwongweng	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	128 ms	436 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=a; i>=b; i--)
#define pb push_back
#define fi first
#define se second

int main(){
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    int n,m; cin>>n>>m;
    vi a(m), b(m), c(m); FOR(i,0,m) cin>>a[i]>>b[i]>>c[i];
    FOR(i,0,m){
        if (a[i]>b[i]) swap(a[i],b[i]);
    }
    vector<ll> cnt;
    ll mn = m;
    FOR(i,0,(1<<m)){
        cnt.assign(n+1,0);
        FOR(j,0,m){
            if (i&(1<<j)){
                cnt[a[j]+1]++; if (b[j]<n) cnt[b[j]+1]--;
            }else{
                cnt[1]++; cnt[a[j]+1]--; if (b[j]<n) cnt[b[j]+1]++;
            }
        }
        FOR(j,1,n+1) cnt[j] += cnt[j-1];
        ll mx = 0; FOR(j,1,n+1) mx = max(mx, cnt[j]);
        //cout<<" "; FOR(j,1,n+1) cout<<cnt[j]<<" ";
        //cout<<"\n";
        FOR(j,1,n+1) mn=min(mn,mx);
    }
    cout<<mn<<"\n";
    return 0;
}

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