Submission #330795

#	Time	Username	Problem	Language	Result	Execution time	Memory
330795		ThaiBaHung	Feast (NOI19_feast)	C++14	12 / 100	54 ms	10620 KiB

feast

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
int n, k;
int a[N];
typedef pair < long long, int > ii;
vector < ii > sum;
set < int > ms;
int L[N], R[N];
long long to[N];
int cs[N];
bool vs[N];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], to[i] = to[i - 1] + a[i];

    long long cur = 0;
    int dem = 0;

    a[0] = -2e9;

    for (int i = 1; i <= n; i++)
    {
        if (a[i] < 0)
        {
            if (a[i - 1] >= 0) cs[i - 1] = dem, R[dem] = i - 1, sum.push_back({cur, dem});

            cur = 0;
            continue;
        }
        else
        {
            if (a[i - 1] < 0)
            {
                cur = a[i];
                dem++;
                L[dem] = i;
                cs[i] = dem;
            }
            else
            {
                cur += a[i];
            }
        }
    }

    if (cur > 0) sum.push_back({cur, dem}), R[dem] = n;

    sort(sum.begin(), sum.end(), greater < ii > ());

    long long res = 0;

    for (int i = 0; i < min(k, int(sum.size())); i++)
        res += sum[i].first, vs[sum[i].second] = true,
        ms.insert(L[sum[i].second]),
        ms.insert(R[sum[i].second]);

    memset(vs, false, sizeof vs);

    for (int i = k; i < sum.size(); i++)
    {
        int id = sum[i].second;
        long long val = sum[i].first;

        if (vs[id]) continue;

        auto it_low = ms.lower_bound(R[id]);
        auto it_hi = ms.lower_bound(L[id]);

        long long cur = 0;

        if (id > 1)
        {
            it_hi--;
            cur = max(cur, val + to[L[id] - 1] - to[*it_hi]);
        }
        if (id < dem && it_low != ms.end())
            cur = max(cur, val + to[*it_low - 1] - to[R[id]]);

        //cout << id << " " << *it_hi << " " << *it_low << '\n';

        if (id > 1 && cur == val + to[L[id] - 1] - to[*it_hi])
        {
            for (int t = cs[*it_hi]; t <= id; t++)
                vs[t] = true;
        }
        else
            if (id < dem && cur == val + to[*it_low - 1] - to[R[id]])
                for (int t = id; t <= cs[*it_low]; t++)
                    vs[t] = true;

        if (cur)
        {
            res += cur;
            //cout << id << " " << cur << '\n';
            ms.insert(L[id]);
            ms.insert(R[id]);
        }
    }

    cout << res;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = k; i < sum.size(); i++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29