Submission #476906

#	Time	Username	Problem	Language	Result	Execution time	Memory
476906		Lam_lai_cuoc_doi	Feast (NOI19_feast)	C++17	100 / 100	206 ms	118464 KiB

feast

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;

constexpr int N = 3e5 + 5;
constexpr ll Inf = 1e17;

#define Sum(x, y) ((x == -Inf || y == -Inf) ? -Inf : (x + y))

struct node
{
    ll ans, pre, suf, sum;
    int l, r, rpre, lsuf;
    node(ll v = -Inf, int x = 0, int y = 0)
    {
        ans = pre = suf = sum = v;
        l = x;
        r = y;
        rpre = y;
        lsuf = x;
    }
    friend node Combine(const node &a, const node &b)
    {
        node ans(-Inf, 0, 0);
        ans.sum = Sum(a.sum, b.sum);
        ans.pre = a.pre;
        ans.rpre = a.rpre;
        ans.suf = b.suf;
        ans.lsuf = b.lsuf;

        if (a.ans > b.ans)
        {
            ans.ans = a.ans;
            ans.l = a.l;
            ans.r = a.r;
        }
        else
        {
            ans.ans = b.ans;
            ans.l = b.l;
            ans.r = b.r;
        }

        if (ans.ans < Sum(a.suf, b.pre))
        {
            ans.ans = Sum(a.suf, b.pre);
            ans.l = a.lsuf;
            ans.r = b.rpre;
        }

        if (ans.pre < Sum(a.sum, b.pre))
        {
            ans.pre = Sum(a.sum, b.pre);
            ans.rpre = b.rpre;
        }
        if (ans.suf < Sum(a.suf, b.sum))
        {
            ans.suf = Sum(a.suf, b.sum);
            ans.lsuf = a.lsuf;
        }

        return ans;
    }
};

struct SegmentTree
{
    vector<node> st, rv;
    vector<bool> lazy;
    int n;

    SegmentTree()
    {
    }

    void Assign(int n)
    {
        this->n = n;
        st.resize(n * 4 + 2);
        rv.resize(n * 4 + 2);
        lazy.assign(n * 4 + 2, 0);
    }

    void Build(int id, int l, int r, ll a[N])
    {
        if (l == r)
        {
            st[id] = node(a[l], l, l);
            rv[id] = node(-a[l], l, l);
            return;
        }
        Build(id << 1, l, (l + r) / 2, a);
        Build(id << 1 | 1, (l + r) / 2 + 1, r, a);
        st[id] = Combine(st[id << 1], st[id << 1 | 1]);
        rv[id] = Combine(rv[id << 1], rv[id << 1 | 1]);
    }

    void Build(ll a[N])
    {
        Build(1, 1, n, a);
    }

    void Push(int id)
    {
        if (lazy[id])
        {
            swap(st[id << 1], rv[id << 1]);
            lazy[id << 1] = !lazy[id << 1];

            swap(st[id << 1 | 1], rv[id << 1 | 1]);
            lazy[id << 1 | 1] = !lazy[id << 1 | 1];

            lazy[id] = 0;
        }
    }

    void Update(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            swap(rv[id], st[id]);
            lazy[id] = !lazy[id];
            return;
        }
        Push(id);

        Update(id << 1, l, (l + r) / 2, a, b);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b);

        st[id] = Combine(st[id << 1], st[id << 1 | 1]);
        rv[id] = Combine(rv[id << 1], rv[id << 1 | 1]);
    }

    void Update(int l, int r)
    {
        Update(1, 1, n, l, r);
    }
} f;

int n, k;
ll a[N];

void Read()
{
    //freopen("test.INP", "r", stdin);
    //freopen("test.OUT", "w", stdout);
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void Solve()
{
    f.Assign(n);
    f.Build(a);

    ll ans(0);

    while (k--)
    {
        if (f.st[1].ans < 0)
            break;
        ans += f.st[1].ans;
        f.Update(f.st[1].l, f.st[1].r);
    }

    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; ++_)
    {
        //cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

feast.cpp: In function 'void read(T&)':
feast.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

• 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