結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2017-02-03 18:17:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 1,480 ms |
コンパイル使用メモリ | 166,820 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:54:44 |
合計ジャッジ時間 | 2,042 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘void Slove()’: main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 7 | #define SF(f,v) scanf(f,v) | ~~~~~^~~~~ main.cpp:33:9: note: in expansion of macro ‘SF’ 33 | SF("%d", &M); // 初期所持金 | ^~ main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 7 | #define SF(f,v) scanf(f,v) | ~~~~~^~~~~ main.cpp:34:9: note: in expansion of macro ‘SF’ 34 | SF("%d", &N); // カップ麺の種類 | ^~ main.cpp:7:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 7 | #define SF(f,v) scanf(f,v) | ~~~~~^~~~~ main.cpp:36:19: note: in expansion of macro ‘SF’ 36 | REP(n, N) SF("%d", &C[n]); // 種類ごとの価格 | ^~
ソースコード
#include "bits/stdc++.h"// マクロ群#define REP(i,n) for(int i=0;i<n;++i)#define REP2(i,a,b) for (int i=(a);i<(b);++i)#define rep(n) REP(i,n)#define SF(f,v) scanf(f,v)#define PF(f,v) printf(f,v)using namespace std;static vector<bool> PrimeFLG;void MakePrimeFLG(int period){// 初期化PrimeFLG = vector<bool>(period + 1, true);PrimeFLG[0] = false;PrimeFLG[1] = false;//// エラトステネスの篩を使って素数ではない物を更新するfor (int i = 2; i * i < period; i++) // √priode まで繰り返すif (PrimeFLG[i] == true) // 素数の時だけfor (int j = i * i; j < period; j += i) // i を軸に倍々ループPrimeFLG[j] = false; // i からなるすべての倍数は素数ではない}void Slove(){int M, N;SF("%d", &M); // 初期所持金SF("%d", &N); // カップ麺の種類vector<int> C(N);REP(n, N) SF("%d", &C[n]); // 種類ごとの価格sort(C.begin(), C.end()); // 小さい順に並べ替え// 素数のフラグリストを作るMakePrimeFLG(M);// 金額分の要素を持ったリストを作成する(-1で初期化)vector<int> dp = vector<int>(M + 1, -1);// 残額をキーとして、その残額になったときに、何個のカップ麺を買えたかをリストに記憶するdp[M] = 0;for (int money = M; money >= 0; --money){if (dp[money] <= -1) continue;for (int kind = 0; kind < N; ++kind){if (money - C[kind] > -1){dp[money - C[kind]] = dp[money - C[kind]] > dp[money] + 1? dp[money - C[kind]]: dp[money] + 1;}else break;}}int ans = 0;// 一番多く買えた個数を結果に対して加算ans += *max_element(dp.begin(), dp.end());// 素数の残額キーに記憶された購入個数分はノーリスクで// 手に入ったこととなるため、その分を結果に対して加算REP(m, M) if (dp[m] > -1 && PrimeFLG[m] == true) ans += dp[m];/*REP(m, M) if (dp[m] != -1){PF("%4d :", m);PF("%d\n", dp[m]);}PF("__%d\n", ans);*/PF("%d", ans);}int main(){Slove();return 0;}