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

• 問題: No.158 奇妙なお使い
• ユーザー: hiyokko2
• 提出日時: 2016-08-06 16:40:44
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,740 bytes
• コンパイル時間: 1,339 ms
• コンパイル使用メモリ: 161,412 KB
• 実行使用メモリ: 49,408 KB
• 最終ジャッジ日時: 2024-04-24 19:10:10
• 合計ジャッジ時間: 5,101 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	13 ms; 47,104 KB
testcase_04	WA	-
testcase_05	AC	13 ms; 47,080 KB
testcase_06	AC	13 ms; 46,976 KB
testcase_07	AC	13 ms; 47,080 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	14 ms; 47,508 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-

ソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
//#define int long long
using namespace std;

struct A
{
	int A1000, A100, A1;
	A(int A1000, int A100, int A1) : A1000(A1000), A100(A100), A1(A1) {}
	A() {}
};

A a, b, c;
int Db, Dc;
int dp[11][101][10001];

//preA:元々持っていた各硬貨の枚数
//D:一回のお使いで支払う額
//getB:一回のお使いで得る硬貨の枚数
//返り値:そのお使いをした後の硬貨の枚数のリスト
vector<A> get_next_As(A preA, int D, A getB)
{
	vector<A> ret;
	
	for (int a1000 = 0; a1000 <= min(D / 1000, preA.A1000); a1000++)
	{
		for (int a100 = 0; a100 <= min(D / 100, preA.A100); a100++)
		{
			int rest = D - 1000 * a1000 - 100 * a100;
			if (0 <= rest && rest <= preA.A1)
			{
				ret.push_back(A(preA.A1000 - a1000 + getB.A1000, preA.A100 - a100 + getB.A100, preA.A1 - rest + getB.A1));
			}
		}
	}

	return ret;
}

int rec(A a)
{
	if (dp[a.A1000][a.A100][a.A1] != -1)
	{
		return dp[a.A1000][a.A100][a.A1];
	}

	int res = 0;

	vector<A> next_As1 = get_next_As(a, Db, b);
	rep(i,next_As1.size())
	{
		res = max(res, rec(next_As1[i])) + 1;
	}

	vector<A> next_As2 = get_next_As(a, Dc, c);
	rep(i,next_As2.size())
	{
		res = max(res, rec(next_As2[i])) + 1;
	}

	return dp[a.A1000][a.A100][a.A1] = res;
}

signed main()
{
	/*
	vector<A> ret = get_next_As(
			A(5, 20, 1000),
			1000,
			A(100, 0, 0)
		);

	rep(i,ret.size())
	{
		printf("A1000 = %d, A100 = %d, A1 = %d\n", ret[i].A1000, ret[i].A100, ret[i].A1);
	}

	cout << "aaa" << endl;
	*/

	cin >> a.A1000 >> a.A100 >> a.A1;
	cin >> Db;
	cin >> b.A1000 >> b.A100 >> b.A1;
	cin >> Dc;
	cin >> c.A1000 >> c.A100 >> c.A1;

	rep(i,11) rep(j,101) rep(k,10001) dp[i][j][k] = -1;

	printf("%d\n", rec(a));
}