Submission #362711

#	Time	Username	Problem	Language	Result	Execution time	Memory
362711		hoaphat1	Holiday (IOI14_holiday)	C++17	30 / 100	100 ms	9432 KiB

holiday

#include<bits/stdc++.h>
 
using namespace std;

long long findMaxAttraction(int n, int s, int d, int a[]) {
	long long ans = 0;
	long long now = 0;
  int L = 0, R = -1;
  vector<int> kt(n, 0);
  priority_queue<pair<int, int>, vector<pair<int,int>> , greater<pair<int, int>>> pq;
  priority_queue<pair<int, int>> smaller;
  int sz = 0;
  auto make_true = [&](int m) {
  	while (sz > m) {
  		auto x = pq.top();
  		pq.pop();
  		if (kt[x.second] != 1) continue;
  		kt[x.second] = 2;
  		now -= x.first;
  		smaller.push(x);
  		--sz;
		}
		while (sz < m && !smaller.empty()) {
			auto x = smaller.top(); smaller.pop();
			if (kt[x.second] != 2) continue;
			kt[x.second] = 1;
			now += x.first;
			pq.push(x);
			++sz;
		}
	};
  auto add = [&](int id) {
  	int v = a[id];
  	pq.emplace(v, id);
  	now += v;
  	kt[id] = 1;
  	++sz;
	};
	auto del = [&](int id) {
		int v = a[id];
		if (kt[id] == 2) {
			kt[id] = 0;
			return ;
		}
		kt[id] = 0;
		now -= v;
		sz--;
	};
  auto moveL = [&](int l) {
  	while (L < l) del(L++);
  	while (L > l) add(--L);
	};
	auto moveR = [&](int r) {
		while (R < r) add(++R);
		while (R > r) del(R--);
	};
	function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
		if (l > r) return ;
		int mid = l + r >> 1;
		int pos = L;
		moveR(L);
		moveL(mid);
		long long val = -1;
		for (int i = L; i <= R; i++) {
			moveR(i);
			int lim = d - min(s - mid, i - s) - (i - mid);
			if (lim <= 0) break;
			make_true(lim);
			if (val < now) {
				val = now;
				pos = i;
			}
		}
		ans = max(ans, val);
		solve(mid + 1, r, pos, R);
		solve(l, mid - 1, L, pos);
	};
	solve(max(0, s - d), s, s, min(n - 1, s + d));
	return ans;
}

Compilation message (stderr)

holiday.cpp: In lambda function:
holiday.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid = l + r >> 1;
      |             ~~^~~

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