QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122879 | #1808. Efficient Partitioning | Scarlett_boy | RE | 0ms | 0kb | C++17 | 3.2kb | 2023-07-11 13:27:06 | 2023-07-11 13:27:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n;
const int mod = 1e9 + 7;
const ll Eps = 1e18, L = 1, R = 2e18;
struct Tree {
#define LOG 65
int root, cnt;
ll Mi, Ma;
vector<int> ls, rs;
vector<ll> MAX1, MAX2;
Tree(int M = 0, ll Min = 1, ll Max = 2e18) : ls(M * LOG), rs(M * LOG), MAX1(M * LOG), MAX2(M * LOG) {
root = 0, cnt = 0;
Mi = Min, Ma = Max;
}
inline void pushup(int p) {
MAX1[p] = max(MAX1[ls[p]], MAX1[rs[p]]);
MAX2[p] = max(MAX2[ls[p]], MAX2[rs[p]]);
}
inline void New(int &p) {
p = ++cnt;
MAX1[p] = MAX2[p] = -Eps;
}
inline void update(int &p, ll l, ll r, ll x, ll w1, ll w2) {
if (!p) New(p);
if (l == r) {
MAX1[p] = max(MAX1[p], w1);
MAX2[p] = max(MAX2[p], w2);
return;
}
int mid = l + r >> 1;
if (x <= mid) update(ls[p], l, mid, x, w1, w2);
else update(rs[p], mid + 1, r, x, w1, w2);
pushup(p);
}
inline void update(int x, ll w1, ll w2) { update(root, Mi, Ma, x, w1, w2); }
inline ll query1(int p, ll l, ll r, ll x, ll y) {
if (!p) return -Eps;
if (x <= l && r <= y) return MAX1[p];
ll ans = -Eps;
int mid = l + r >> 1;
if (x <= mid) ans = max(ans, query1(ls[p], l, mid, x, y));
if (y > mid) ans = max(ans, query1(rs[p], mid + 1, r, x, y));
return ans;
}
inline ll query1(ll l, ll r) { return query1(root, Mi, Ma, l, r); }
inline ll query2(int p, ll l, ll r, ll x, ll y) {
if (!p) return -Eps;
if (x <= l && r <= y) return MAX2[p];
ll ans = -Eps;
int mid = l + r >> 1;
if (x <= mid) ans = max(ans, query2(ls[p], l, mid, x, y));
if (y > mid) ans = max(ans, query2(rs[p], mid + 1, r, x, y));
return ans;
}
inline ll query2(ll l, ll r) { return query2(root, Mi, Ma, l, r); }
};
void solve() {
cin >> n;
vector<ll> a(n + 5), b(n + 5), c(n + 5), sum(n + 5);
vector<ll> dp(n + 5, -Eps);
Tree T(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
sum[0] = a[0];
for (int i = 1; i < n; i++) sum[i] = a[i] + sum[i - 1];
dp[0] = a[0] + b[0] + c[0];
T.update(dp[0] - b[1] + sum[0] + Eps, dp[0], b[1] - sum[0]);
for (int i = 1; i < n; i++) {
// for (int j = 0; j < i; j++) {
// dp[i] = max(dp[i], min(dp[j], b[j + 1] + c[i] + query(j + 1, i)));
// }
ll x = c[i] + sum[i] + Eps;
dp[i] = max(T.query1(L, x), T.query2(x, R) + c[i] + sum[i]);
// cout << T.query1(L, x) << " " << T.query2(x, R) + c[i] + sum[i] << " " << T.query2(x, R) << "\n";
T.update(dp[i] - b[i + 1] + sum[i] + Eps, dp[i], b[i + 1] - sum[i]);
}
cout << dp[n - 1] << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
// cin >> _;
for (int o = 1; o <= _; o++) {
// cout << "Case #<<" << o << ": ";
solve();
}
return 0;
}
/*
1
10 4
AABABBABAB
10 3 4 10 7 1 8 10 7 6
*/
详细
Test #1:
score: 0
Runtime Error
input:
2 1 -1 -1 4 1 -2