Submission #694662

#	Time	Username	Problem	Language	Result	Execution time	Memory
694662		ghostwriter	Feast (NOI19_feast)	C++17	100 / 100	260 ms	16200 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define bg begin
#define ed end
#define ft front
#define bk back
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed()
#define mtp make_tuple
#define ins insert
#define ers erase
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return b; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const ll oo = (ll)1e18 + 5;
const int N = 3e5 + 5;
int n, k, a[N], ln[N], rn[N], cnt = 0;
ll sum[N], rs = 0;
int sign(int v) { return v < 0; }
multiset<pll> s[2];
void del(int pos) {
    if (sum[pos] >= 0) s[0].ers({sum[pos], pos});
    else s[1].ers({sum[pos], pos});
}
void add(pll v) {
    if (v.st >= 0) s[0].ins(v);
    else s[1].ins(v);
}
void del() {
    auto cur = *s[0].bg();
    int pp = ln[cur.nd], np = rn[cur.nd];
    del(cur.nd);
    del(pp);
    del(np);
    add({sum[pp] + sum[np] + cur.st, cur.nd});
    add({-oo, cur.nd});
    ln[cur.nd] = ln[pp];
    rn[cur.nd] = rn[np];
    rn[ln[cur.nd]] = cur.nd;
    ln[rn[cur.nd]] = cur.nd;
    sum[cur.nd] = sum[pp] + sum[np] + cur.st;
}
void mrg() {
    auto cur = *--s[1].ed();
    int pp = ln[cur.nd], np = rn[cur.nd];
    del(cur.nd);
    del(pp);
    del(np);
    add({sum[pp] + sum[np] + cur.st, cur.nd});
    ln[cur.nd] = ln[pp];
    rn[cur.nd] = rn[np];
    rn[ln[cur.nd]] = cur.nd;
    ln[rn[cur.nd]] = cur.nd;
    sum[cur.nd] = sum[pp] + sum[np] + cur.st;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) {
        if (!cnt && a[i] < 0) continue;
        int j = i;
        ll csum = 0;
        WHILE(j <= n && sign(a[j]) == sign(a[i])) {
            csum += a[j];
            ++j;
        }
        --j;
        if (a[i] < 0 && j == n) break;
        add({csum, ++cnt});
        ln[cnt] = cnt - 1;
        rn[cnt - 1] = cnt;
        sum[cnt] = csum;
        i = j;
    }
    ln[cnt + 1] = cnt;
    rn[cnt] = cnt + 1;
    sum[0] = sum[cnt + 1] = -oo;
    add({-oo, 0});
    add({-oo, cnt + 1});
    WHILE(!s[0].empty()) {
        if (sz(s[0]) <= k) {
            EACH(i, s[0]) rs += i.st;
            break;
        }
        if (-(*s[0].bg()).st >= (*--s[1].ed()).st) del();
        else mrg();
    }
    cout << rs;
//    cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
/*
12 2
6 -8 -10 10 -10 9 -4 3 -4 7 -4 8

*/

• 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