Submission #433508

#	Time	Username	Problem	Language	Result	Execution time	Memory
433508		frodakcin	Holiday (IOI14_holiday)	C++11	23 / 100	2972 ms	16872 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 incu()
		{
			if(0 <= u && !bench.empty())
				val += *bench.rbegin(), active.insert(*bench.rbegin()), bench.erase(std::prev(bench.end()));
			++u;
		}
		void decu()
		{
			if(0 < u && u <= active.size())
				val -= *active.begin(), bench.insert(*active.begin()), active.erase(active.begin());
			--u;
		}
		void ins(int v)
		{
			val += v;
			active.insert(v);
			if(active.size() > u)
			{
				val -= *active.begin();
				bench.insert(*active.begin());
				active.erase(active.begin());
			}
			decu();
		}
		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();
		}
};

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

	std::vector<ll> ans(start+1, -1);
	todo.push_back({0, start+1, start+1, 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;

			for(;br < l;)
				set.ins(a[br++]);
			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() {}
      |   ^~~~
holiday.cpp: In member function 'void bset::decu()':
holiday.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(0 < u && u <= active.size())
      |                ~~^~~~~~~~~~~~~~~~
holiday.cpp: In member function 'void bset::ins(int)':
holiday.cpp:45:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |    if(active.size() > u)
      |       ~~~~~~~~~~~~~~^~~
holiday.cpp: In function 'll getans(int)':
holiday.cpp:75:45: warning: narrowing conversion of 'a.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   75 |  todo.push_back({0, start+1, start+1, a.size()});
      |                                       ~~~~~~^~

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