65pts RE7个点!
查看原帖
65pts RE7个点!
798043
Ehuo_ovo楼主2023/10/15 21:50

求调!

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n,q;
int pre0[500005];
int sin0[500005];
int presin0[500005];
int sin1[500005];
queue<int>que;

int f[500005];
void all0(){
	f[1]=min(pre0[1],sin0[1]);
	for(int i=2;i<=n;i++){
		f[i]=min(f[i-1]+sin0[i],pre0[i]);
	}
}
vector<int>ve;


signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	freopen("t1.out","w",stdout);
	bool spe=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>pre0[i];
	}
	for(int i=1;i<=n;i++){
		cin>>sin0[i];
		presin0[i]=presin0[i-1]+sin0[i];
	}
	for(int i=1;i<=n;i++){
		cin>>sin1[i];
		if(sin1[i]!=0) spe=1;
	}
	
	all0();
	
	cin>>q;while(q--){
		int m;cin>>m;
		
		
		if(m==0){
			cout<<f[n]<<endl;
			continue;
		}
		
		
		if(m==1){
			int aim;cin>>aim;
			int mn=f[n]+sin1[aim];
			int mn2=f[aim-1]+(presin0[n]-presin0[aim]);
			cout<<min(mn,mn2)<<endl;
			continue;
		}
		
		
		if(spe==0){
			while(m--){
				int tmp;cin>>tmp;
				que.push(tmp);
			}
			que.push(n+1);
			int mn=f[n];
			int mn2=f[que.front()-1],st=que.front();
			while(!que.empty()){
				int top=que.front();
				que.pop();
				if(!que.empty()) mn2+=(presin0[que.front()-1]-presin0[top]);
			}
			cout<<min(mn,mn2)<<endl;
			continue;
		}
		
		vector<int>().swap(ve);
		int mn=f[n];
		int topsum=0;
		while(m--){
			int tmp;cin>>tmp;
			que.push(tmp);
			ve.push_back(tmp);
			mn+=sin1[tmp];
			topsum+=sin1[tmp];
		}
		que.push(n+1);
		ve.push_back(n+1);
	
		int lst=0;
		for(int i=ve.size()-1;i>=0;i--){
//			cout<<"        "<<i+1<<" "<<ve[i]<<endl;
			topsum-=sin1[ve[i]];
			mn=min(mn,lst+f[ve[i]-1]+topsum);
			if(i!=0) lst+=(presin0[ve[i]-1]-presin0[ve[i-1]]);
		}
		
		
		int mn2=f[que.front()-1],st=que.front();
		while(!que.empty()){
			int top=que.front();
			que.pop();
			mn2+=(presin0[que.front()-1]-presin0[top]);
		}
		cout<<min(mn,mn2)<<endl;
		continue;
	}
}

2023/10/15 21:50
加载中...