제출 #486185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486185		cheissmart	Cake 3 (JOI19_cake3)	C++14	24 / 100	4083 ms	7564 KiB

cake3

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

void DBG() { cerr << "]" << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...); 
}
#define debug(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int INF = 1e9 + 7, N = 2e5 + 7;
const ll oo = 1e18 + 7;

// qry(l, r, m): sum of max m things in [l, r)

int b[N];

ll qry(int l, int r, int m) {
	assert(r - l >= m);
	ll ans = 0;
	vi tt;
	for(int i = l; i < r; i++)
		tt.PB(b[i]);
	sort(ALL(tt), greater<int>());
	for(int i = 0; i < m; i++)
		ans += tt[i];
	return ans;
}

signed main() {
	IO_OP;
	int n, m;
	cin >> n >> m;
	m -= 2;
	V<pi> a(n); // c, v
	for(int i = 0; i < n; i++) {
		cin >> a[i].S >> a[i].F;
	}	
	sort(ALL(a));
	
	for(int i = 0; i < n; i++)
		b[i] = a[i].S;
	
	auto cost = [&] (int j, int i) {
		if(i - j - 1 < m) return -oo;
		return 0LL + 2 * a[j].F - 2 * a[i].F + a[i].S + a[j].S + qry(j + 1, i, m);
	};
	
	ll ans = -oo;
	
	function<void(int, int, int, int)> solve = [&] (int l, int r, int ql, int qr) {
		if(l > r)
			return;
		if(r == l) {
			for(int i = ql; i <= qr; i++)
				ans = max(ans, cost(i, l));
			return;
		}
		int m = (l + r) / 2;
		ll mx = -oo, qm = -1;
		for(int i = ql; i <= qr; i++) {
			ll tt = cost(i, m);
			if(tt > mx) {
				mx = tt;
				qm = i;
			}
		}
		assert(qm != -1);
		ans = max(ans, mx);
		solve(l, m - 1, ql, qm);
		solve(m + 1, r, qm, qr);
	};
	solve(m + 1, n - 1, 0, n - 1);

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

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76