社区讨论

第二个点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 条回复,欢迎继续交流。

正在加载回复...