結果

問題 No.2309 [Cherry 5th Tune D] 夏の先取り
コンテスト
ユーザー kotatsugame
提出日時 2023-05-19 22:07:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 3,000 ms
コード長 1,607 bytes
コンパイル時間 1,034 ms
コンパイル使用メモリ 80,932 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-18 02:49:53
合計ジャッジ時間 2,685 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<cassert>
#include<random>
using namespace std;
long A,B,C,X,Y,Z,W;
long solve()
{
	long ans=0;
	for(long a=0;a<=A&&a<=B;a++)
	{
		long rd=min(min(A-a,B-a),C);
		long mid=max(0L,A+B-2*a-C);
		if(mid<=rd)
		{
			//mid<=d<=rd -> (A-a-d)*Z+(B-a-d)*Y+dW=(A-a)*Z+(B-a)*Y+d*(W-Z-Y);
			long d=W-Z-Y>=0?rd:mid;
			ans=max(ans,a*X+(A-a-d)*Z+(B-a-d)*Y+d*W);
		}
		if(0<mid)
		{
			//0<=c<=A-a-d
			//0<=b=C-d-c<=B-a-d
			//-> max(0,C-B+a)<=c<=min(A-a,C)-d
			long rd=min(A-a,C)-max(0L,C-B+a);
			assert(rd>=0);
			//0<=d<=rd
			{
				long x=min(C,A-a);
				//c=min(C,A-a)-d=x-d
				//c(Z-Y)+CY+d(W-Y)=(x-d)(Z-Y)+CY+d(W-Y)=x(Z-Y)+CY+d(W-Z)
				if(W>=Z)ans=max(ans,a*X+x*(Z-Y)+C*Y+rd*(W-Z));
				else ans=max(ans,a*X+x*(Z-Y)+C*Y);
			}
			{
				long x=max(0L,C-B+a);
				//c=max(0,C-B+a)=x
				//c(Z-Y)+CY+d(W-Y)=x(Z-Y)+CY+d(W-Y)
				if(W>=Y)ans=max(ans,a*X+x*(Z-Y)+C*Y+rd*(W-Y));
				else ans=max(ans,a*X+x*(Z-Y)+C*Y);
			}
		}
	}
	return ans;
}
long naive()
{
	long ans=0;
	for(long a=0;a<=A;a++)for(long b=0;a+b<=B;b++)for(long c=0;a+c<=A&&b+c<=C;c++)
	{
		long d=min(A-a-c,min(B-a-b,C-b-c));
		ans=max(ans,a*X+b*Y+c*Z+d*W);
	}
	return ans;
}
int main()
{
	/*
	mt19937 rng(114514);
	for(A=0;A<=10;A++)for(B=0;B<=10;B++)for(C=0;C<=10;C++)
	{
		for(int tm=0;tm<100;tm++)
		{
			X=rng()%(int)1e9+1;
			Y=rng()%(int)1e9+1;
			Z=rng()%(int)1e9+1;
			W=rng()%(int)1e9+1;
			if(solve()!=naive())
			{
				cout<<A<<" "<<B<<" "<<C<<" "<<X<<" "<<Y<<" "<<Z<<" "<<W<<endl;
				return 1;
			}
		}
	}
	return 0;
	*/
	int T;cin>>T;
	for(;T--;)
	{
		cin>>A>>B>>C>>X>>Y>>Z>>W;
		cout<<solve()<<"\n";
	}
}
0