Submission #376704

#	Time	Username	Problem	Language	Result	Execution time	Memory
376704		casperwang	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	364 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define All(x) x.begin(), x.end()
#define tiiii tuple<int,int,int,int>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 200000;
int N, M;
vector <pii> arr;
vector <pii> dp;
int ans;

void solve(int L, int R, int l, int r) {
	int mid = L + R >> 1;
	priority_queue <int, vector<int>, greater<int>> val;
	int sum = arr[mid].ff + arr[mid].ss * 2;
	for (int i = mid+1; i <= r; i++) {
		val.push(arr[i].ff);
		sum += arr[i].ff;
		while (val.size()+1 > M) {
			sum -= val.top();
			val.pop();
		}
		dp[mid] = max(dp[mid], pii(sum - 2 * arr[i].ss, i));
	}
	if (mid > L)
		solve(L, mid-1, l, dp[mid].ss);
	if (mid < R)
		solve(mid+1, R, dp[mid].ss, r);
	return;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		auto &[v, c] = arr[i];
		cin >> v >> c;
	}
	dp.resize(N);
	sort(All(arr), [](const pii a, const pii b) {
		return a.ss < b.ss;
	});
	solve(0, N-1, 0, N-1);
	for (int i = 0; i < N; i++)
		ans = max(ans, dp[i].ff);
	cout << ans << '\n';
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int mid = L + R >> 1;
      |            ~~^~~
cake3.cpp:27:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |   while (val.size()+1 > M) {
      |          ~~~~~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:45:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   auto &[v, c] = arr[i];
      |         ^

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