結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-07 19:52:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 1,489 ms |
コンパイル使用メモリ | 161,924 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:40:33 |
合計ジャッジ時間 | 2,486 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#define rep(i, a, n) for(int i = a; i < n; i++)#define repp(i, n) rep(i, 0, n)#define repb(i, a, b) for(int i = a; i >= b; i--)#define all(a) a.begin(), a.end()#define int long longusing namespace std;int prime[10010];bool is_prime[10010];void sieve(int n){int p = 0;rep(i, 0, n + 1) is_prime[i] = true;is_prime[0] = is_prime[1] = false;rep(i, 2, n + 1){if(is_prime[i]) prime[p++] = i;for(int j = 2*i; j <= n; j += i) is_prime[j] = false;}return;}int dp[10010];signed main(){int m, n;cin >> m >> n;sieve(m);vector<int> c(n);rep(i, 0, n) cin >> c[i];// dp[m] = 1;rep(i, 0, n){repb(j, m, 0){if(j + c[i] <= m && (dp[j + c[i]] != 0 || j + c[i] == m)){dp[j] = max(dp[j], dp[j + c[i]] + 1);}}}int ans = 0, MAX = 0;rep(i, 0, m){// cout << i << ' ' << dp[i] << endl;if(is_prime[i]){// cout << i << " " << dp[i] << endl;ans += dp[i];}MAX = max(MAX, dp[i]);}cout << ans + MAX << endl;}