This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll inf = 1e10;
vector<ll> mxconv(vector<ll> &a, vector<ll> &b) {
int n = a.size(), m = b.size();
vector<ll> c(n+m-1);
c[0] = 0;
int i = 1, j = 1;
while (i < n || j < m) {
if (i == n) ++j;
else if (j == m) ++i;
else {
if (a[i] - a[i-1] > b[j] - b[j-1]) ++i;
else ++j;
}
c[i+j-2] = a[i-1] + b[j-1];
}
return c;
}
vector<vector<vector<ll>>> dq(vector<ll> &a) { // dp[i][b1][b2] = uzmes ih i b1 = da li uzmes poslednji b2 = da li uzmes prvi
int n = a.size();
if (n == 0) return {{{{0}, {0}}}, {{{0}, {0}}}};
if (n == 1) return {{{{0, -inf}, {0, -inf}}}, {{{0, -inf}, {0, a[0]}}}};
vector<ll> L, R;
for (int i = 0; i < n/2; ++i) L.pb(a[i]);
for (int i = n/2; i < n; ++i) R.pb(a[i]);
auto A = dq(L), B = dq(R);
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(2, vector<ll>(1 + (n+1)/2, -inf)));
// if (n == 2 && a[0] == 3) {
// for (int X = 0; X < 2; ++X) {
// for (int Y = 0; Y < 2; ++Y) {
// for (auto t : A[X][Y]) {
// cout << t << ' ';
// }
// cout << ':';
// for (auto t : B[X][Y]) {
// cout << t << ' ';
// }
// cout << '\n';
// }
// cout << '\n';
// }
// }
for (int X = 0; X < 2; ++X) {
for (int Y = 0; Y < 2; ++Y) {
auto t1 = mxconv(A[X][0], B[0][Y]);
auto t2 = mxconv(A[X][1], B[0][Y]);
auto t3 = mxconv(A[X][0], B[1][Y]);
for (int i = 0; i <= (n+1)/2; ++i) {
dp[X][Y][i] = max({
(i < t1.size() ? t1[i] : -inf),
(i < t2.size() ? t2[i] : -inf),
(i < t3.size() ? t3[i] : -inf)});
}
}
}
return dp;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
auto ans = dq(a);
for (int i = 1; i <= (n+1)/2; ++i) {
cout << max({ans[0][0][i], ans[0][1][i], ans[1][1][i], ans[1][0][i]}) << '\n';
}
int t = (n + 1)/2;
}
Compilation message (stderr)
candies.cpp: In function 'std::vector<std::vector<std::vector<long long int> > > dq(std::vector<long long int>&)':
candies.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | (i < t1.size() ? t1[i] : -inf),
| ~~^~~~~~~~~~~
candies.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | (i < t2.size() ? t2[i] : -inf),
| ~~^~~~~~~~~~~
candies.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | (i < t3.size() ? t3[i] : -inf)});
| ~~^~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:76:9: warning: unused variable 't' [-Wunused-variable]
76 | int t = (n + 1)/2;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |