Submission #549203

#	Time	Username	Problem	Language	Result	Execution time	Memory
549203		d2k05	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	340 KiB

cake3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 5;

int n, m;
pair <ll, ll> a[N];

int main() {
	ios :: sync_with_stdio(0), cin.tie(0);
	cin >> n >> m; --m;
	for (int i = 1; i <= n; ++i) cin >> a[i].second >> a[i].first;
	sort(a + 1, a + 1 + n);
	ll ans = 0, sum = 0;
	set <pair <int, int> > st;
	set <ll> br;
	set <int> lmao;
	for (int i = 1; i <= n; ++i) {
		if (st.size() == m) {
			ans = max(ans, sum + a[i].second - 2 * a[i].first + 2 * (*lmao.begin()));	
		//	if (!br.empty()) 
			//	ans = max(ans, sum + a[i].second - 2 * a[i].first + *(--br.end()) - st.begin() -> first);
		}
		if (st.size() < m) lmao.insert(a[i].first), st.insert({a[i].second, i}), sum += a[i].second;
		else if (st.size() == m) {
			if (a[i].second > st.begin() -> first) {
				int j = st.begin() -> second;
				lmao.erase(a[j].first);
				br.insert(2 * a[j].first + a[j].second);
				sum -= a[j].second;
				st.erase(st.begin());
				lmao.insert(a[i].first);
				st.insert({a[i].second, i}); sum += a[i].second;
			} 
			else br.insert(2 * a[i].first + a[i].second);
		}
		else br.insert(2 * a[i].first + a[i].second);
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:21:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |   if (st.size() == m) {
      |       ~~~~~~~~~~^~~~
cake3.cpp:26:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if (st.size() < m) lmao.insert(a[i].first), st.insert({a[i].second, i}), sum += a[i].second;
      |       ~~~~~~~~~~^~~
cake3.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   else if (st.size() == m) {
      |            ~~~~~~~~~~^~~~

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