Submission #412290

#	Time	Username	Problem	Language	Result	Execution time	Memory
412290		amoo_safar	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	199 ms	24348 KiB

arranging_tickets

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 4e5 + 10;

vector<pii> G[N];
int n, m;

void Add_Edge(int u, int v, int c){
	G[u].pb({v, c});
}

ll ps[N];

ll Solve(int l, int dif){
	int r = l + n;
	memset(ps, 0, sizeof ps);
	multiset<pii> ms;

	ll res = 0;
	for(int i = l; i < r - 1; i++){
		for(auto [x, c] : G[i]){
			if(x >= r) continue;
			ps[i] += c;
			ps[x] -= c;
			ms.insert({x, c});
		}
		ps[i] += ps[i - 1];
		while(ps[i] > dif){
			auto [fr, cnt] = *ms.rbegin();
			ms.erase(ms.find({fr, cnt}));
			if(fr <= i)
				continue;

			int del = min((ll) cnt, (ps[i] - dif + 1) / 2);
			
			ps[i] -= 2 * del;
			ps[fr] += 2 * del;
			res += del;
			if(cnt > del)
				ms.insert({fr, cnt - del});
		}
	}
	return res + dif;
}

ll df[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int a, b, c;
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		// assert(c == 1);
		if(a > b) swap(a, b);
		df[a] += c;
		df[b] -= c;
		
		Add_Edge(a, b, c);
		Add_Edge(b, n + a, c);
		Add_Edge(n + a, n + b, c);
	}
	for(int i = 1; i <= n; i++) df[i] += df[i - 1];
	int id_mx = max_element(df + 1, df + n) - df;
	id_mx ++;
	ll ans = min(Solve(id_mx, 0), Solve(id_mx, 1));

	cout << ans << '\n';
	return 0;
}

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