#14228 (C++11) No.158 奇妙なお使い

• 問題: No.158 奇妙なお使い
• ユーザー: wing3196
• 提出日時: 2015-02-27 17:26:53
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,263 bytes
• コンパイル時間: 760 ms
• コンパイル使用メモリ: 79,264 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-23 22:40:21
• 合計ジャッジ時間: 1,732 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	WA	-
testcase_03	AC	2 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	WA	-
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	2 ms; 5,376 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	3 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	3 ms; 5,376 KB
testcase_30	AC	9 ms; 5,376 KB

ソースコード

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;

struct Data{
	int a,b,c,cnt;
	Data(){
		a=b=c=-1; cnt=0;
	}
	Data(int _a,int _b,int _c,int _cnt){
		a=_a; b=_b; c=_c; cnt=_cnt;
	}
	Data(Data x,Data y,int d){
		while(x.a>0 && d>=1000){
			d -= 1000;
			x.a--;
		}
		while(x.b>0 && d>=100){
			d -= 100;
			x.b--;
		}
		while(x.c>0 && d>0){
			d--;
			x.c--;
		}
		if(d!=0){
			a=b=c=-1;
		}
		else{
			a = x.a+y.a; b = x.b+y.b; c = x.c+y.c;
			cnt = x.cnt+1;
		}
	}
	bool operator<(const Data &x)const{
		if(a!=x.a) return a<x.a;
		if(b!=x.b) return b<x.b;
		return c<x.c;
	}
	void input(){
		cin>>a>>b>>c;
	}
	int get_sum(){
		return a*1000+b*100+c;
	}
};

Data dp[10000];

int main(){
	Data A,B,C;
	int Db,Dc;
	A.input();
	cin>>Db;
	B.input();
	cin>>Dc;
	C.input();
	dp[A.get_sum()] = A;
	int ans = 0;
	for(int i=A.get_sum();i>=0;i--){
		if(dp[i].a==-1) continue;
		ans = max(ans,dp[i].cnt);
		if(i>=Db) dp[i-Db+B.get_sum()] = max(dp[i-Db+B.get_sum()],Data(dp[i],B,Db));
		if(i>=Dc) dp[i-Dc+C.get_sum()] = max(dp[i-Dc+C.get_sum()],Data(dp[i],C,Dc));
	}
	printf("%d\n",ans);
	return 0;
}