Submission #1265045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265045		tvgk	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	328 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;
const ll inf = 1e18;

bool dd[mxN];
int n, k;
ll sum;
ii a[mxN], tree[mxN * 4][2];
set<int> s;
priority_queue<ii, vector<ii>, greater<ii>> pq;

void Upd(int vt, bool tt, int j = 1, int l = 1, int r = n)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        tree[j][1] = {a[l].se * tt, l};
        tree[j][0] = {(a[l].se + a[l].fi) * tt, l};
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, tt, j * 2, l, mid);
    Upd(vt, tt, j * 2 + 1, mid + 1, r);
    tree[j][0] = max(tree[j * 2][0], tree[j * 2 + 1][0]);
    tree[j][1] = max(tree[j * 2][1], tree[j * 2 + 1][1]);
}

ii Get(int vt, int j = 1, int l = 1, int r = n)
{
    if (r < vt)
        return tree[j][0];

    if (l >= vt)
    {
        if (tree[j][1].fi)
            return {tree[j][1].fi + a[vt].fi * 2, tree[j][1].se};
        else
            return tree[j][1];
    }

    int mid = (l + r) / 2;
    return max(Get(vt, j * 2, l, mid), Get(vt, j * 2 + 1, mid + 1, r));
}

void Add(int j)
{
    dd[j] = 1;
    pq.push({a[j].se, j});
    Upd(j, 0);
    s.insert(j);
    sum += a[j].se;
}

void Rem(int j)
{
    dd[j] = 0;
    Upd(j, 1);
    s.erase(j);
    sum -= a[j].se;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i].se >> a[i].fi;
    sort(a + 1, a + n + 1);

    for (int i = 1; i < k; i++)
        Add(i);

    ll ans = -inf;
    for (int i = k; i <= n; i++)
    {
        Add(i);
        ans = max(ans, sum - (a[i].fi - a[*s.begin()].fi) * 2);
        
        while (pq.size())
        {
            int j = pq.top().se;
            pq.pop();

            if (!dd[j])
                continue;

            Rem(j);
            break;
        }

        while (1)
        {
            int nxt = *s.upper_bound(*s.begin());
            ii j = Get(nxt);

            if (j.fi > a[*s.begin()].se + a[*s.begin()].fi * 2)
            {
                Rem(*s.begin());
                Add(j.se);
            }
            else
                break;
        }
    }
    cout << ans;
}

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