Submission #250416

#	Time	Username	Problem	Language	Result	Execution time	Memory
250416		tutis	Candies (JOI18_candies)	C++17	0 / 100	520 ms	524292 KiB

candies

/*input
5
3 5 1 7 6
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename K>
using ordered_map = tree<T, K, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector<ll>a(n);
	for (ll&i : a)
		cin >> i;
	function<vector<array<array<ll, 2>, 2>>(vector<ll>)>ans = [&](vector<ll>a) -> vector<array<array<ll, 2>, 2>>
	{
		assert(!a.empty());
		if (a.size() == 1)
		{
			vector<array<array<ll, 2>, 2>>ret(2);
			ret[1][1][1] = a[0];
			ret[0][1][1] = a[0];
			ret[0][1][0] = 0;
			ret[0][0][1] = 0;
			ret[0][0][0] = 0;
			ret[1][1][0] = 0;
			ret[1][0][1] = 0;
			ret[1][0][0] = 0;
			return ret;
		}
		if (a.size() == 2)
		{
			vector<array<array<ll, 2>, 2>>ret(2);
			ret[1][1][1] = max(a[0], a[1]);
			ret[1][1][0] = a[0];
			ret[1][0][1] = a[1];
			ret[1][0][0] = 0;
			ret[0][1][1] = 0;
			ret[0][1][0] = 0;
			ret[0][0][1] = 0;
			ret[0][0][0] = 0;
			return ret;
		}
		int i = (a.size()) / 2;
		ll xxx = a[i];
		vector<ll>k;
		vector<ll>d;
		for (int j = 0; j < i; j++)
			k.push_back(a[j]);
		for (int j = i + 1; j < n; j++)
			d.push_back(a[j]);
		auto K = ans(k);
		auto D = ans(d);
		vector<array<array<ll, 2>, 2>>ret(((int)a.size() + 5) / 2);
		for (int i = 0; i < ret.size(); i++)
		{
			for (int x : {0, 1})
			{
				for (int y : {0, 1})
				{
					ret[i][x][y] = 0;
				}
			}
		}
		for (int i = 0; i < K.size(); i++)
		{
			for (int j = 0; j < D.size(); j++)
			{
				for (int x : {0, 1})
				{
					for (int y : {0, 1})
					{
						ret[i + j][x][y] = max(
						                       ret[i + j][x][y],
						                       K[i][x][1] + D[j][1][y]
						                   );
						if (i + j + 1 < ret.size())
							ret[i + j + 1][x][y] = max(ret[i + j + 1][x][y],
							                           K[i][x][0] + D[j][0][y] + xxx
							                          );
					}
				}
			}
		}
		for (int i = 0; i < ret.size(); i++)
		{
			ret[i][0][1] = max(ret[i][0][1], ret[i][0][0]);
			ret[i][1][0] = max(ret[i][1][0], ret[i][0][0]);
			ret[i][1][1] = max({ret[i][1][1], ret[i][0][1], ret[i][1][0]});
		}
		return ret;
	};
	vector<array<array<ll, 2>, 2>>x = ans(a);
	for (int i = 1; i <= (n + 1) / 2; i++)
	{
		cout << x[i][1][1] << "\n";
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In lambda function:
candies.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ret.size(); i++)
                   ~~^~~~~~~~~~~~
candies.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < K.size(); i++)
                   ~~^~~~~~~~~~
candies.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < D.size(); j++)
                    ~~^~~~~~~~~~
candies.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (i + j + 1 < ret.size())
           ~~~~~~~~~~^~~~~~~~~~~~
candies.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ret.size(); i++)
                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92