Submission #376685

#	Time	Username	Problem	Language	Result	Execution time	Memory
376685		wiwiho	Cake 3 (JOI19_cake3)	C++14	24 / 100	4050 ms	6268 KiB

cake3

#include<bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}

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

    int n, m;
    cin >> n >> m;

    vector<pll> a(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> a[i].S >> a[i].F;
    }

    lsort(a);
    //printv(a, cerr);

    ll ans = -(1LL << 60);
    for(int i = 1; i <= n; i++){
        multiset<ll> st;
        ll sum = 0;
        
        for(int j = i; j <= n; j++){
            ll c = a[j].F, v = a[j].S;
            sum += v;
            st.insert(v);
            while(st.size() > m){
                sum -= *st.begin();
                st.erase(st.begin());
            }
            //cerr << i << " " << j << "  ";
            //printv(st, cerr);
            if(st.size() == m) ans = max(ans, sum - 2 * (c - a[i].F));
        }
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:48:29: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |             while(st.size() > m){
      |                   ~~~~~~~~~~^~~
cake3.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |             if(st.size() == m) ans = max(ans, sum - 2 * (c - a[i].F));
      |                ~~~~~~~~~~^~~~

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