Submission #923619

#	Time	Username	Problem	Language	Result	Execution time	Memory
923619		danikoynov	Cake 3 (JOI19_cake3)	C++14	24 / 100	4008 ms	8776 KiB

cake3

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

struct element
{
    ll v, s, idx;

    element(ll _v = 0, ll _s = 0, ll _idx = 0)
    {
        v = _v;
        s = _s;
        idx = _idx;
    }
}e[maxn];
int n, m;

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> e[i].v >> e[i].s;
        e[i].s *= 2;
        e[i].idx = i;
    }
}

bool cmp_second(element e1, element e2)
{
    return e1.s < e2.s;
}
ll inf = 1e18;


ll result;

ll dp[maxn];

ll cost(int left, int right)
{
    //cout << "cost " << left << " " << right << endl;
    vector < ll > values;
    for (int i = left; i <= right; i ++)
        values.push_back(e[i].v);

    sort(values.begin(), values.end());

    ll res = 0;
    for (int i = (int)(values.size()) - 1; i >= (int)(values.size()) - m; i --)
        res += values[i];

        //exit(0);
    return res;
}

void divide(int l, int r, int optl, int optr)
{
    if (l > r)
        return;

    ///cout << l << " " << r << " " << optl << " " << optr << endl;
    int mid = max(optl + m - 1, (l + r) / 2), opt = -1;
    if (mid > r)
        return;

    for (int i = optl; i <= min(optr, mid); i ++)
    {
        ///cout << "check " << mid << " " << i << endl;
        if (mid - i + 1 >= m)
        {
            ll sum = - e[mid].s + e[i].s + cost(i, mid);
            ///cout << "alive " << " " << sum << endl;
            if (sum > dp[mid])
            {
                dp[mid ] = sum;
                opt = i;
            }
        }
    }


    //cout << "pos " << mid << " " << opt << endl;

    divide(l, mid - 1, optl, opt);
    divide(mid + 1, r, opt, optr);

}

void print()
{
    ll best = -inf;
    for (int i = 1; i <= n; i ++)
        best = max(best, dp[i]);
    cout << best << endl;
}
void solve()
{
    input();
    sort(e + 1, e + n + 1, cmp_second);
    for (int i = 1; i <= n; i ++)
        dp[i] = -inf;
    divide(1, n, 1, n);
    print();
}

int main()
{
    solve();
    return 0;
}

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