結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-02 07:12:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 858 bytes |
コンパイル時間 | 1,385 ms |
コンパイル使用メモリ | 167,144 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:34:33 |
合計ジャッジ時間 | 2,644 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)int M, N;int C[20];int dp[21][10001];//-----------------------------------------------------------------bool isprime(int n) {if (n <= 1) return false;for (int i = 2; i * i <= n; i++)if (n % i == 0) return false;return true;}//-----------------------------------------------------------------int main() {scanf("%d %d", &M, &N);rep(i, 0, N) scanf("%d", &C[i]);rep(i, 0, N + 1) rep(j, 0, M + 1) dp[i][j] = -1;dp[0][M] = 0;rep(i, 0, N) rep(j, 0, M + 1) if (0 <= dp[i][j]) {rep(k, 0, j / C[i]+1)dp[i + 1][j - k * C[i]] = max(dp[i + 1][j - k * C[i]], dp[i][j] + k);}int ans = 0;int _max = 0;rep(j, 0, M + 1) if (0 <= dp[N][j]) {if (isprime(j)) ans += dp[N][j];_max = max(_max, dp[N][j]);}ans += _max;printf("%d\n", ans);}