結果

問題 No.385 カップ麺生活
ユーザー YoshiRyuYoshiRyu
提出日時 2017-02-03 18:17:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,115 bytes
コンパイル時間 1,559 ms
コンパイル使用メモリ 165,928 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-15 07:37:46
合計ジャッジ時間 2,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,948 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 1 ms
6,944 KB
testcase_30 AC 2 ms
6,944 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void Slove()’:
main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    7 | #define SF(f,v) scanf(f,v)
      |                 ~~~~~^~~~~
main.cpp:33:9: note: in expansion of macro ‘SF’
   33 |         SF("%d", &M);   // 初期所持金
      |         ^~
main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    7 | #define SF(f,v) scanf(f,v)
      |                 ~~~~~^~~~~
main.cpp:34:9: note: in expansion of macro ‘SF’
   34 |         SF("%d", &N);   // カップ麺の種類
      |         ^~
main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    7 | #define SF(f,v) scanf(f,v)
      |                 ~~~~~^~~~~
main.cpp:36:19: note: in expansion of macro ‘SF’
   36 |         REP(n, N) SF("%d", &C[n]);      // 種類ごとの価格
      |                   ^~

ソースコード

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);

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

	// 残額をキーとして、その残額になったときに、何個のカップ麺を買えたかをリストに記憶する
	dp[M] = 0;
	for (int money = M; money >= 0; --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];

	/*REP(m, M) if (dp[m] != -1)
	{
		PF("%4d :", m);
		PF("%d\n", dp[m]);
	}

	PF("__%d\n", ans);*/


	PF("%d", ans);
}

int main()
{
	Slove();
	return 0;
}
0