Submission #222705

#	Time	Username	Problem	Language	Result	Execution time	Memory
222705		opukittpceno_hhr	Candies (JOI18_candies)	C++17	0 / 100	18 ms	384 KiB

candies

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 2001;
const int INF = 1e18 + 129;

int n;
int a[N];
int mapl[N];
int mapr[N];

int summ(int l, int r) {
	int ans = 0;
	for (int i = 0; i < r - l + 1; i++) {
		if (i & 1) {
			ans -= a[l + i];
		} else {
			// cerr << "add " << a[l + i] << endl;
			ans += a[l + i];
		}
	}
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	set<pair<int, int>> seg;
	for (int i = 1; i <= n; i++) {
		mapl[i] = i;
		mapr[i] = i;
		seg.insert({i, i});
	}
	auto ers = [&](int l, int r) {
		// cerr << "hr " << l << ' ' << r << endl;
		auto it = seg.lower_bound({l, r});
		auto prv = it;
		if (it != seg.begin()) prv--;
		auto nxt = it;
		if (it != seg.end()) nxt++;
		if (l == 1 && r == n) {
			seg.erase({l, r});
			return;
		}
		if (l == 1) {
			pair<int, int> we = *it;
			pair<int, int> next = *(nxt);
			seg.erase(we);
			seg.erase(next);
			seg.insert({l, next.second});
			return;
		}
		if (r == n) {
			pair<int, int> we = *it;
			pair<int, int> prev = *(prv);
			seg.erase(we);
			seg.erase(prev);
			seg.insert({prev.first, r});
			return;
		}
		// cerr << "full erase " << l << ' ' << r << endl;
		// cerr << "was " << seg.size() << endl;
		pair<int, int> we = *it;
		pair<int, int> next = *(nxt);
		pair<int, int> prev = *(prv);
		// cerr << we.first << ' ' << we.second << endl;
		// cerr << prev.first << ' ' << prev.second << endl;
		// cerr << next.first << ' ' << next.second << endl;
		
		seg.erase(prev);
		seg.erase(we);
		seg.erase(next);
		seg.insert({prev.first, next.second});
		// cerr << "now " << seg.size() << endl;
	};
	int curr = 0;
	vector<int> ans;
	while (!seg.empty()) {
		int mx = -INF;
		int lm = -1;
		int rm = -1;
		for (auto [l, r] : seg) {
			if (summ(l, r) > mx) {
				mx = summ(l, r);
				lm = l;
				rm = r;
			}
		}
		// cerr << "before " << seg.size() << ' ' << mx << endl;
		ers(lm, rm);
		curr += mx;
		ans.push_back(curr);
	}
	for (auto t : ans) {
		cout << t << ' ';
	}
	cout << endl;
	// cerr << summ(4, 4) << endl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92