#include <bits/stdc++.h>
using namespace std;
const int kN = 2e5;
const int64_t INF = 2e18L;
int a[2 * kN], v[1 + kN + 1];
tuple<int, int, int> intervals[2 * kN];
vector<pair<int, int>> rEnd[1 + kN + 1];
void minSelf(int64_t &x, int64_t y) {
if (y < x) {
x = y;
}
}
struct ST {
int n;
vector<int64_t> t, lazy;
ST(int N) : n(N) {
int dim = 1;
while (dim < n + 1) {
dim *= 2;
}
dim *= 2;
t.resize(dim);
lazy.resize(dim);
}
void push(int x) {
if (lazy[x] == 0) {
return;
}
for (int y = 2 * x; y <= 2 * x + 1; ++y) {
t[y] += lazy[x];
lazy[y] += lazy[x];
}
lazy[x] = 0;
}
/* void setElement(int x, int lx, int rx, int pos, int64_t v) {
if (lx == rx) {
t[x] = v;
return;
}
push(x);
int mid = (lx + rx) / 2;
if (pos <= mid) {
setElement(x * 2, lx, mid, pos, v);
} else {
setElement(x * 2 + 1, mid + 1, rx, pos, v);
}
t[x] = min(t[x * 2], t[x * 2 + 1]);
}
void setElement(int pos, int v) {
setElement(1, 0, n, pos, v);
} */
void rangeAdd(int x, int lx, int rx, int st, int dr, int64_t v) {
if (st <= lx && rx <= dr) {
t[x] += v;
lazy[x] += v;
return;
}
push(x);
int mid = (lx + rx) / 2;
if (st <= mid) {
rangeAdd(x * 2, lx, mid, st, dr, v);
}
if (mid < dr) {
rangeAdd(x * 2 + 1, mid + 1, rx, st, dr, v);
}
t[x] = min(t[x * 2], t[x * 2 + 1]);
}
void rangeAdd(int st, int dr, int64_t v) {
rangeAdd(1, 0, n, st, dr, v);
}
int64_t query(int x, int lx, int rx, int st, int dr) {
if (st <= lx && rx <= dr) {
return t[x];
}
push(x);
int mid = (lx + rx) / 2;
int64_t ans = INF;
if (st <= mid) {
minSelf(ans, query(x * 2, lx, mid, st, dr));
}
if (mid < dr) {
minSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
}
return ans;
}
int64_t query(int st, int dr) {
return query(1, 0, n, st, dr);
}
};
int64_t solve(int n) {
ST t(n);
for (int i = 1; i <= n; ++i) {
t.rangeAdd(i, i, t.query(0, i - 1));
t.rangeAdd(0, i - 1, v[i]);
for (auto it : rEnd[i]) {
int start, cost;
tie(start, cost) = it;
t.rangeAdd(start, i, cost);
}
}
return t.query(n, n);
}
void testCase() {
int n, m;
cin >> n >> m;
int N = n + m - 1;
for (int i = 1; i <= N; ++i) {
cin >> a[i];
}
for (int i = 1; i <= N; ++i) {
int cost;
cin >> cost;
int y = min(i, m - 1);
int x = i - y;
int index = x - y + m;
int len = min(i, N - i + 1);
intervals[i] = {(index + 1) / 2, len, cost};
}
int64_t ans = 0;
for (int par = 0; par <= 1; ++par) {
int M = (N + par) / 2 + 1;
for (int i = 1; i <= M; ++i) {
rEnd[i].clear();
}
for (int i = 2 - par; i <= N; i += 2) {
int index, len, cost;
tie(index, len, cost) = intervals[i];
v[(i + par) / 2] = a[i];
rEnd[index + len - 1].emplace_back(index, cost);
}
ans += solve(M);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
20904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
509 ms |
32116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
