Submission #340333

#	Time	Username	Problem	Language	Result	Execution time	Memory
340333		guka415	Feast (NOI19_feast)	C++14	100 / 100	447 ms	26852 KiB

feast

#define _CRT_SECURE_NO_WARNINGS
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int sz = 3e5 + 5;
int k, n;
ll a[sz];
map<int, pair<ll, bool>> arr; //pos, val, isNeg
set<pair<ll, pair<bool, int>>> q;//val, pos, isNeg

inline pair<int, pair<ll, bool>> qToArr(pair<ll, pair<bool, int> > x) {
	return { x.second.second, {x.first,x.second.first} };
}

inline pair<ll, pair<bool, int>> arrToQ(pair<int, pair<ll, bool>> x) {
	return { x.second.first,{x.second.second,x.first} };
}


bool fix(vector<ll>& v) {
	if (v.back() < 0)v.pop_back();
	if (v.empty())return 0;
	reverse(v.begin(), v.end());
	if (v.back() < 0)v.pop_back();
	if (v.empty())return 0;
	return 1;
}

void removeFromDS(pair<ll, pair<bool, int>> x) {
	auto y = arr.find(x.second.second), yp = y, ym = y;
	yp++;
	ym--;
	if (x.second.first) {
		ll nval = yp->second.first + ym->second.first - x.first;
		q.erase(arrToQ(*yp));
		q.erase(arrToQ(*ym));
		q.erase(x);
		q.insert({ nval,{0,x.second.second} });
		arr[x.second.second] = { nval, 0 };
		arr.erase(yp);
		arr.erase(ym);
	}
	else {
		if (ym == arr.end()) {
			q.erase(arrToQ(*yp));
			q.erase(x);
			arr.erase(yp);
			arr.erase(qToArr(x).first);
		}
		else if (yp == arr.end()) {
			q.erase(arrToQ(*ym));
			q.erase(x);
			arr.erase(ym);
			arr.erase(qToArr(x).first);
		}
		else {
			ll nval = yp->second.first + ym->second.first - x.first;
			q.erase(arrToQ(*yp));
			q.erase(arrToQ(*ym));
			q.erase(x);
			q.insert({ nval,{1,x.second.second} });
			arr[x.second.second] = { nval, 1 };
			arr.erase(yp);
			arr.erase(ym);
		}
	}

}

ll solve(vector<ll> v) {
	if (!fix(v))return 0;
	ll tot = 0;
	int vsz = v.size();
	for (int i = 0; i < vsz; i += 2) {
		tot += v[i];
	}
	foru(i, 0, vsz) {
		arr[i] = { abs(v[i]),i & 1 }; q.insert({ abs(v[i]),{i & 1,i} });
	}
	int cur = vsz / 2 + 1;
	while (cur > k) {
		auto x = *q.begin();
		tot -= x.first;
		removeFromDS(x);
		cur--;
	}
	return tot;
}

int main() {
	fast;
	arr.clear();
	q.clear();
	cin >> n >> k;
	foru(i, 0, n)cin >> a[i];
	ll ts = 0;
	bool f = 1, pos = 0;
	vector<ll> v;
	foru(i, 0, n) {
		if (f) {
			pos = (a[i] >= 0);
			ts += a[i];
			f = 0;
		}
		else {
			if ((a[i] >= 0) != (a[i - 1] >= 0)) {
				pos = !pos;
				v.pb(ts);
				ts = a[i];
			}
			else ts += a[i];
		}
	}
	v.pb(ts);
	cout << solve(v) << '\n';
	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