Submission #638330

#	Time	Username	Problem	Language	Result	Execution time	Memory
638330		shmad	Feast (NOI19_feast)	C++17	12 / 100	189 ms	12140 KiB

feast

#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

//#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvt = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;

int n, k, l[N], r[N];
ll a[N], b[N];

void solve () {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int m = 0;
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			b[++m] = a[i];
			continue;
		}
		if ((a[i] > 0 && b[m] > 0) || (a[i] < 0 && b[m] < 0)) b[m] += a[i];
		else b[++m] = a[i];
	}
	if (b[m] < 0) b[m--] = 0;
	multiset<pii> s;
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		s.insert({abs(b[i]), i});
		l[i] = i - 1;
		r[i] = i + 1;
		cnt += (b[i] > 0);    
	}
	r[m] = 0;
	while (!s.empty() && cnt > k) {
		pii v = *s.begin();
		s.erase(s.begin());
		int val = v.ff, i = v.ss;
		if (b[i] > 0) cnt--;
		if (l[i] != 0) {
			s.erase({abs(b[l[i]]), l[i]});
			if (b[l[i]] > 0) cnt--;
			b[i] += b[l[i]];
		    l[i] = l[l[i]];
		    if (l[i] != 0) r[l[i]] = i;
		}
		if (r[i] != 0) {
			s.erase({abs(b[r[i]]), r[i]});
			if (b[r[i]] > 0) cnt--;
			b[i] += b[r[i]];
			r[i] = r[r[i]];
			if (r[i] != 0) l[r[i]] = i;
		}
		if (b[i] > 0) {
			s.insert({abs(b[i]), i});
			cnt++;
			continue;
		}
		if (l[i] == 0) l[r[i]] = 0;
		else if (r[i] == 0) r[l[i]] = 0;		
		else s.insert({abs(b[i]), i});
	}
	ll ans = 0;
	for (auto [val, i]: s) if (b[i] > 0) ans += b[i];
	cout << ans;
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:53:7: warning: unused variable 'val' [-Wunused-variable]
   53 |   int val = v.ff, i = v.ss;
      |       ^~~

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