結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2016-07-01 22:40:56 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,046 bytes |
コンパイル時間 | 1,445 ms |
コンパイル使用メモリ | 163,008 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:24:00 |
合計ジャッジ時間 | 2,422 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T1, class T2> bool chmin(T1 &a, T2 b) { if (b < a) { a = b; return true; } return false; }template<class T1, class T2> bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; }int main() {vector<bool> is_prime(10101, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i < 10101; i++) {if (is_prime[i]) {for (int j = i * 2; j < 10101; j += i) {is_prime[j] = false;}}}int m, n;cin >> m >> n;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];static int dp[22][10101];fill_n(*dp, 22 * 10101, -1e9);dp[0][0] = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= m; j++) {chmax(dp[i + 1][j], dp[i][j]);if (j - a[i] >= 0) chmax(dp[i + 1][j], dp[i + 1][j - a[i]] + 1);}}int mx = 0;for (int i = 0; i <= m; i++) {mx = max(mx, dp[n][i]);}long long sum = mx;for (int i = 0; i <= m; i++) {if (is_prime[m - i]) {if (dp[n][i] >= 0) sum += dp[n][i];}}cout << sum << endl;}