Submission #104733

#	Time	Username	Problem	Language	Result	Execution time	Memory
104733		antimirage	Cake 3 (JOI19_cake3)	C++14	24 / 100	298 ms	512 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2005;

int n, m;

long long ans = -1e18;

pair <int, int> a[N];

multiset <int> st;

main(){
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].sc, &a[i].fr);
		
	sort(a + 1, a + n + 1);
	
	for (int i = 1; i <= n; i++){
		
		long long sum = 0;
		
		st.clear();
		
		for (int j = i; j <= n; j++){
			
			if ((int)st.size() < m)
				sum += a[j].sc,
				st.insert( a[j].sc );
			
			else if (*st.begin() < a[j].sc){
				
				sum -= *st.begin();
				st.erase(st.begin());
				sum += a[j].sc;
				st.insert( a[j].sc ); 
			}
				
			if ((int)st.size() == m) 
				ans = max(ans, sum - (a[j].fr - a[i].fr) * 2);
		}
	}
	cout << ans << endl;
}
/**
5 3
2 1
4 2
6 4
8 8
10 16
 **/

Compilation message (stderr)

cake3.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].sc, &a[i].fr);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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