#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#include"homecoming.h"
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, b;
vector<int> tooka, tookb;
struct seg {
int n;
vector<ll> tree;
seg(int n) {
n = a.size();
while(n & (n-1)) n += n&-n;
tree.resize(2*n, 1ll<<60);
}
template<int SET>
void upd(int pos, ll val) {
for(SET ? (tree[pos+=n]=val) : (tree[pos+=n]+=val); pos/=2;)
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
ll query() { return tree[1]; }
ll query(int l, int r) {
ll res = 0;
for(l += n, r += n; l < r; l>>=1,r>>=1) {
if(l&1) res = min(res, tree[l++]);
if(r&1) res = min(res, tree[--r]);
}
return res;
}
};
//ll get(const vector<ll> &a, int l, int r) {
// return a[r] - (l?a[l-1]:0);
//}
ll naive1(int fil) {
deque<ll> dp;
const ll inf = 1ll<<50;
for(int i = 0; i <= k; i++)
dp.push_back(i == fil ? 0 : -inf);
ll best = 0, lazyadd = 0;
for(int i = 0; i < n; i++) {
ll bk = dp.back();
ll ne0 = best;
dp.pop_back();
dp.back() = max(dp.back(), bk);
lazyadd += b[i], best += b[i];
dp.back() += a[i];
dp.push_front(ne0-lazyadd);
best = max(best, ne0);
best = max(dp.back()+lazyadd, best);
//for(auto i : dp) cout << i+lazyadd << " "; cout << endl;
//cout << best+lazyadd << endl;
}
return best;
}
long long solve(int N, int K, int *A, int *B) {
n = N, k = K;
a = vector<ll>(A, A+n);
b = vector<ll>(B, B+n);
for(auto &i : b) i *= -1;
//for(int i = 1; i < n; i++)
// a[i] += a[i-1], b[i] += b[i-1];
ll ans = 0;
//for(auto i : a) cout << i << " "; cout << endl;
//for(auto i : b) cout << i << " "; cout << endl;
for(int i = 0; i < k; i++) ans = max(ans, naive1(i));
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
12140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
