Submission #1229766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229766		PenguinsAreCute	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	100 ms	412 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	int a[m], b[m];
	for(int i=0,trash;i<m;i++) {
		cin >> a[i] >> b[i] >> trash;
		a[i]--;
		b[i]--;
		if(a[i] > b[i])
			swap(a[i], b[i]);
	}
	int ans = 1e9;
	for(int i=0;i<(1<<m);i++) {
		int cnt[n+1];
		memset(cnt,0,sizeof(cnt));
		for(int j=0;j<m;j++) {
			if(i&(1<<j))
				cnt[0]++, cnt[a[j]]--, cnt[b[j]]++;
			else
				cnt[a[j]]++, cnt[b[j]]--;
		}
		partial_sum(cnt,cnt+n,cnt);
		ans = min(ans, *max_element(cnt,cnt+n));
	}
	cout << ans;
}

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