oj.uz

답안 #250420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250420 2020-07-17T20:10:35 Z tutis Candies (JOI18_candies) C++17
8 / 100
 5000 ms 12720 KB 
/*input
5
3 5 1 7 6
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<array<array<ll, 2>, 2>>ans(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;
			}
		}
	}
	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})
				{
					assert(i + j < ret.size());
					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;
};
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

candies.cpp: In function 'std::vector<std::array<std::array<long long int, 2>, 2> > ans(std::vector<long long int>)':
candies.cpp:44:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = i + 1; j < a.size(); j++)
                      ~~^~~~~~~~~~
candies.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ret.size(); i++)
                  ~~^~~~~~~~~~~~
candies.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < K.size(); i++)
                  ~~^~~~~~~~~~
candies.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < D.size(); j++)
                   ~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from candies.cpp:5:
candies.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      assert(i + j < ret.size());
             ~~~~~~^~~~~~~~~~~~
candies.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (i + j + 1 < ret.size())
          ~~~~~~~~~~^~~~~~~~~~~~
candies.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ret.size(); i++)
                  ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 7 ms 532 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 7 ms 512 KB Output is correct
15 Correct 7 ms 512 KB Output is correct
16 Correct 7 ms 512 KB Output is correct
17 Correct 7 ms 512 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Correct 7 ms 512 KB Output is correct
20 Correct 7 ms 512 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 7 ms 532 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 7 ms 512 KB Output is correct
15 Correct 7 ms 512 KB Output is correct
16 Correct 7 ms 512 KB Output is correct
17 Correct 7 ms 512 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Correct 7 ms 512 KB Output is correct
20 Correct 7 ms 512 KB Output is correct
21 Execution timed out 5071 ms 12720 KB Time limit exceeded
22 Halted 0 ms 0 KB -