結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-02 02:38:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 750 ms |
コンパイル使用メモリ | 99,628 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:31:34 |
合計ジャッジ時間 | 1,876 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <cstdio>#include <iostream>#include <vector>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <string>#include <cstring>#include <sstream>#include <algorithm>#include <functional>#include <queue>#include <stack>#include <cmath>#include <iomanip>#include <list>#include <tuple>#include <bitset>using namespace std;#define int long long#define rep(i,n) for(int i = 0;i < n;i++)//[0,n]まで素数表を返すvector<bool> makePrimeTable(int n) {//エラトステネスの篩を用いて素数表を作成//era[i] iが素数ならtruevector<bool> era(n + 1, true);//0と1を素数として扱ったほうが良い場合に注意era[0] = false;era[1] = false;for (int i = 2; i <= n; i++) {if (era[i]) {for (int j = i * 2; j <= n; j += i) {era[j] = 0;}}}return era;}int me[10001];//me[i] = 所持金をiにする際、買うことのできるカップ麺の最大個数signed main() {int m, n;cin >> m >> n;vector<int> c(n);for (int i = 0; i < n; i++) {cin >> c[i];}auto tb = makePrimeTable(m);queue<int> q;q.push(m);while (q.size()) {auto nw = q.front();q.pop();rep(i, n) {int t = nw - c[i];if (t >= 0) {if (me[t] < me[nw] + 1) {me[t] = me[nw] + 1;q.push(t);}}}}int ma = 0;int sum = 0;for (int i = 0; i <= m; i++) {ma = max(ma, me[i]);if (tb[i]) {sum += me[i];}}cout << sum + ma << endl;return 0;}