Submission #376837

#	Time	Username	Problem	Language	Result	Execution time	Memory
376837		wiwiho	Cake 3 (JOI19_cake3)	C++14	24 / 100	3856 ms	11628 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 << ')';
}

pll operator+(pll a, pll b){
    return mp(a.F + b.F, a.S + b.S);
}

const ll MAX = 1LL << 60;

ll solve(int n, int m, vector<pll>& a, int i){
    //cerr << "solve " << i << "\n";

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

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

    int t1 = clock();
    mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());
 
    int n, m;
    cin >> n >> m;
    uniform_int_distribution<int> ud(1, n - m + 1);
 
    vector<pll> a(n + 1);
 
    for(int i = 1; i <= n; i++){
        cin >> a[i].S >> a[i].F;
        //a[i].S = rand() % 1000;
        //a[i].F = rand() % 1000;
    }
 
    lsort(a);

    ll ans = -MAX;
    while(clock() - t1 < CLOCKS_PER_SEC * 3.8){
        int i = ud(rnd);
        ans = max(ans, solve(n, m, a, i));
    }
    cout << ans << "\n";
 
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'll solve(int, int, std::vector<std::pair<long long int, long long int> >&, int)':
cake3.cpp:42:25: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         while(st.size() > m){
      |               ~~~~~~~~~~^~~
cake3.cpp:51:22: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         if(st.size() == m){
      |            ~~~~~~~~~~^~~~
cake3.cpp:38:12: warning: unused variable 'c' [-Wunused-variable]
   38 |         ll c = a[j].F, v = a[j].S;
      |            ^

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