社区讨论
第二个点wa了,95分求助
P9744 「KDOI-06-S」消除序列参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo12gbn3
- 此快照首次捕获于
- 2023/10/22 14:06 2 年前
- 此快照最后确认于
- 2023/11/02 13:35 2 年前
第二个点过不去很奇怪。
CPP#include <bits/stdc++.h>
#define read(x) {x=0;int ch;while((ch=getchar())<48);do x=x*10+(ch^48);while((ch=getchar())>47);}
#define N 500010
#define int long long
using namespace std;
using ll = long long;
int n, m, q;
ll a[N], b[N], c[N];
int p[N];
ll sum[N], rsum[N], hz[N], f[N][19];
int lg2[N];
inline ll getmin(int l, int r) {
int t = lg2[r - l + 1];
return min(f[l][t], f[r - (1 << t) + 1][t]);
}
signed main() {
read(n);
for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= n; ++i) read(b[i]);
for (int i = 1; i <= n; ++i) read(c[i]);
for (int i = n; i; --i) {
hz[i] = hz[i + 1] + b[i];
f[i][0] = a[i] + hz[i + 1];
// cout << f[i][0] << ' ';
}
// puts("");
f[0][0] = hz[1];
for (int i = 1; i < 19; ++i) {
for (int j = 0; j + (1 << i) - 1 <= n; ++j) {
f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
}
}
read(q);
while (q--) {
read(m);
for (int i = 1; i <= m; ++i) read(p[i]);
p[m + 1] = n + 1;
for (int i = 1; i <= m; ++i) {
sum[i] = sum[i - 1] + c[p[i]];
}
rsum[m + 1] = 0;
for (int i = m; i; --i) {
rsum[i] = rsum[i + 1] + b[p[i]];
}
ll ans = 1e18;
for (int i = 0; i <= m; ++i) {
ans = min(ans, sum[i] - rsum[i + 1] + getmin(p[i], p[i + 1] - 1));
}
printf("%lld\n", ans);
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...