oj.uz

Submission #433513

# Submission time Handle Problem Language Result Execution time Memory
433513 2021-06-20T02:11:40 Z frodakcin Holiday (IOI14_holiday) C++11
100 / 100
 3789 ms 15960 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 11024 KB Output is correct
2 Correct 130 ms 11008 KB Output is correct
3 Correct 135 ms 10972 KB Output is correct
4 Correct 151 ms 11020 KB Output is correct
5 Correct 157 ms 10280 KB Output is correct
6 Correct 25 ms 3552 KB Output is correct
7 Correct 66 ms 5908 KB Output is correct
8 Correct 89 ms 6880 KB Output is correct
9 Correct 17 ms 2760 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1100 KB Output is correct
2 Correct 34 ms 1136 KB Output is correct
3 Correct 36 ms 1040 KB Output is correct
4 Correct 30 ms 916 KB Output is correct
5 Correct 39 ms 972 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 10 ms 716 KB Output is correct
8 Correct 10 ms 716 KB Output is correct
9 Correct 14 ms 760 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2980 ms 15960 KB Output is correct
2 Correct 138 ms 10960 KB Output is correct
3 Correct 1099 ms 5788 KB Output is correct
4 Correct 33 ms 844 KB Output is correct
5 Correct 8 ms 716 KB Output is correct
6 Correct 9 ms 736 KB Output is correct
7 Correct 11 ms 760 KB Output is correct
8 Correct 3789 ms 10116 KB Output is correct
9 Correct 3582 ms 10192 KB Output is correct