T1
  • 板块学术版
  • 楼主_lqs_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/15 18:31
  • 上次更新2023/11/2 13:36:23
查看原帖
T1
664744
_lqs_楼主2023/10/15 18:31

95 分第二个点 WA 了,求调错。

#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define int long long
int n,m,i,j,ans,a[N],b[N],c[N],q,p[N],u[N],l,Q[N],mp[N],cnt,qq;
int f[N][25],g[N],Log[N];
int qry(int l,int r){
	int p=Log[r-l+1];
	return min(f[l][p],f[r-(1<<p)+1][p]);
}
signed main(){
//	freopen("reserve8.in","r",stdin);
//	freopen("1.out","w",stdout); 
	scanf("%lld",&n);
	for(i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(i=1;i<=n;i++) scanf("%lld",&c[i]);
	for(i=n;i>=1;i--) Q[i]=Q[i+1]+b[i];
	memset(f,127,sizeof(f));
	for(i=0;i<=n;i++) g[i]=a[i]+Q[i+1],f[i][0]=g[i];
	for(i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
	for(j=1;j<=20;j++){
		for(i=0;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	scanf("%lld",&q),qq=q;
	while(q--){
		scanf("%lld",&m),l=0,ans=1e18;
		for(i=1;i<=m;i++) scanf("%lld",&p[i]);
		sort(p+1,p+1+m),mp[m+1]=0,p[m+1]=n;
		for(i=m;i>=1;i--) mp[i]=mp[i+1]+b[p[i]];
		int k,s=0;
		for(i=0,j=0;j<=m;i=p[j+1],j++){
			k=a[i];
			int r;
			if(j+1>m) r=n;
			else r=p[j+1]-1;
			int Minn=qry(i,r);
			if(p[l+1]==i && l<m) l++,s+=c[i];
			ans=min(ans,s+Minn-mp[l+1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
2023/10/15 18:31
加载中...