WA在3,4,90pts
查看原帖
WA在3,4,90pts
366516
xuyiyang楼主2023/10/16 09:56

看不懂前面那位90的调法,求助

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;
typedef long long LL;

int n, m;
int a[N], b[N], c[N];
int d[N];
LL L[N], R[N];
LL st[N][21];
LL sum[N];

inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') w = -1;
	for (; c >= '0' && c <= '9'; c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
	return s * w;
}

void init()
{
	for (int i = 1; i <= n; i ++ ) st[i][0] = (LL)a[i] - sum[i];
	int t = log(n) / log(2) + 1;
	for (int j = 1; j < t; j ++ )
		for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
			st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); 
}

LL query(int l, int r)
{
	if (l > r) return 0; 
	int k = log(r - l + 1) / log(2);
	return min(st[l][k], st[r - (1 << k) + 1][k]); 
}

int main()
{
	n = read();
	for (int i = 1; i <= n; i ++ ) a[i] = read();
	for (int i = 1; i <= n; i ++ ) b[i] = read(), sum[i] = sum[i - 1] + b[i];
	for (int i = 1; i <= n; i ++ ) c[i] = read();
	m = read(); init();
	while (m -- )
	{
		int k;
		scanf("%d", &k);
		for (int i = 1; i <= k; i ++ ) scanf("%d", &d[i]);
		for (int i = 1; i <= k; i ++ ) L[i] = L[i - 1] + b[d[i]], R[i] = R[i - 1] + c[d[i]];
		d[0] = 1; d[k + 1] = n + 1; LL res = 1e18;
		for (int i = 1; i <= k + 1; i ++ )
		{
			LL s = query(d[i - 1], d[i] - 1); 
			s += R[i - 1]; 
			s += sum[n] - (L[k] - L[i - 1]);
			
			res = min(res, s);
		}
		printf("%lld\n", res);
	}
	return 0;
} 
2023/10/16 09:56
加载中...