結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2020-06-02 21:46:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,219 bytes |
コンパイル時間 | 1,573 ms |
コンパイル使用メモリ | 163,224 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 23:02:52 |
合計ジャッジ時間 | 1,921 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.02 21:46:20**/#include "bits/stdc++.h"using namespace std;typedef long long ll;int main() {int m;cin >> m;int n;cin >> n;// エラトステネスの篩 O(NloglogN)// N以下の素数int N = m;vector< bool > isprime(N + 1, true);vector< int > prime;isprime[0] = isprime[1] = false;for (int i = 2; i * i <= N; i++) {if (isprime[i]) {for (int j = i + i; j <= N; j += i) {isprime[j] = false;}}}for (int i = 2; i <= N; i++) {if (isprime[i]) {prime.push_back(i);}}constexpr int INF = 1e9 + 6;vector< int > dp(m + 1, -INF);dp[0] = 0;ll ans = 0;for (int i = 0; i < n; i++) {int c;cin >> c;for (int j = c; j <= m; j++) {if (dp[j - c] == -INF) continue;dp[j] = max(dp[j], dp[j - c] + 1);ans = max(ans, (ll)dp[j]);}}for (int i = 0; i < prime.size(); i++) {if (dp[m-prime[i]] == -INF) continue;ans += dp[m-prime[i]];}cout << ans << endl;return 0;}