結果

問題 No.2309 [Cherry 5th Tune D] 夏の先取り
ユーザー kotatsugamekotatsugame
提出日時 2023-05-19 22:07:19
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 4 ms
6,820 KB
testcase_02 AC 3 ms
6,816 KB
testcase_03 AC 4 ms
6,820 KB
testcase_04 AC 3 ms
6,820 KB
testcase_05 AC 4 ms
6,820 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 3 ms
6,816 KB
testcase_09 AC 4 ms
6,816 KB
testcase_10 AC 4 ms
6,816 KB
testcase_11 AC 4 ms
6,820 KB
testcase_12 AC 4 ms
6,820 KB
testcase_13 AC 4 ms
6,816 KB
testcase_14 AC 3 ms
6,820 KB
testcase_15 AC 5 ms
6,820 KB
testcase_16 AC 3 ms
6,820 KB
testcase_17 AC 4 ms
6,816 KB
testcase_18 AC 4 ms
6,820 KB
testcase_19 AC 3 ms
6,816 KB
testcase_20 AC 4 ms
6,816 KB
testcase_21 AC 3 ms
6,816 KB
testcase_22 AC 3 ms
6,816 KB
testcase_23 AC 3 ms
6,820 KB
testcase_24 AC 4 ms
6,816 KB
testcase_25 AC 3 ms
6,816 KB
testcase_26 AC 5 ms
6,816 KB
testcase_27 AC 4 ms
6,816 KB
testcase_28 AC 4 ms
6,816 KB
testcase_29 AC 5 ms
6,820 KB
testcase_30 AC 4 ms
6,816 KB
testcase_31 AC 7 ms
6,816 KB
testcase_32 AC 7 ms
6,816 KB
testcase_33 AC 7 ms
6,816 KB
testcase_34 AC 6 ms
6,820 KB
testcase_35 AC 7 ms
6,820 KB
testcase_36 AC 2 ms
6,820 KB
testcase_37 AC 2 ms
6,816 KB
testcase_38 AC 2 ms
6,820 KB
testcase_39 AC 2 ms
6,816 KB
testcase_40 AC 1 ms
6,820 KB
testcase_41 AC 8 ms
6,816 KB
testcase_42 AC 7 ms
6,816 KB
testcase_43 AC 4 ms
6,820 KB
testcase_44 AC 3 ms
6,816 KB
testcase_45 AC 3 ms
6,816 KB
testcase_46 AC 3 ms
6,816 KB
testcase_47 AC 2 ms
6,820 KB
testcase_48 AC 2 ms
6,820 KB
testcase_49 AC 3 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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