제출 #135440

#제출 시각아이디문제언어결과실행 시간메모리
135440mirbek01Arranging Tickets (JOI17_arranging_tickets)C++11
0 / 100
2 ms376 KiB
# 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...