求助S组模拟赛T1
  • 板块学术版
  • 楼主Targanzqq
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/15 19:05
  • 上次更新2023/11/2 13:35:27
查看原帖
求助S组模拟赛T1
555617
Targanzqq楼主2023/10/15 19:05

90pts,求助,3和4测试点过不去

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

int n,m,q,a[500005],b[500005],c[500005],p[500005],sufb[500005]={0},sumc[500005],sufkey[500005];
int st[500005][21]={0};

inline int read()
{
    char c=getchar();
    int f=1,n=0;
    while(c!='-'&&(c<'0'||c>'9'))
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        n=n*10+(c^48);
        c=getchar();
    }
    return n*f;
}
void pr(int x)
{
    if(!x)
    {
        return ;
    }
    int l=x/10;
    pr(l);
    putchar(x%10^48);
}
inline void write(int x)
{
    if(!x)
    {
        putchar('0');
        return ;
    }
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    pr(x);
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		b[i]=read();
	}
	for(int i=1;i<=n;i++){
		c[i]=read();
	}
	for(int i=n;i>=1;i--){
		sufb[i]=sufb[i+1]+b[i];
	}
	for(int i=1;i<=n;i++){
		st[i][0]=a[i]+sufb[i+1];
	}
	for(int j=1;j<=20;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]);
		}
	}
	cin>>q;
	int minans,minn;
	for(int i=1;i<=q;i++){
		m=read();
		for(int j=1;j<=m+2;j++){
			sufkey[j]=0;
			sumc[j]=0;
		}
		for(int j=1;j<=m;j++){
			p[j]=read();
		}
		if(m==n){
			cout<<0<<endl;
			continue;
		}
		for(int j=1;j<=m;j++){
			sumc[j]=sumc[j-1]+c[p[j]]; 
		}
		for(int j=m;j>=1;j--){
			sufkey[j]=sufkey[j+1]+b[p[j]]; 
		}
		p[0]=1;p[m+1]=n+1;
		minans=-1;
		for(int j=(p[1]==1?1:0);j<=m;j++){
			int l=log2(p[j+1]-p[j]);
			minn=min(st[p[j]][l],st[p[j+1]-(1<<l)][l]);
			if(minans==-1)minans=minn+sumc[j]-sufkey[j+1];
			else minans=min(minans,minn+sumc[j]-sufkey[j+1]);
			//cout<<"check"<<j<<" "<<minn<<" "<<sumc[j]<<" "<<sufkey[j+1]<<endl;
		}
		write(minans);
		cout<<"\n";
	}
} 
2023/10/15 19:05
加载中...