Submission #73284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
73284	2018-08-28T06:39:24 Z	윤교준(#2271)	Radio (Balkan15_RADIO)	C++11	45 / 100	2000 ms	4812 KB

radio

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const bool debug = 0;
const int MAXN = 100005;

struct EVT {
	EVT(int x, int idx) : x(x), idx(idx) {}
	int x, idx;

	bool operator < (const EVT &t) const {
		if(x != t.x) return x < t.x;
		return idx < t.idx;
	}
};

multiset<int> AI, AO, BI, BO, CI, CO;

vector<EVT> EV;
vector<int> XV;

int A[MAXN], B[MAXN], C[MAXN];

ll Ans = INFLL, Sum, SumA, SumC;
int N, K;

inline void erase(multiset<int> &A, multiset<int> &B, int x) {
	auto it = A.find(x);
	if(A.end() != it) {
		A.erase(it);
		Sum -= x;
		return;
	}
	it = B.find(x);
	if(B.end() != it)
		B.erase(it);
}
inline void goup(multiset<int> &A, multiset<int> &B) {
	for(int t; !B.empty();) {
		t = *prev(B.end());
		if(!A.empty() && t <= *A.begin()) break;
		B.erase(prev(B.end()));
		A.insert(t);
		Sum += t;
	}
}
inline void goup(multiset<int> &A, multiset<int> &B, ll cut, ll dx) {
	for(ll x; !B.empty();) {
		x = ll(*prev(B.end())) + dx;
		if(x <= cut) break;
		x -= dx;
		B.erase(prev(B.end()));
		A.insert(x);
		Sum += x;
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> K; K = N-K;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i];

	XV.eb(-INF); XV.eb(INF);
	for(int i = 1; i <= N; i++) {
		XV.eb(A[i] - B[i]);
		XV.eb(A[i] + B[i]);
		EV.eb(A[i]-B[i], -i);
		EV.eb(A[i]+B[i], i);
	}
	sorv(XV); univ(XV);
	sorv(EV);

	if(debug) {
		for(int i = 1; i <= N; i++) printf("%d ; %d %d %d\n", i, A[i], B[i], C[i]);
		printf("XV : "); for(int v : XV) printf("%d ", v); puts("");
		printf("EV : "); for(auto &v : EV) printf("(%d,%d) ", v.x, v.idx); puts("");
		puts("");
	}

	for(int i = 1; i <= N; i++) {
		CO.insert(A[i]-B[i]+C[i]);
		SumC += A[i]-B[i];
	}
	for(int xvi = 0, evi = 0, xvn = sz(XV), evn = sz(EV); xvi < xvn; xvi++) {
		const int X = XV[xvi];
		for(int idx, t; evi < evn && EV[evi].x <= X; evi++) {
			idx = EV[evi].idx;
			if(idx < 0) {
				idx = -idx;
				t = A[idx]-B[idx]+C[idx];
				erase(CI, CO, t);
				t = C[idx];
				BO.insert(t);
				SumC -= A[idx]-B[idx];
			} else {
				t = C[idx];
				erase(BI, BO, t);
				t = -A[idx]-B[idx]+C[idx];
				AO.insert(t);
				SumA += -A[idx]-B[idx];
			}
		}
		goup(AI, AO); goup(BI, BO); goup(CI, CO);
		for(int cnt = sz(AI) + sz(BI) + sz(CI); cnt < K; cnt++) {
			ll at = (AO.empty() ? -INFLL : *prev(AO.end())) + X;
			ll bt = BO.empty() ? -INFLL : *prev(BO.end());
			ll ct = (CO.empty() ? -INFLL : *prev(CO.end())) - X;
			ll mxt = max({at, bt, ct});
			if(mxt == at) {
				at -= X;
				AI.insert(at);
				AO.erase(prev(AO.end()));
				Sum += at;
			} else if(mxt == bt) {
				BI.insert(bt);
				BO.erase(prev(BO.end()));
				Sum += bt;
			} else {
				ct += X;
				CI.insert(ct);
				CO.erase(prev(CO.end()));
				Sum += ct;
			}
		}
		{
			ll l = INFLL;
			if(!AI.empty()) upmin(l, ll(*AI.begin()) + X);
			if(!BI.empty()) upmin(l, ll(*BI.begin()));
			if(!CI.empty()) upmin(l, ll(*CI.begin()) - X);
			goup(AI, AO, l, X);
			goup(BI, BO, l, 0);
			goup(CI, CO, l, -X);
		}
		for(int cnt = sz(AI) + sz(BI) + sz(CI); K < cnt; cnt--) {
			ll at = (AI.empty() ? INFLL : *AI.begin()) + X;
			ll bt = BI.empty() ? INFLL : *BI.begin();
			ll ct = (CI.empty() ? INFLL : *CI.begin()) - X;
			ll mnt = min({at, bt, ct});
			if(mnt == at) {
				at -= X;
				AI.erase(AI.begin());
				AO.insert(at);
				Sum -= at;
			} else if(mnt == bt) {
				BI.erase(BI.begin());
				BO.insert(bt);
				Sum -= bt;
			} else {
				ct += X;
				CI.erase(CI.begin());
				CO.insert(ct);
				Sum -= ct;
			}
		}

		{
			ll ret = Sum;
			ret += ll(X) * sz(AI);
			ret -= ll(X) * sz(CI);
			ll cost = SumA + SumC;
			cost += ll(X) * (sz(AI) + sz(AO));
			cost -= ll(X) * (sz(CI) + sz(CO));
			
			ret = cost - ret;
			if(ret < Ans) Ans = ret;

			if(debug) {
				printf("X = %d, xvi=%d, evi=%d :: ret=%lld, Sum=%lld\n", X, xvi, evi, ret, Sum);
				for(int v : AO) printf("%d ", v);
				printf(" // ");
				for(int v : AI) printf("%d ", v);
				puts("");
				for(int v : BO) printf("%d ", v);
				printf(" // ");
				for(int v : BI) printf("%d ", v);
				puts("");
				for(int v : CO) printf("%d ", v);
				printf(" // ");
				for(int v : CI) printf("%d ", v);
				puts("");
				puts("");
			}
		}
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	3 ms	540 KB	Output is correct
7	Correct	3 ms	564 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	564 KB	Output is correct
2	Correct	16 ms	608 KB	Output is correct
3	Correct	53 ms	608 KB	Output is correct
4	Correct	79 ms	692 KB	Output is correct
5	Correct	116 ms	724 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	724 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	70 ms	724 KB	Output is correct
4	Correct	122 ms	724 KB	Output is correct
5	Correct	4 ms	724 KB	Output is correct
6	Correct	12 ms	724 KB	Output is correct