Submission #263245

#	Time	Username	Problem	Language	Result	Execution time	Memory
263245		keko37	Cake 3 (JOI19_cake3)	C++14	24 / 100	4073 ms	9848 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 200005;
const llint INF = 1000000000000000000LL;

llint n, m, sum, sol = -INF;
pi p[MAXN];
multiset <llint> st;
vector <int> v;

bool cmp (pi a, pi b) {
    return a.second < b.second;
}

void init () {
    st.clear();
    sum = 0;
}

void ubaci (llint val) {
    st.insert(val);
    sum += val;
    if (st.size() > m - 2) {
        sum -= *st.begin();
        st.erase(st.begin());
    }
}

llint calc (int j) {
    init();
    llint res = -INF;
    int ind = -1;
    for (int i = j - 1; i >= 0; i--) {
        if (st.size() == m - 2) {
            llint tmp = sum + p[i].first + p[i].second;
            if (tmp > res) {
                res = tmp;
                ind = i;
            }
        }
        ubaci(p[i].first);
    }
    //cout << "bla " << ind << " " << j << "  " << res << endl;
    v.push_back(ind);
    return res;
}

bool check () {
    for (int i = 1; i < v.size(); i++) {
        if (v[i] < v[i - 1]) return 0;
    }
    return 1;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        p[i].second *= 2;
    }
    sort(p, p + n, cmp);
    for (int j = m - 1; j < n; j++) {
        sol = max(sol, calc(j) + p[j].first - p[j].second);
    }
    cout << sol;
    if (!check()) cout << "RIP";
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void ubaci(llint)':
cake3.cpp:28:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'llint' {aka 'long long int'} [-Wsign-compare]
   28 |     if (st.size() > m - 2) {
      |         ~~~~~~~~~~^~~~~~~
cake3.cpp: In function 'llint calc(int)':
cake3.cpp:39:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'llint' {aka 'long long int'} [-Wsign-compare]
   39 |         if (st.size() == m - 2) {
      |             ~~~~~~~~~~^~~~~~~~
cake3.cpp: In function 'bool check()':
cake3.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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