제출 #1210735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210735		AMnu	Arranging Tickets (JOI17_arranging_tickets)	C++20	45 / 100	7 ms	10052 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef pair<int,int> pii;

const int MAXN = 4e5+5;

int N, M, st;
ll pref[MAXN], mn, ans;
vector <pii> seg[MAXN];
priority_queue <pii> PQ;

void solve() {
	for (int i=st;i<=st+N;i++) {
		pref[i] = 0;
	}
	while (!PQ.empty()) {
		PQ.pop();
	}
	for (int i=st+1;i<=st+N;i++) {
		pref[i] += pref[i-1];
		for (auto x : seg[i]) {
			if (x.fi > st+N) continue;
			pref[i] += x.se;
			pref[x.fi] -= x.se;
			PQ.push(x);
		}
		while (pref[i] > ans) {
			auto x = PQ.top();
			PQ.pop();
			int use = min((ll)x.se,(pref[i]-ans+1)/2);
			if (use < x.se) {
				PQ.push({x.fi,x.se-use});
			}
			ans += use;
			pref[i] -= use;
			pref[x.fi] += 2*use;
		}
	}
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i=1;i<=M;i++) {
		int A, B, C;
		cin >> A >> B >> C;
		if (A > B) swap(A,B);
		seg[A].push_back({B,C});
		seg[B].push_back({N+A,C});
		seg[N+A].push_back({N+B,C});
		pref[A] += C;
		pref[B] -= C;
	}
	for (int i=1;i<=N;i++) {
		pref[i] += pref[i-1];
		if (pref[i] > pref[st]) {
			st = i;
		}
	}
	st = 1;
	solve();
	mn = ans;
	ans = 1;
	solve();
	cout << min(mn,ans) << "\n";
}

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