Submission #869375

#	Time	Username	Problem	Language	Result	Execution time	Memory
869375		browntoad	Cake 3 (JOI19_cake3)	C++14	24 / 100	4043 ms	18516 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second

const ll maxn = 5e5+5;
const ll inf = (1ll<<60);
const ll mod = 1000992299;

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

bool cmp(pii a, pii b){
    return a.s < b.s;
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m; cin>>n>>m;
    vector<pii> vc(n);
    REP(i, n) cin>>vc[i].f>>vc[i].s;
    sort(ALL(vc), cmp);
    int ans = -inf;
    REP(i, n){
        pbds_set<pii> toad;
        int burr = 0;
        FOR(j, i+1, n){
            if (SZ(toad) < m-2){
                toad.insert({-vc[j].f, j});
                burr += vc[j].f;
                continue;
            }  
            ans = max(ans, (burr+vc[i].f+vc[j].f)-2*(vc[j].s-vc[i].s));
            pii poo = *toad.find_by_order(m-3);
            toad.insert({-vc[j].f, j});
            pii np = *toad.find_by_order(m-3);
            if (np.s != poo.s){
                burr += poo.f;
                burr += vc[j].f;
            }
        }
    }
    cout<<ans<<endl;
}

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