結果

問題 No.385 カップ麺生活
ユーザー YoshiRyuYoshiRyu
提出日時 2017-02-03 17:49:02
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,006 bytes
コンパイル時間 1,794 ms
コンパイル使用メモリ 151,284 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-25 18:27:03
合計ジャッジ時間 4,073 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 WA -
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 RE -
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 RE -
testcase_16 AC 2 ms
4,380 KB
testcase_17 RE -
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 RE -
testcase_23 AC 2 ms
4,376 KB
testcase_24 RE -
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 1 ms
4,376 KB
testcase_31 RE -
testcase_32 AC 2 ms
4,376 KB
testcase_33 AC 1 ms
4,376 KB
testcase_34 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

// マクロ群
#define REP(i,n) for(int i=0;i<n;++i)
#define REP2(i,a,b) for (int i=(a);i<(b);++i)
#define rep(n) REP(i,n)
#define SF(f,v) scanf(f,v)
#define PF(f,v) printf(f,v)

using namespace std;

static vector<bool> PrimeFLG;

void MakePrimeFLG(int period)
{
	// 初期化
	PrimeFLG = vector<bool>(period + 1, true);
	PrimeFLG[0] = false;
	PrimeFLG[1] = false;

	//// エラトステネスの篩を使って素数ではない物を更新する

	for (int i = 2; i * i < period; i++)	// √priode　まで繰り返す
		if (PrimeFLG[i] == true)	// 素数の時だけ
			for (int j = i * i; j < period; j += i)	// i を軸に倍々ループ
				PrimeFLG[j] = false;	// i からなるすべての倍数は素数ではない
}

void Slove()
{
	int M, N;

	SF("%d", &M);	// 初期所持金
	SF("%d", &N);	// カップ麺の種類
	vector<int> C(N);
	REP(n, N) SF("%d", &C[n]);	// 種類ごとの価格

	sort(C.begin(), C.end());	// 小さい順に並べ替え

	// 素数のフラグリストを作る
	MakePrimeFLG(M);

	// 金額分の要素を持ったリストを作成する
	vector<int> dp = vector<int>(M, -1);	// -1で初期化

	// 残額をキーとして、その残額になったときに、
	// 何個のカップ麺を買えたかをリストに記憶する
	dp[M] = 0;
	for (int money = M; money != -1; --money)
	{
		if (dp[money] == -1) continue;

		for (int kind = 0; kind < N; ++kind)
		{
			if (money - C[kind] > -1)
			{
				dp[money - C[kind]] = dp[money - C[kind]] > dp[money] + 1
									? dp[money - C[kind]]
									: dp[money] + 1;
			}
			else break;
		}
	}

	int ans = 0;

	// 一番多く買えた個数を結果に対して加算
	ans += *max_element(dp.begin(), dp.end());

	// 素数の残額キーに記憶された購入個数分はノーリスクで
	// 手に入ったこととなるため、その分を結果に対して加算
	REP(m, M) if (dp[m] > -1 && PrimeFLG[m] == true) ans += dp[m];

	PF("%d\n", ans);
}

int main()
{
	Slove();
}
0