#1159861 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: askr58
• 提出日時: 2026-04-18 17:46:17
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 218 ms / 2,000 ms
• コード長: 1,611 bytes
• コンパイル時間: 5,660 ms
• コンパイル使用メモリ: 339,616 KB
• 実行使用メモリ: 28,416 KB
• 最終ジャッジ日時: 2026-04-18 17:46:43
• 合計ジャッジ時間: 23,884 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 60

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll solve(int n,ll k,vector<ll> a,vector<ll> b,vector<ll> c,vector<ll> d){
	set<pair<ll,ll>> s;
	ll inf=1e18;
	s.insert(make_pair(inf,k));
	ll sum=k;
	ll base=0;
	for(int i=0;i<n;i++){
		s.insert(make_pair(a[i],b[i]));
		sum+=b[i];
		ll cnt=0,t=0;
		while(cnt<d[i]&&!s.empty()){
			auto[x,v]=*s.begin();
			if(x>c[i])break;
			if(cnt+v<=d[i]){
				cnt+=v;
				sum-=v;
				t+=v*x;
				s.erase(s.begin());
			}else{
				t+=(d[i]-cnt)*x;
				v-=d[i]-cnt;
				sum-=d[i]-cnt;
				cnt=d[i];
				s.erase(s.begin());
				s.insert(make_pair(x,v));
			}
		}
		s.insert(make_pair(c[i],cnt));
		sum+=cnt;
		base+=c[i]*cnt-t;
		while(sum>k){
			auto[x,v]=*(--s.end());
			if(sum-k>=v){
				sum-=v;
				s.erase(--s.end());
			}else{
				v-=sum-k;
				sum=k;
				s.erase(--s.end());
				s.insert(make_pair(x,v));
			}
		}
	/*	vector<ll> v;
		for(auto[x,vv]:s)for(int i=0;i<vv;i++)v.push_back(x);
		vector<ll> ans(k+1);
		ans[0]=base;
		for(int i=0;i<k;i++)ans[i+1]=ans[i]-v[i];
		for(int i=0;i<=k;i++)cout<<ans[i]<<" ";
		cout<<endl;
		ll sum2=0;
		for(auto[x,vv]:s)sum2+=vv;
		for(auto[x,vv]:s)cout<<"("<<x<<","<<vv<<")";
		cout<<endl;
		cout<<sum<<" "<<sum2<<" "<<k<<endl;
		//cout<<base<<endl;//*/
	}
	return base;
}
				
		
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int ttt;
	cin>>ttt;
	while(ttt--){
		int n;
		ll k;
		cin>>n>>k;
		vector<ll> a(n),b(n),c(n),d(n);
		for(int i=0;i<n;i++)cin>>a[i];
		for(int i=0;i<n;i++)cin>>b[i];
		for(int i=0;i<n;i++)cin>>c[i];
		for(int i=0;i<n;i++)cin>>d[i];
		cout<<solve(n,k,a,b,c,d)<<endl;
	}
}