Submission #433513

#	Time	Username	Problem	Language	Result	Execution time	Memory
433513		frodakcin	Holiday (IOI14_holiday)	C++11	100 / 100	3789 ms	15960 KiB

holiday

#include"holiday.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
#include <algorithm>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

using ll = long long;

int D;
std::vector<int> a;

struct tbd
{
	public:
		int u, v, l, r;
};

struct bset
{
	public:
		std::multiset<int> active, bench;
		ll val;
		int u;
		bset(): val(0), u(D+1), active(), bench() {}
		void check()
		{
			assert(u < 0 || u >= (int)active.size());
			if(u < 0) assert(active.empty());
			if(u > (int)active.size()) assert(bench.empty());
			if(0 <= u && u <= (int)active.size()) assert(u == active.size());
			assert(u + (int)active.size() + (int)bench.size() == D+1);
		}
		void incu()
		{
			if(0 <= u && !bench.empty())
				val += *bench.rbegin(), active.insert(*bench.rbegin()), bench.erase(std::prev(bench.end()));
			++u;
			check();
		}
		void decu()
		{
			if(0 < u && u == (int)active.size())
				val -= *active.begin(), bench.insert(*active.begin()), active.erase(active.begin());
			--u;
			check();
		}
		void ins(int v)
		{
			val += v;
			active.insert(v);
			if((int)active.size() > u)
			{
				val -= *active.begin();
				bench.insert(*active.begin());
				active.erase(active.begin());
			}
			decu();
			check();
		}
		void rem(int v)
		{
			if(bench.find(v) != bench.end())
				bench.erase(bench.find(v));
			else
			{
				auto it=active.find(v);
				assert(it != active.end());
				val -= *it;
				active.erase(it);
				if(!bench.empty())
					val += *bench.rbegin(), active.insert(*bench.rbegin()), bench.erase(std::prev(bench.end()));
			}
			incu();
			check();
		}
};

ll getans(int start) // start is central
{
	std::vector<tbd> todo, next;

	std::vector<ll> ans(start+1, -1);
	todo.push_back({0, start+1, start+1, (int)a.size()});
	for(;!todo.empty();)
	{
		bset set;
		int bl = start+1, br = start+1;
		for(;bl>0;)
			set.ins(a[--bl]);

		for(auto x: todo)
		{
			int u=x.u, v=x.v, l=x.l, r=x.r;
			int w = (u+v)/2;

			assert(br <= l);
			for(;br < l;)
				set.ins(a[br++]);
			assert(bl <= w);
			for(;bl < w;)
				set.rem(a[bl++]);

			int m = l;
			ll bv = set.val;
			for(;br < r;)
			{
				set.ins(a[br++]);
				if(ckmax(bv, set.val))
					m=br;
			}
			ans[w] = bv;
			if(u<w) next.push_back({u, w, l, m});
			if(w+1<v) next.push_back({w+1, v, m, r});
		}

		todo.clear();
		todo.swap(next);
	}

	return *std::max_element(ans.begin(), ans.end());
}

ll findMaxAttraction(int n, int start, int d, int attraction[])
{
	D = d;
	ll ans=0;
	{ // double left
		a.clear();
		for(int i=0;i<n;++i)
		{
			a.push_back(attraction[i]);
			if(i < start)
				a.push_back(0);
		}
		ckmax(ans, getans(start*2));
	}
	{ // double right
		a.clear();
		for(int i=0;i<n;++i)
		{
			a.push_back(attraction[i]);
			if(i >= start)
				a.push_back(0);
		}
		ckmax(ans, getans(start));
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp: In constructor 'bset::bset()':
holiday.cpp:27:7: warning: 'bset::u' will be initialized after [-Wreorder]
   27 |   int u;
      |       ^
holiday.cpp:25:22: warning:   'std::multiset<int> bset::active' [-Wreorder]
   25 |   std::multiset<int> active, bench;
      |                      ^~~~~~
holiday.cpp:28:3: warning:   when initialized here [-Wreorder]
   28 |   bset(): val(0), u(D+1), active(), bench() {}
      |   ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from holiday.cpp:3:
holiday.cpp: In member function 'void bset::check()':
holiday.cpp:34:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    if(0 <= u && u <= (int)active.size()) assert(u == active.size());
      |                                                 ~~^~~~~~~~~~~~~~~~

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