結果
問題 | 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;}