/*
Wei Wai Wei Wai
Zumigat nan damu dimi kwayt rayt
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod FM(2);
*/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 10;
int n, a[maxn];
vector<ll> dp[maxn << 2][4];
vector<ll> merge(vector<ll> a, vector<ll> b){
vector<ll> res;
if (a.empty() || b.empty()) return res;
res.push_back(0);
res.resize(a.size() + b.size() - 1, 0);
int pta = 1, ptb = 1;
for (int i = 1; i < res.size(); i++){
assert(pta < a.size() || ptb < b.size());
if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
res[i] = res[i-1] + a[pta] - a[pta-1];
pta++;
}
else{
res[i] = res[i-1] + b[ptb] - b[ptb-1];
ptb++;
}
}
return res;
}
void solve(int v, int l, int r){
if (l + 1 == r){
dp[v][0].push_back(0);
dp[v][3].push_back(0);
dp[v][3].push_back(a[l]);
return;
}
int mid = (l + r) >> 1;
int lc = v << 1;
int rc = lc | 1;
solve(lc, l, mid);
solve(rc, mid, r);
for (int i = 0; i < 4; i++){
int sz = (r - l == 2? (i&1) + (i&2): (r - l == 3? max(1, (i&1) + (i&2)): (r - l - 2 - (i&1) - (i&2) + 1) / 2 + (i&1) + (i&2))) + 1;
dp[v][i].resize(sz, 0);
for (int j = 0; j < 3; j++){
vector<ll> tmp = merge(dp[lc][(i&2)+(j&1)], dp[rc][(j&2)+(i&1)]);
for (int k = 0; k < tmp.size(); k++){
dp[v][i][k] = max(dp[v][i][k], tmp[k]);
}
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
solve(1, 1, n+1);
for (int i = 1; i <= (n+1)/2; i++){
ll res = 0;
for (int j = 0; j < 4; j++){
if (dp[1][j].size() > i) res = max(res, dp[1][j][i]);
}
cout << res << '\n';
}
return 0;
}
Compilation message
candies.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
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 | for (int i = 1; i < res.size(); i++){
| ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from candies.cpp:8:
candies.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | assert(pta < a.size() || ptb < b.size());
| ~~~~^~~~~~~~~~
candies.cpp:58:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | assert(pta < a.size() || ptb < b.size());
| ~~~~^~~~~~~~~~
candies.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
| ~~~~^~~~~~~~~~~
candies.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
| ~~~~^~~~~~~~~~
candies.cpp: In function 'void solve(int, int, int)':
candies.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int k = 0; k < tmp.size(); k++){
| ~~^~~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:104:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
104 | if (dp[1][j].size() > i) res = max(res, dp[1][j][i]);
| ~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
152780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
152780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
