Submission #433512

#	Time	Username	Problem	Language	Result	Execution time	Memory
433512		frodakcin	Holiday (IOI14_holiday)	C++17	47 / 100	5092 ms	12308 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<ll> ans(start+1, -1);
	for(int i=0;i<=start;++i)
	{
		bset set;
		int bl = i, br = i;
		for(;br < (int)a.size();)
		{
			set.ins(a[br++]);
			if(br > start)
				ckmax(ans[i], set.val);
		}
	}

	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());
      |                                                 ~~^~~~~~~~~~~~~~~~
holiday.cpp: In function 'll getans(int)':
holiday.cpp:88:7: warning: unused variable 'bl' [-Wunused-variable]
   88 |   int bl = i, br = i;
      |       ^~

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