結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-01 23:09:12 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,271 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 55,952 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:25:56 |
合計ジャッジ時間 | 1,305 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <iostream> #include <cstring> using namespace std; const int kMAX_M = 10010; const int kMAX_N = 30; int M, N; int C[kMAX_N]; int can_adjust[kMAX_M]; bool IsPrime(int num) { if (num == 0 || num == 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } void Solve() { memset(can_adjust, -1, sizeof(can_adjust)); can_adjust[0] = 0; for (int i = 0; i < N; i++) { for (int price = 0; price <= M; price++) { if (price - C[i] >= 0 && can_adjust[price - C[i]] >= 0) { can_adjust[price] = max(can_adjust[price], can_adjust[price - C[i]] + 1); } } } int answer = 0, max_num = 0; for (int price = 0; price <= M; price++) { int remaining = M - price; if (IsPrime(remaining) && can_adjust[price] > 0) { answer += can_adjust[price]; } max_num = max(max_num, can_adjust[price]); } answer += max_num; cout << answer << endl; } int main() { cin >> M >> N; for (int i = 0; i < N; i++) { cin >> C[i]; } Solve(); /* for (int i = 0; i <= 100; i++) { cout << i << " " << can_adjust[i] << endl; } */ return 0; }