Submission #362909

#	Time	Username	Problem	Language	Result	Execution time	Memory
362909		Lam_lai_cuoc_doi	Cake 3 (JOI19_cake3)	C++17	100 / 100	3108 ms	19948 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 2e5 + 5;
const ll Inf = 1e17;
struct Pakage
{
    int c;
    ll v;
    bool operator<(const Pakage &a) const
    {
        return c < a.c;
    }
} a[N];
int n, m, id[N], now[N];
ll dp[N], ans(0);
struct node
{
    int v;
    ll sum;
    node()
    {
        v = sum = 0;
    }
    void combine(const node &a, const node &b)
    {
        v = a.v + b.v;
        sum = a.sum + b.sum;
    }
};
struct SegmentTree
{
    node st[N * 4];
    bool ck[N];
    SegmentTree()
    {
        memset(ck, 0, sizeof ck);
    }
    void Update(int id, int l, int r, int pos, ll v)
    {
        if (l > pos || r < pos)
            return;
        if (l == pos && l == r)
        {
            st[id].v ^= 1;
            st[id].sum += v;
            return;
        }
        Update(id << 1, l, (l + r) / 2, pos, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, pos, v);
        st[id].combine(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int v)
    {
        Update(1, 1, n, v, (ck[v] ? -1 : 1) * a[id[v]].v);
        ck[v] ^= 1;
    }
    ll Get(int id, int l, int r, int d)
    {
        if (l == r)
            return st[id].sum;
        if (st[id << 1].v >= d)
            return Get(id << 1, l, (l + r) / 2, d);
        else
            return st[id << 1].sum + Get(id << 1 | 1, (l + r) / 2 + 1, r, d - st[id << 1].v);
    }
    ll Get(int d)
    {
        if (d <= 0)
            return 0;
        return Get(1, 1, n, d);
    }
} f;

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].v >> a[i].c;
        id[i] = i;
    }
    sort(a + 1, a + n + 1);
    sort(id + 1, id + n + 1, [&](const int &x, const int &y) {
        return a[x].v > a[y].v;
    });
}

template <class T>
void Max(T &x, const T &y)
{
    if (x < y)
        x = y;
}

void DAC(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    int mid = (l + r) / 2, optmid(-1);
    for (int i = r; i >= mid; --i)
        f.Update(now[i]);
    for (int i = optl; i <= optr && i < mid - (m - 2); ++i)
    {
        f.Update(now[i]);
        ll v = f.Get(m - 2);
        if (dp[mid] < a[mid].v - 2 * a[mid].c + a[i].v + 2 * a[i].c + v)
        {
            dp[mid] = a[mid].v - 2 * a[mid].c + a[i].v + 2 * a[i].c + v;
            optmid = i;
        }
    }
    Max(ans, dp[mid]);
    if (optmid != -1)
    {
        for (int i = optl; i <= optr && i < mid - (m - 2); ++i)
            f.Update(now[i]);
        DAC(l, mid - 1, optl, optmid);
        for (int i = r; i >= mid; --i)
            f.Update(now[i]);
        for (int i = optl; i < optmid; ++i)
            f.Update(now[i]);
        DAC(mid + 1, r, optmid, optr);
        for (int i = optl; i < optmid; ++i)
            f.Update(now[i]);
    }
    else
    {
        for (int i = r; i >= mid; --i)
            f.Update(now[i]);
        DAC(mid + 1, r, optl, optr);
    }
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        now[id[i]] = i,
        f.Update(i);
    fill_n(dp, N, -Inf);
    ans = -Inf;
    DAC(1, n, 1, n);
    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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