結果

問題 No.385 カップ麺生活
ユーザー 37zigen37zigen
提出日時 2016-07-02 04:27:03
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,615 bytes
コンパイル時間 727 ms
コンパイル使用メモリ 63,028 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-20 07:08:58
合計ジャッジ時間 1,700 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 2 ms
6,940 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 4 ms
6,944 KB
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 WA -
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 -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)

const int inf = 1e9;

bool is_prime[10001];
bool used[10001];
bool can_make[10001];
int memo[10001];
int memo2[10001];

int M, N, C[21];

void sieve()
{
	fill(is_prime, is_prime + 10001, true);

	is_prime[0] = is_prime[1] = false;

	for (int i = 2; i <= 10000; ++i) {
		if (!is_prime[i]) continue;
		is_prime[i] = true;

		for (int j = i * 2; j <= 10000; j += i) {
			is_prime[j] = false;
		}
	}
}

int calc(int a)
{
	if (a == 0)return 0;
	int& res = memo[a];

	if (~res) return res;

	res = -9999999;

	rep(i, N) {
		if (C[i] < 0)continue;
		if (a - C[i] < 0) continue;
		res = max(res, 1 + calc(a - C[i]));
	}
	memo[a] = res;
	return res;
}


int calc2(int a)
{
	if (a == 0)return 0;
	int& res = memo2[a];

	if (~res) return res;

	res = 0;

	rep(i, N) {
		if (C[i] < 0)continue;
		if (a - C[i] < 0) continue;
		res = max(res, 1 + calc2(a - C[i]));
	}
	memo2[a] = res;
	return res;
}

signed main()
{
	cin >> M >> N;
	rep(i, N) cin >> C[i];

	sort(C, C + N);

	sieve();
	fill(memo, memo + 10001, -1);
	fill(memo2, memo2 + 10001, -1);

	can_make[0] = true;

	for (int i = 1; i < M; i++) {
		for (int j = 0; j <N; j++) {
			can_make[i] = can_make[i] || can_make[i - C[j]];
		}
	}


	int ans = calc2(M);

	for (int i = M - 1; i >= 1; i--) {
		if (is_prime[i] && can_make[i]) {
			ans += calc(M - i);
		}
	}	

	cout << ans << endl;
}
0