結果

問題 No.158 奇妙なお使い
ユーザー wing3196
提出日時 2015-02-27 17:26:53
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0