/*input
5
3 5 1 7 6
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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() + 3) / 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})
{
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;
};
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 lambda function:
candies.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ret.size(); i++)
~~^~~~~~~~~~~~
candies.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < K.size(); i++)
~~^~~~~~~~~~
candies.cpp:70:22: 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:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(i + j < ret.size());
~~~~~~^~~~~~~~~~~~
candies.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + j + 1 < ret.size())
~~~~~~~~~~^~~~~~~~~~~~
candies.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ret.size(); i++)
~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
478 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
478 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
