Submission #797376

#	Time	Username	Problem	Language	Result	Execution time	Memory
797376		Sohsoh84	Holiday (IOI14_holiday)	C++17	100 / 100	1053 ms	17240 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

typedef long long ll;

#define debug(x)	cerr << #x << ": " << x << endl;
#define sep		' '

const int MAXN = 2e5 + 10;

using namespace std;

ll A[MAXN], n;

namespace sack {
	ll score = 0;
	int len, d;
	multiset<int> st;
	vector<pair<int,  vector<int>>> history;

	inline void init(int d_) {
		d = d_;
		st.clear();
		history.clear();
	}

	inline void add(int x) {
		len++;
		vector<int> er_vec;
		
		st.insert(x);
		score += x;

		while (int(st.size()) > max(0, d - len + 1)) {
			er_vec.push_back(*st.begin());	
			score -= *st.begin();
			st.erase(st.begin());
		}

		history.push_back({x, er_vec});
	}

	inline void rollback() {
		len--;
		auto [x, y] = history.back();
		history.pop_back();

		for (int e : y) {
			st.insert(e);
			score += e;
		}

		st.erase(st.find(x));
		score -= x;
	}

	inline void rollback(int k) {
		while (k--) rollback();
	}
}

ll divide(int l, int r, int optl, int optr) { // (r, optl]
	if (r < l) return 0;

	int mid = (l + r) >> 1;
	for (int i = r; i >= mid; i--) sack::add(A[i]);

	ll ans = sack::score, opt = optl;
	for (int i = optl + 1; i <= optr; i++) {
		sack::add(A[i]);
		if (sack::score > ans) {
			ans = sack::score;
			opt = i;
		}
	}

	sack::rollback(optr - optl);
	ans = max(ans, divide(l, mid - 1, optl, opt));
	sack::rollback(r - mid + 1);
	for (int i = optl + 1; i <= opt; i++) sack::add(A[i]);
	ans = max(ans, divide(mid + 1, r, opt, optr));
	sack::rollback(opt - optl);

	return ans;

}

inline ll solve(int n_, int start, int d, int attraction[]) {
	memset(A, 0, sizeof A);
	n = 0;

	for (int i = 0; i < n_; i++) {
		if (i > start) A[n++] = 0;
		A[n++] = attraction[i];
	}

	sack::init(d);
	return divide(max(0, start - d), start, start, min(ll(start + d), n - 1));
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	ll ans = solve(n, start, d, attraction);
	reverse(attraction, attraction + n);
	ans = max(ans, solve(n, n - 1 - start, d, attraction));
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53