| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250442 |
2020-07-17T22:28:37 Z |
tutis |
Candies (JOI18_candies) |
C++17 |
|
548 ms |
17692 KB |
/*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 < b.size(); i++)
assert(2 * b[i] >= b[i - 1] + b[i + 1]);
vector<ll>c((int)a.size() + (int)b.size() - 1, -1e15);
int x = 0;
for (int i = 0; i < c.size(); i++)
{
int lo = max(0, i - (int)b.size() + 1);
int hi = min((int)a.size() - 1, i);
x = max(x, lo);
x = min(x, hi);
while (true)
{
int x1 = x + 1;
if (x1 <= hi && a[x1] + b[i - x1] >= a[x] + b[i - x])
x++;
else
break;
}
c[i] = a[x] + b[i - x];
}
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
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 < b.size(); i++)
~~~~~~^~~~~~~~~~
candies.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c.size(); i++)
~~^~~~~~~~~~
candies.cpp: In function 'std::vector<std::array<std::array<long long int, 2>, 2> > ans(const std::vector<long long int>&)':
candies.cpp:76:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j < a.size(); j++)
~~^~~~~~~~~~
candies.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ret.size(); i++)
~~^~~~~~~~~~~~
candies.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < K.size(); i++)
~~^~~~~~~~~~
candies.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < D.size(); i++)
~~^~~~~~~~~~
candies.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < suma[x][1][y].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~
candies.cpp:112: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:112: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:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ret.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
564 KB |
Output is correct |
| 11 |
Correct |
6 ms |
512 KB |
Output is correct |
| 12 |
Correct |
5 ms |
512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
512 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| 15 |
Correct |
5 ms |
512 KB |
Output is correct |
| 16 |
Correct |
5 ms |
512 KB |
Output is correct |
| 17 |
Correct |
5 ms |
512 KB |
Output is correct |
| 18 |
Correct |
6 ms |
512 KB |
Output is correct |
| 19 |
Correct |
5 ms |
512 KB |
Output is correct |
| 20 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
564 KB |
Output is correct |
| 11 |
Correct |
6 ms |
512 KB |
Output is correct |
| 12 |
Correct |
5 ms |
512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
512 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| 15 |
Correct |
5 ms |
512 KB |
Output is correct |
| 16 |
Correct |
5 ms |
512 KB |
Output is correct |
| 17 |
Correct |
5 ms |
512 KB |
Output is correct |
| 18 |
Correct |
6 ms |
512 KB |
Output is correct |
| 19 |
Correct |
5 ms |
512 KB |
Output is correct |
| 20 |
Correct |
5 ms |
512 KB |
Output is correct |
| 21 |
Correct |
527 ms |
17644 KB |
Output is correct |
| 22 |
Correct |
532 ms |
17344 KB |
Output is correct |
| 23 |
Correct |
530 ms |
17508 KB |
Output is correct |
| 24 |
Correct |
499 ms |
17340 KB |
Output is correct |
| 25 |
Correct |
486 ms |
17344 KB |
Output is correct |
| 26 |
Correct |
497 ms |
17344 KB |
Output is correct |
| 27 |
Correct |
505 ms |
17340 KB |
Output is correct |
| 28 |
Correct |
495 ms |
17488 KB |
Output is correct |
| 29 |
Correct |
491 ms |
17332 KB |
Output is correct |
| 30 |
Correct |
495 ms |
17340 KB |
Output is correct |
| 31 |
Correct |
495 ms |
17460 KB |
Output is correct |
| 32 |
Correct |
491 ms |
17336 KB |
Output is correct |
| 33 |
Correct |
501 ms |
17436 KB |
Output is correct |
| 34 |
Correct |
512 ms |
17552 KB |
Output is correct |
| 35 |
Correct |
510 ms |
17464 KB |
Output is correct |
| 36 |
Correct |
535 ms |
17512 KB |
Output is correct |
| 37 |
Correct |
548 ms |
17508 KB |
Output is correct |
| 38 |
Correct |
541 ms |
17444 KB |
Output is correct |
| 39 |
Correct |
495 ms |
17336 KB |
Output is correct |
| 40 |
Correct |
492 ms |
17508 KB |
Output is correct |
| 41 |
Correct |
488 ms |
17344 KB |
Output is correct |
| 42 |
Correct |
487 ms |
17340 KB |
Output is correct |
| 43 |
Correct |
487 ms |
17544 KB |
Output is correct |
| 44 |
Correct |
484 ms |
17336 KB |
Output is correct |
| 45 |
Correct |
488 ms |
17468 KB |
Output is correct |
| 46 |
Correct |
492 ms |
17512 KB |
Output is correct |
| 47 |
Correct |
488 ms |
17472 KB |
Output is correct |
| 48 |
Correct |
501 ms |
17512 KB |
Output is correct |
| 49 |
Correct |
515 ms |
17692 KB |
Output is correct |
| 50 |
Correct |
503 ms |
17460 KB |
Output is correct |
