WA on #2 95pts求调
查看原帖
WA on #2 95pts求调
245959
Ender_NaCl楼主2023/10/17 21:10

RT,找不到哪里错了

#include <iostream>

#include <cstdio>

#define ll long long

using namespace std;

const int N = 500010;

ll a[N],b[N],c[N],lg[N],n,p[N];
ll suf[N],minn[N][20],tmp1[N],tmp2[N];

void Build()
{
	int i,j;
	for(i = 0;i <= n;i++) minn[i][0] = a[i] + suf[i + 1];
	for(j = 1;j <= lg[n];j++) for(i = 0;i + (1<<j) - 1<= n;i++) minn[i][j] = min(minn[i][j - 1],minn[i + (1<<(j - 1))][j - 1]);
}

ll Find(int l,int r)
{
	int m = lg[r - l + 1];
	return min(minn[l][m],minn[r - (1<<m) + 1][m]);
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	int i;
	cin>>n;
	for(i = 2;i <= n;i++) lg[i] = lg[i>>1] + 1;
	for(i = 1;i <= n;i++) cin>>a[i];
	for(i = 1;i <= n;i++) cin>>b[i];
	for(i = 1;i <= n;i++) cin>>c[i];
	for(i = n;i >= 1;i--) suf[i] = suf[i + 1] + b[i];
	Build();
	int q;
	cin>>q;
	while(q--)
	{
		int m;
		ll ans;
		cin>>m;
		for(i = 1;i <= m;i++) cin>>p[i];
		tmp2[m + 1] = 0;
		for(i = 1;i <= m;i++) tmp1[i] = tmp1[i - 1] + c[p[i]];
		for(i = m;i >= 1;i--) tmp2[i] = tmp2[i + 1] - b[p[i]];
		p[m + 1] = n + 1;
		ans = Find(0,p[1] - 1) + tmp2[1];
		for(i = 1;i <= m;i++) ans = min(ans,tmp1[i] + Find(p[i],p[i + 1] - 1) + tmp2[i + 1]);
		cout<<ans<<endl;
	}
	return 0;
}
2023/10/17 21:10
加载中...