求助,13-20点1.2s超时
查看原帖
求助,13-20点1.2s超时
719058
fengjunnemo楼主2023/10/20 22:04
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 500010
#define inf 0x3f3f3f3f
int n;
int a[N],b[N],c[N];
int fb[N],fc[N];
int u[N];
int q,m;
int p[N];
bool vis[N];
void clean(){
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));
	memset(fc,0,sizeof(fc));
}
int solve(){
	int ans=inf,cnt=0;
	for(int i=1;i<=n;i++){
		if(vis[i]){
			if(i>1){
				fc[i]=fc[i-1]+c[i];
			}else{
				fc[i]=c[i];
			}
		}else{
			fc[i]=fc[i-1];
			cnt+=b[i];
		}
		//cout<<fc[i]<<" ";
	}
	//cout<<"\n";
	for(int i=0;i<=n;i++){
		if(!vis[i]){
			cnt-=b[i];
		}
		ans=min(ans,fc[i]+u[i]+cnt);
		//cout<<fc[i]<<" "<<u[i]<<" "<<cnt<<"\n";
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		
		cin>>b[i];
		if(i==1){
			fb[i]=b[i];
		}else{
			fb[i]=fb[i-1]+b[i];
		}
	}
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	u[1]=min(fb[1],a[1]);
	for(int i=2;i<=n;i++){
		u[i]=min(a[i],u[i-1]+b[i]);
	}
	cin>>q;
	while(q--){
		clean();
		cin>>m;
		for(int i=1;i<=m;i++){
			cin>>p[i];
			vis[p[i]]=1;
		}
		cout<<solve()<<"\n";
	}
	return 0;
}
2023/10/20 22:04
加载中...