#14159 (C90) No.158 奇妙なお使い

• 問題: No.158 奇妙なお使い
• ユーザー: ぴろず
• 提出日時: 2015-02-27 00:28:00
• 言語: C90 (gcc 11.4.0)
• 結果: AC
• 実行時間: 629 ms / 5,000 ms
• コード長: 1,133 bytes
• コンパイル時間: 777 ms
• コンパイル使用メモリ: 26,380 KB
• 実行使用メモリ: 46,168 KB
• 最終ジャッジ日時: 2023-09-11 07:52:46
• 合計ジャッジ時間: 3,347 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	16 ms; 45,196 KB
testcase_01	AC	18 ms; 45,308 KB
testcase_02	AC	16 ms; 45,252 KB
testcase_03	AC	15 ms; 45,248 KB
testcase_04	AC	629 ms; 46,168 KB
testcase_05	AC	16 ms; 45,284 KB
testcase_06	AC	16 ms; 45,184 KB
testcase_07	AC	16 ms; 45,296 KB
testcase_08	AC	15 ms; 45,116 KB
testcase_09	AC	16 ms; 45,180 KB
testcase_10	AC	16 ms; 45,156 KB
testcase_11	AC	16 ms; 45,176 KB
testcase_12	AC	16 ms; 45,296 KB
testcase_13	AC	15 ms; 45,148 KB
testcase_14	AC	18 ms; 45,204 KB
testcase_15	AC	27 ms; 45,312 KB
testcase_16	AC	23 ms; 45,208 KB
testcase_17	AC	72 ms; 45,328 KB
testcase_18	AC	22 ms; 45,340 KB
testcase_19	AC	16 ms; 45,252 KB
testcase_20	AC	19 ms; 45,232 KB
testcase_21	AC	16 ms; 45,500 KB
testcase_22	AC	17 ms; 46,104 KB
testcase_23	AC	16 ms; 45,284 KB
testcase_24	AC	16 ms; 45,288 KB
testcase_25	AC	16 ms; 45,136 KB
testcase_26	AC	18 ms; 45,124 KB
testcase_27	AC	16 ms; 45,188 KB
testcase_28	AC	46 ms; 45,212 KB
testcase_29	AC	16 ms; 45,260 KB
testcase_30	AC	48 ms; 45,296 KB

ソースコード

#include <stdio.h>
#include <math.h>

int a1000;
int a100;
int a1;
int b1000;
int b100;
int b1;
int db;
int c1000;
int c100;
int c1;
int dc;
int dp[11][101][10001];
int max(int a,int b) {
	return a > b ? a : b;
}
int dfs(int a,int b,int c) {
	int i,j;
		if (a < 0 || b < 0 || c < 0) {
			return 0; //苦し紛れ
		}
		if (dp[a][b][c] >= 0) {
			return dp[a][b][c];
		}
		int ret = 0;
		for(i=0;i<=a;i++) {
			for(j=0;j<=b;j++) {
				int bx = db - i * 1000 - j * 100;
				if (bx >= 0 && bx <= c) {
					ret = max(ret, dfs(a-i+b1000, b-j+b100, c-bx+b1) + 1);
				}
				int cx = dc - i * 1000 - j * 100;
				if (cx >= 0 && cx <= c) {
					ret = max(ret, dfs(a-i+c1000, b-j+c100, c-cx+c1) + 1);
				}
			}
		}
		return dp[a][b][c] = ret;
	}
int main() {
	scanf("%d",&a1000);
	scanf("%d",&a100);
	scanf("%d",&a1);
	scanf("%d",&db);
	scanf("%d",&b1000);
	scanf("%d",&b100);
	scanf("%d",&b1);
	scanf("%d",&dc);
	scanf("%d",&c1000);
	scanf("%d",&c100);
	scanf("%d",&c1);
	int i,j,k;
	for(i=0;i<=10;i++) {
		for(j=0;j<=100;j++) {
			for(k=0;k<=10000;k++) {
				dp[i][j][k] = -1;
			}
		}
	}
	printf("%d\n",dfs(a1000,a100,a1));
	return 0;

}