結果

問題 No.385 カップ麺生活
ユーザー 37zigen
提出日時 2016-07-02 04:27:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,615 bytes
コンパイル時間 727 ms
コンパイル使用メモリ 63,152 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-12 02:17:09
合計ジャッジ時間 1,642 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 3 WA * 29
権限があれば一括ダウンロードができます

ソースコード

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