結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2016-07-02 19:44:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,913 bytes |
コンパイル時間 | 1,551 ms |
コンパイル使用メモリ | 171,192 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:37:42 |
合計ジャッジ時間 | 2,474 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;using i32 = int32_t; using i64 = int64_t; using str = string;using u32 = uint32_t; using u64 = uint64_t; using usize = size_t;using f64 = double_t; template <typename T> using vec = vector<T>;#define times(n, i) for (i64 i = 0; i < (n); ++i)#define range(n, m, i) for (i64 i = (n); i < (m); ++i)#define upto(n, m, i) for (i64 i = (n); i <= (m); ++i)#define downto(n, m, i) for (i64 i = (n); i >= (m); --i)#define foreach(xs, x) for (auto &x : (xs))#define all(xs) (xs).begin(), (xs).end()#define sortall(xs) sort(all(xs))#define reverseall(xs) reverse(all(xs))#define uniqueall(xs) (xs).erase(unique(all(xs)), (xs).end())#define maximum(xs) (*max_element(all(xs)))#define minimum(xs) (*min_element(all(xs)))#define even(x) (((x) & 1) == 0)#define odd(x) (((x) & 1) == 1)#define append emplace_backconst i64 MOD = 1000000007;i32 m, n;vec<i32> c;vec<i32> primes;void init_primes() {i32 tmp[10001];upto(2, m, x) {tmp[x] = 1;}range(2, sqrt(m), i) {if (tmp[i]) {for (int j = 0; i*(j+2) <= m; j++) {tmp[i*(j+2)] = 0;}}}upto(2, m, x) {if (tmp[x])primes.append(x);}}i32 main(){cin >> m >> n;c.resize(n);times(n, i) {cin >> c[i];}init_primes();i32 dp[21][10001];times(n, i) {upto(0, m, j) {if (j != c[i] && dp[i][j] == 0 && (j >= c[i] && dp[i+1][j-c[i]] == 0))continue;if (j < c[i])dp[i+1][j] = dp[i][j];elsedp[i+1][j] = max(dp[i][j], dp[i+1][j-c[i]] + 1);}}i64 ans = m / minimum(c);times(primes.size(), i) {ans += dp[n][m-primes[i]];}cout << ans << endl;return 0;}