出题人题解 | 重复の任务

没时间写了到时候再补吧

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll vector<ll>
#define eb emplace_back
#define pob pop_back
const ll MAXN=1e5+15;
struct node{
	ll l,r;
	lll sum,maxx;
};
ll n,cnt,muls;
ll a[MAXN],b[MAXN],w[MAXN],c[MAXN];
lll dp[MAXN],dpb[MAXN];
node sgt[MAXN<<2];
inline lll to_lll(ll x){
	lll ret;
	while(x){
		ret.eb(x%10);
		x/=10;
	}
	return ret;
}
inline lll maxs(const lll &a,const lll &b){
	if(a.size()^b.size()){
		if(a.size()>b.size()) return a;
		return b;
	}
	for(ll i=a.size()-1;i>=0;i--){
		if(a[i]^b[i]){
			if(a[i]>b[i]) return a;
			return b;
		}
	}
	return a;
}
inline lll relead(lll a){
	while(a.size()>1&&a.back()==0) a.pob();
	return a;
}
inline lll add(const lll &a,const lll &b){
	if(a.size()>b.size()) return add(b,a);
	ll t=0;
	lll c;
	for(ll i=0;i<a.size();i++){
		c.eb((a[i]+b[i]+t)%10);
		t=(a[i]+b[i]+t)/10;
	}
	for(ll i=a.size();i<b.size();i++){
		c.eb((b[i]+t)%10);
		t=(b[i]+t)/10;
	}
	while(t){
		c.eb(t%10);
		t/=10;
	}
	return relead(c);
}
inline lll mul(const lll &a,const ll &b){
    ll t,x=0;
    lll c;
    for(ll i=0;i<a.size();i++){
        t=a[i]*b+x;
        c.eb(t%10);
        x=t/10;
    }
    while(x){
        c.eb(x%10);
        x/=10;
    }
    return relead(c);
}
inline void print(lll a){
	for(ll i=a.size()-1;i>=0;i--) cout<<a[i];
	return;
}
inline ll ls(const ll &p){return p<<1;}
inline ll rs(const ll &p){return p<<1|1;}
inline void build(const ll &l,const ll &r,const ll &p){
	lll t(1,0);
	sgt[p]={l,r,t,t};
	if(l>=r) return;
	ll mid=l+r>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	return;
}
inline void update(const ll &l,const ll &r,const ll &x,const ll &p,const lll &c){
	if(l>=x&&r<=x){
		sgt[p].sum=sgt[p].maxx=c;
		return;
	}
	ll mid=l+r>>1;
	if(mid>=x) update(l,mid,x,ls(p),c);
	if(mid<x) update(mid+1,r,x,rs(p),c);
	sgt[p].sum=add(sgt[ls(p)].sum,sgt[rs(p)].sum);
	sgt[p].maxx=maxs(sgt[ls(p)].maxx,sgt[rs(p)].maxx);
	return;
}
inline lll query(const ll &l,const ll &r,const ll &ql,const ll &qr,const ll &p,const bool &op){
	if(l>=ql&&r<=qr){
		if(op) return sgt[p].sum;
		return sgt[p].maxx;
	}
	ll mid=l+r>>1;
	lll ret;
	if(mid>=ql) ret=query(l,mid,ql,qr,ls(p),op);
	if(mid<qr){
		if(op) ret=add(ret,query(mid+1,r,ql,qr,rs(p),op));
		else ret=maxs(query(mid+1,r,ql,qr,rs(p),op),ret);
	}
	return ret;
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	for(ll i=1;i<=n;i++) cin>>b[i];
    for(ll i=0;i<=n;i++) cin>>w[i];
    for(ll i=1;i<=n;i++) cin>>c[i];
	build(1,n,1);
	dp[1]=to_lll(a[1]+b[1]+max(a[1],b[1]));
	update(1,n,1,1,dp[1]);
	for(ll i=2;i<=n;i++){
		dp[i]=add(query(1,n,a[i],b[i],1,true),query(1,n,a[i],b[i],1,false));
		update(1,n,i,1,dp[i]);
	}
    for(ll i=1;i<=n;i++){
        muls=1;
        while(c[i]>=muls){
            dp[++cnt+n]=mul(dp[i],muls);
            w[cnt+n]=muls*w[i];
            c[i]-=muls;
            muls<<=1;
        }
        if(c[i]){
            dp[++cnt+n]=mul(dp[i],c[i]);
            w[cnt+n]=c[i]*w[i];
        }
    }
    for(ll i=n+1;i<=n+cnt;i++){
        for(ll j=w[0];j>=w[i];j--){
            dpb[j]=maxs(add(dpb[j-w[i]],dp[i]),dpb[j]);
        }
    }
    print(dpb[w[0]]);
	return 0;
}