Submission #248880

#	Time	Username	Problem	Language	Result	Execution time	Memory
248880		SamAnd	Feast (NOI19_feast)	C++17	100 / 100	834 ms	32248 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006;

int n, k;
int a[N];

struct ban
{
    int x;
    ll s;
    ban(){}
    ban(int x, ll s)
    {
        this->x = x;
        this->s = s;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (abs(a.s) < abs(b.s))
        return true;
    if (abs(a.s) > abs(b.s))
        return false;
    return a.x < b.x;
}
int dq;
set<ban> t;

int p[N];
int l[N], r[N];
ll s[N];
int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}
void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);

    t.erase(ban(x, s[x]));
    t.erase(ban(y, s[y]));
    if (s[x] > 0)
        --dq;
    if (s[y] > 0)
        --dq;
    p[x] = y;
    l[y] = min(l[x], l[y]);
    r[y] = max(r[x], r[y]);
    s[y] += s[x];
    if (s[y] > 0)
        ++dq;
    t.insert(ban(y, s[y]));
}

void solv()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i)
    {
        p[i] = i;
        l[i] = r[i] = i;
        s[i] = a[i];
        t.insert(ban(i, s[i]));
        if (s[i] > 0)
            ++dq;
    }
    for (int i = 1; i <= n; ++i)
    {
        int x = fi(i);
        if (s[x] > 0 && r[x] < n && s[fi(r[x] + 1)] > 0)
        {
            kpc(x, r[x] + 1);
        }
        if (s[x] < 0 && r[x] < n && s[fi(r[x] + 1)] < 0)
        {
            kpc(x, r[x] + 1);
        }
    }

    while (dq > k)
    {
        int x = t.begin()->x;
        if (s[x] < 0)
        {
            if (l[x] == 1 || r[x] == n)
            {
                t.erase(ban(x, s[x]));
                continue;
            }
        }
        if (l[x] > 1)
        {
            kpc(x, l[x] - 1);
            x = fi(x);
        }
        if (r[x] < n)
        {
            kpc(x, r[x] + 1);
            x = fi(x);
        }
    }

    ll ans = 0;
    for (auto it = t.begin(); it != t.end(); ++it)
    {
        if (it->s > 0)
            ans += it->s;
    }
    printf("%lld\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

feast.cpp: In function 'void solv()':
feast.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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