結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2020-11-19 00:17:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,051 bytes |
コンパイル時間 | 1,729 ms |
コンパイル使用メモリ | 172,956 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 09:19:01 |
合計ジャッジ時間 | 2,906 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int nax = 1e4 + 7;vector<int>prime(nax, true);void is_prime() {prime[0] = false;prime[1] = false;for (int i = 2; i < nax; i++) {if (prime[i] && ll(i * i) < nax) {for (int j = i * i; j <= nax; j += i) {prime[j] = false;}}}}int main() {#ifndef ONLINE_JUDGEfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios_base::sync_with_stdio(false);cin.tie(NULL);int n, m;cin >> m >> n;is_prime();vector<int>v(n);for (int i = 0; i < n; i++) {cin >> v[i];}sort(v.begin(), v.end());vector<int>dp(nax, -1);dp[m] = 0;for (int rem = m; rem >= 0; rem--) {for (int rep = 0; rep < n; rep++) {if (rem - v[rep] >= 0 && dp[rem] >= 0) {dp[rem - v[rep]] = max(1 + dp[rem], dp[rem - v[rep]]);}}}int ans = 0;for (int i = 0; i <= m; i++) {if (prime[i] && dp[i] != -1) {ans += dp[i];}}while (m > 0) {if (m - v[0] >= 0) {ans++;}m = m - v[0];}cout << ans << endl;}