Submission #923522

#	Time	Username	Problem	Language	Result	Execution time	Memory
923522		danikoynov	Cake 3 (JOI19_cake3)	C++14	24 / 100	4099 ms	59940 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;

int n, m;
pair < int, int > a[maxn];
void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i].first >> a[i].second;
    }
}

bool cmp_second(pair < int, int > f, pair < int, int > s)
{
    return f.second < s.second;
}
ll inf = 1e18;

struct block
{
    vector < ll > to_left, to_right;

    void init(int idx)
    {
        to_left.resize(2);
        to_right.resize(2);
        to_left[0] = -inf;
        to_left[1] = a[idx].first + 2 * a[idx].second;
        to_right[0] = -inf;
        to_right[1] = a[idx].first - 2 * a[idx].second;
    }
};

block tree[4 * maxn];
ll result;

void conquer(int t, int l, int r)
{
    int len = r - l + 1;
    if (len >= m)
    {
        for (int i = 1; i <= m; i ++)
        {
            if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
            {
                ll sum = tree[t * 2].to_left[i] + tree[t * 2 + 1].to_right[m - i];
                if (sum > result)
                {
                    //cout << l << " : " << r << " " << sum << endl;
                    result = sum;
                }
            }
        }
    }

    vector < ll > lf_val, rf_val;
    int mid = (l + r) / 2;
    for (int i = l; i <= mid; i ++)
        lf_val.push_back(a[i].first);
    for (int i = mid + 1; i <= r; i ++)
        rf_val.push_back(a[i].first);

    sort(lf_val.begin(), lf_val.end());
    reverse(lf_val.begin(), lf_val.end());

    sort(rf_val.begin(), rf_val.end());
    reverse(rf_val.begin(), rf_val.end());

    lf_val.insert(lf_val.begin(), (ll)0);
    rf_val.insert(rf_val.begin(), (ll)0);

    for (int i = 1; i < lf_val.size(); i ++)
        lf_val[i] += lf_val[i - 1];

    for (int i = 1; i < rf_val.size(); i ++)
        rf_val[i] += rf_val[i - 1];


    tree[t].to_left.resize(r - l + 2, -inf);
    for (int i = 1; i < tree[t * 2].to_left.size(); i ++)
        tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[i]);

    for (int i = 1; i < tree[t * 2 + 1].to_left.size(); i ++)
        tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2 + 1].to_left[i]);
    //cout << "--------------------" << endl;
    //cout << "range " << l << " " << r << endl;
    for (int i = 1; i <= len; i ++)
    {
        for (int j = 1; j <= min((int)(tree[t * 2].to_left.size() - 1), i); j ++ )
        {

            if (i - j < rf_val.size())
                tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[j] + rf_val[i - j]);
        }
    }

    tree[t].to_right.resize(r - l + 2, -inf);
    for (int i = 1; i < tree[t * 2].to_right.size(); i ++)
        tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2].to_right[i]);

    for (int i = 1; i < tree[t * 2 + 1].to_right.size(); i ++)
        tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[i]);

    for (int i = 1; i <= len; i ++)
    {
        for (int j = 1; j <= min((int)tree[t * 2 + 1].to_right.size() - 1, i); j ++)
        {
            if (i - j < lf_val.size())
                tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[j] + lf_val[i - j]);
        }
    }


    //for (int i = 0; i < tree[t].to_left.size(); i ++)
    //    cout << tree[t].to_right[i] << " ";
    //cout << endl;

}
void  divide(int t, int l, int r)
{
    if (l == r)
    {
        tree[t].init(l);
        if (m == 1)
            result = max(result, (ll)a[l].first);
        return;
    }

    int mid = (l + r) / 2;
    divide(t * 2, l, mid);
    divide(t * 2 + 1, mid + 1, r);

    conquer(t, l, r);
}
void do_math()
{
    sort(a + 1, a + n + 1, cmp_second);
    result = -inf;
    divide(1, 1, n);
    cout << result << endl;
}
void solve()
{
    input();
    do_math();
}

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

Compilation message (stderr)

cake3.cpp: In function 'void conquer(int, int, int)':
cake3.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:66:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
      |                                                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 1; i < lf_val.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
cake3.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i < rf_val.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
cake3.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < tree[t * 2].to_left.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 1; i < tree[t * 2 + 1].to_left.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             if (i - j < rf_val.size())
      |                 ~~~~~~^~~~~~~~~~~~~~~
cake3.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 1; i < tree[t * 2].to_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 1; i < tree[t * 2 + 1].to_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             if (i - j < lf_val.size())
      |                 ~~~~~~^~~~~~~~~~~~~~~

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