結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-15 17:13:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,306 bytes |
コンパイル時間 | 789 ms |
コンパイル使用メモリ | 66,320 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-04 22:42:04 |
合計ジャッジ時間 | 1,697 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <iostream>#include <cstdio>#include <algorithm>#include <vector>#include <cstring>using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)int dp[10010];int prime[10010];//i番目の素数bool isprime[10010];//trueならiは素数//エラトテネスvoid eratos(int m){for (int i = 0; i <= m; ++i) isprime[i] = true;isprime[0] = isprime[1] = false;//iを残してiの倍数を消していくint p = 0;for (int i = 2; i <= m; ++i){if(isprime[i]){prime[p] = i; p++;for (int j = 2 * i; j <= m; j += i){isprime[j] = false;}}}return;}int main(void){int m, n; cin >> m >> n;eratos(m);vector<int> c(n);rep(i, n) cin >> c[i];sort(c.begin(), c.end());memset(dp, -1, sizeof(dp));dp[m] = 0;for (int i = m; i >= 0; --i){//所持金の残りfor (int j = 0; j < n; ++j){//すべてのカップ麺を調べるif(i - c[j] >= 0 && dp[i] >= 0){dp[i - c[j]] = max(dp[i - c[j]], dp[i] + 1);}}}int ans = 0;//残りの所持金が素数の時for (int i = 0; i <= m; ++i){if(dp[i] != -1 && isprime[i] == true) ans += dp[i];}//残りの所持金が素数の時をすべて廻ったあとは一番安いカップ麺を買えばいいwhile(m > 0){if(m - c[0] >= 0) ans++;m -= c[0];}printf("%d\n", ans);}