Submission #836815

#	Time	Username	Problem	Language	Result	Execution time	Memory
836815		Ozy	Cake 3 (JOI19_cake3)	C++17	24 / 100	124 ms	724 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define pll pair<lli,lli>

#define MAX 2000
//para el arreglo de orden
#define tono first
#define val second

lli n,a,b,res,sum,m;
pll arr[MAX+2];
multiset<lli> mejores; // de grande a chico

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    rep(i,1,n) cin >> arr[i].val >> arr[i].tono;

    res = -(1ll<<60);
    sort(arr+1,arr+n+1);
    rep(ini,1,n-m+1) {

        //debug(arr[ini].tono);

        mejores.clear();
        sum = 0;

        rep(fin,ini,n) {
            mejores.insert(arr[fin].val);
            sum += arr[fin].val;
            if (mejores.size() > m) {
                auto it = mejores.begin();
                sum -= (*it);
                mejores.erase(it);
            }

            if (mejores.size() == m) {
                a = (arr[fin].tono-arr[ini].tono)*2;
                a = sum - a;
                res = max(res,a);
            }
        }
    }

    cout << res;
    return 0;  
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:38:32: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |             if (mejores.size() > m) {
      |                 ~~~~~~~~~~~~~~~^~~
cake3.cpp:44:32: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |             if (mejores.size() == m) {
      |                 ~~~~~~~~~~~~~~~^~~~

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