Submission #1101114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101114		trie	Feast (NOI19_feast)	C++17	100 / 100	270 ms	23200 KiB

feast

#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;

template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}

template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}

const int N = 2005;
const int V = 3e5 + 5;
const int MOD = 1e9 + 7;

int n, k, a[V], pos;
pli sum = mp(0, 1);
set<pli> Q;
set<int> s;
ll cost[V], ans;

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

    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        if (i == 1 || (sum.fi < 0 && a[i] < 0) || (sum.fi >= 0 && a[i] >= 0)) sum.fi += a[i];
        else {
            if (sum.se > 1 || sum.fi >= 0) {
                cost[sum.se] = sum.fi;
                if (sum.fi >= 0) pos++;
                sum.fi = abs(sum.fi);
                Q.insert(sum);
                s.insert(sum.se);
            }
            sum = mp(a[i], i);
        }
    }

    if (sum.fi >= 0) {
        pos++;
        cost[sum.se] = sum.fi;
        Q.insert(sum);
        s.insert(sum.se);
    }

    while((int) pos > k) {
        pli x = *Q.begin();
        auto u = s.lower_bound(x.se), v = u;
        ++v;
        if (cost[x.se] < 0 && (u == s.begin() || v == s.end())) {
            s.erase(u);
            Q.erase(Q.begin());
            continue;
        }
        int re[2] = {0, 0};
        if (cost[x.se] >= 0) --pos;
        if (u != s.begin()) {
            --u;
            cost[x.se] += cost[*u];
            re[0] = *u;
        }
        if (v != s.end()) {
            cost[x.se] += cost[*v];
            re[1] = *v;
        }
        Q.erase(Q.begin());
        for(int j = 0 ; j < 2 ; j++) if (re[j]) {
            if (cost[re[j]] >= 0) --pos;
            s.erase(re[j]);
            auto it = Q.find(pli(abs(cost[re[j]]), re[j]));
            if (it != Q.end()) Q.erase(it);
        }
        Q.insert(mp(abs(cost[x.se]), x.se));
        if (cost[x.se] >= 0) ++pos;
    }

    while((int) Q.size()) {
        pli x = *Q.begin();
        Q.erase(Q.begin());
        if (cost[x.se] >= 0) ans += cost[x.se];
    } cout << ans;
}

int main(void) {
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int t = 1; while(t--) solve();
    return 0;
}

• 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