Submission #250425

#	Time	Username	Problem	Language	Result	Execution time	Memory
250425		tutis	Candies (JOI18_candies)	C++17	0 / 100	2 ms	640 KiB

candies

/*input
5
3 5 1 7 6
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<ll> sum(vector<ll>&a, vector<ll>&b)
{
	for (ll &i : a)
		if (i < 0)
			i = -1e15;
	for (ll &i : b)
		if (i < 0)
			i = -1e15;
	for (int i = 1; i + 1 < a.size(); i++)
		assert(2 * a[i] >= a[i - 1] + a[i + 1]);
	for (int i = 1; i + 1 < a.size(); i++)
		assert(2 * b[i] >= b[i - 1] + b[i + 1]);
	vector<ll>c((int)a.size() + (int)b.size() - 1, -1e15);
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < b.size(); j++)
			c[i + j] = max(c[i + j], a[i] + b[j]);
	return c;
}
vector<array<array<ll, 2>, 2>>ans(const vector<ll> &a)
{
	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] = 0;
		ret[0][1][0] = 0;
		ret[0][0][1] = 0;
		ret[0][0][0] = 0;
		ret[1][1][0] = -1e15;
		ret[1][0][1] = -1e15;
		ret[1][0][0] = -1e15;
		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] = -1e15;
		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 < a.size(); j++)
		d.push_back(a[j]);
	auto K = ans(k);
	auto D = ans(d);
	vector<array<array<ll, 2>, 2>>ret(((int)a.size() + 3) / 2);
	for (int i = 0; i < ret.size(); i++)
	{
		for (int x : {0, 1})
		{
			for (int y : {0, 1})
			{
				ret[i][x][y] = -1e15;
			}
		}
	}
	vector<ll>suma[2][2][2];
	for (int x : {0, 1})
	{
		for (int t : {0, 1})
			for (int y : {0, 1})
			{
				vector<ll>a;
				vector<ll>b;
				for (int i = 0; i < K.size(); i++)
					a.push_back(K[i][x][t]);
				for (int i = 0; i < D.size(); i++)
					b.push_back(D[i][t][y]);
				suma[x][t][y] = sum(a, b);
			}
	}
	for (int x : {0, 1})
	{
		for (int y : {0, 1})
		{
			for (int i = 0; i < suma[x][1][y].size(); i++)
				ret[i][x][y] = max(ret[i][x][y], suma[x][1][y][i]);
			for (int i = 0; i < suma[x][0][y].size() && i + 1 < ret.size(); i++)
				ret[i + 1][x][y] = max(ret[i + 1][x][y], xxx + suma[x][0][y][i]);
		}
	}
	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;
};
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;
	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 function 'std::vector<long long int> sum(std::vector<long long int>&, std::vector<long long int>&)':
candies.cpp:17:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i + 1 < a.size(); i++)
                  ~~~~~~^~~~~~~~~~
candies.cpp:19:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i + 1 < a.size(); i++)
                  ~~~~~~^~~~~~~~~~
candies.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
candies.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < b.size(); j++)
                   ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<std::array<std::array<long long int, 2>, 2> > ans(const std::vector<long long int>&)':
candies.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = i + 1; j < a.size(); j++)
                      ~~^~~~~~~~~~
candies.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ret.size(); i++)
                  ~~^~~~~~~~~~~~
candies.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < K.size(); i++)
                     ~~^~~~~~~~~~
candies.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < D.size(); i++)
                     ~~^~~~~~~~~~
candies.cpp:96:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < suma[x][1][y].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~
candies.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < suma[x][0][y].size() && i + 1 < ret.size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~
candies.cpp:98:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < suma[x][0][y].size() && i + 1 < ret.size(); i++)
                                                ~~~~~~^~~~~~~~~~~~
candies.cpp:102:20: 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