Submission #135440

#	Time	Username	Problem	Language	Result	Execution time	Memory
135440		mirbek01	Arranging Tickets (JOI17_arranging_tickets)	C++11	0 / 100	2 ms	376 KiB

arranging_tickets

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 2;

struct st{
	int a, b;
	long long c;
} ar[N], b[N];

int n, m, pf[N];
long long ans;

bool cmp(st a, st b){
	if(a.a == b.a)
		return a.b < b.b;
	return a.a < b.a;
}

int main(){
	cin >> n >> m;
	
	for(int i = 1; i <= m; i ++){
		cin >> ar[i].a >> ar[i].b >> ar[i].c;
		if(ar[i].a > ar[i].b)
			swap(ar[i].a, ar[i].b);
	}
	
	sort(ar + 1, ar + m + 1, cmp);
	int sz = 0;
	
	for(int i = 1; i <= m; i ++){
		int pt = i;
		while(pt + 1 <= m && ar[pt + 1].a == ar[i].a && ar[pt + 1].b == ar[i].b)
			ar[i].c += ar[++ pt].c;
		b[++ sz] = ar[i];
		i = pt;
	}
	m = sz;
	
	for(int i = 1; i <= m; i ++)
		ar[i] = b[i];
	
	for(int i = 1; i <= m; i ++){
		ans += ar[i].c / 2;
		ar[i].c %= 2;
		pf[ ar[i].a ] += ar[i].c;
		pf[ ar[i].b ] -= ar[i].c;
	}
	
	int mx = 0;
	
	for(int i = 1; i <= n; i ++){
		pf[i] += pf[i - 1];
		mx = max(mx, pf[i]);
	}
	cout << ans + (mx + 1) / 2 << endl;
}

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