oj.uz

Submission #549203

# Submission time Handle Problem Language Result Execution time Memory
549203 2022-04-15T12:02:02 Z d2k05 Cake 3 (JOI19_cake3) C++14
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -