oj.uz

Submission #135440

# Submission time Handle Problem Language Result Execution time Memory
135440 2019-07-24T05:42:39 Z mirbek01 Arranging Tickets (JOI17_arranging_tickets) C++11
0 / 100
 2 ms 376 KB 
# 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -