oj.uz

Submission #476903

# Submission time Handle Problem Language Result Execution time Memory
476903 2021-09-29T02:59:26 Z Lam_lai_cuoc_doi Feast (NOI19_feast) C++17
22 / 100
 92 ms 62028 KB 
#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
{
    node st[N * 4];
    int n;

    void Build(int id, int l, int r, ll a[N])
    {
        if (l > r)
            return;
        if (l == r)
        {
            st[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]);
    }

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

    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)
        {
            st[id] = node(-Inf, l, r);
            return;
        }
        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]);
    }

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

int n, k;
ll a[N];

void Read()
{
    cin >> n >> k;

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

void Solve()
{
    f.n = 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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 61636 KB Output is correct
2 Correct 70 ms 61752 KB Output is correct
3 Correct 92 ms 61892 KB Output is correct
4 Correct 68 ms 61808 KB Output is correct
5 Correct 68 ms 61888 KB Output is correct
6 Correct 74 ms 61740 KB Output is correct
7 Correct 73 ms 61732 KB Output is correct
8 Correct 76 ms 61780 KB Output is correct
9 Correct 69 ms 61668 KB Output is correct
10 Correct 66 ms 61708 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 60040 KB Output is correct
2 Correct 65 ms 60140 KB Output is correct
3 Correct 72 ms 59952 KB Output is correct
4 Incorrect 55 ms 60024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 62012 KB Output is correct
2 Correct 70 ms 61892 KB Output is correct
3 Correct 74 ms 61876 KB Output is correct
4 Correct 88 ms 61932 KB Output is correct
5 Correct 74 ms 61880 KB Output is correct
6 Correct 80 ms 62020 KB Output is correct
7 Correct 72 ms 61932 KB Output is correct
8 Correct 92 ms 61944 KB Output is correct
9 Correct 71 ms 61992 KB Output is correct
10 Correct 81 ms 62028 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56580 KB Output is correct
2 Incorrect 25 ms 56684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56580 KB Output is correct
2 Incorrect 25 ms 56684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56580 KB Output is correct
2 Incorrect 25 ms 56684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 61636 KB Output is correct
2 Correct 70 ms 61752 KB Output is correct
3 Correct 92 ms 61892 KB Output is correct
4 Correct 68 ms 61808 KB Output is correct
5 Correct 68 ms 61888 KB Output is correct
6 Correct 74 ms 61740 KB Output is correct
7 Correct 73 ms 61732 KB Output is correct
8 Correct 76 ms 61780 KB Output is correct
9 Correct 69 ms 61668 KB Output is correct
10 Correct 66 ms 61708 KB Output is correct
11 Correct 61 ms 60040 KB Output is correct
12 Correct 65 ms 60140 KB Output is correct
13 Correct 72 ms 59952 KB Output is correct
14 Incorrect 55 ms 60024 KB Output isn't correct
15 Halted 0 ms 0 KB -