제출 #89134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89134		nikolapesic2802	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	1665 ms	19036 KiB

arranging_tickets

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e5 + 100, MAX_M = 1e5 + 100;

int N, M; ti Nr[MAX_M];
ll Sum[MAX_N], Temp[MAX_N], maxV;
vector<vector<pi> > interval(MAX_N);
bool isCan(ll use, ll up) {
	ll cnt = 0;
	priority_queue<pi> Q;
	for(int i=0; i<=N; i++) Temp[i] = 0;
	for(int i=1, j=0; i<=N; i++) {
		Temp[i] += Temp[i-1];
		for(auto p:interval[i])
            Q.push(p);
		ll now = Sum[i] + Temp[i];
		while(!Q.empty() && now > up) {
			int y, c; tie(y, c) = Q.top(); Q.pop();
			if(y <= i) continue;
			int v = min((ll)c, (now - up + 1) / 2);
			Temp[i] -= 2 * v;
			Temp[y] += 2 * v;
			cnt += v;
			now -= 2 * v;
			if(c - v > 0) Q.push(pi(y, c-v));
		}
		if(now > up) return false;
		if(cnt > use) return false;
	}
	return true;
}
int main() {
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c);
		if(x > y) swap(x, y);
		interval[x].push_back({y,c});
		Sum[x] += c; Sum[y] -= c;
	}
	for(int i=1; i<=N; i++) Sum[i] += Sum[i-1], maxV = max(maxV, Sum[i]);

	ll ans = -1;
	for(ll l=0, r=maxV; l<=r; ) {
		ll m = (l+r) >> 1;
		if(isCan(maxV-m, 2*m-maxV) || isCan(maxV-m+1, 2*m-maxV-1)) ans = m, r = m-1; else l = m+1;
	}
	printf("%lld\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:44:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, c; scanf("%d%d%d", &x, &y, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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