結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-14 18:38:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 1,642 bytes |
コンパイル時間 | 657 ms |
コンパイル使用メモリ | 84,992 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:41:44 |
合計ジャッジ時間 | 2,108 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
/* -*- coding: utf-8 -*-** 385.cc: No.385 カップ麺生活 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_M = 10000;const int MAX_N = 20;/* typedef */typedef long long ll;/* global variables */int cs[MAX_N], dp[2][MAX_M + 1];bool primes[MAX_M + 1];/* subroutines */void gen_primes(int maxp) {memset(primes, true, sizeof(primes));primes[0] = primes[1] = false;int p;for (p = 2; p * p <= maxp; p++)if (primes[p])for (int q = p * p; q <= maxp; q += p) primes[q] = false;}/* main */int main() {int m, n;cin >> m >> n;for (int i = 0; i < n; i++) cin >> cs[i];memset(dp, -1, sizeof(dp));dp[0][0] = 0;int cur = 0, nxt = 1;for (int i = 0; i < n; i++) {memcpy(dp[nxt], dp[cur], sizeof(dp[cur]));for (int c = cs[i], v = 1; c <= m; c += cs[i], v++)for (int j0 = 0, j1 = c; j1 <= m; j0++, j1++)if (dp[cur][j0] >= 0) {int d = dp[cur][j0] + v;if (dp[nxt][j1] < d) dp[nxt][j1] = d;}cur ^= 1, nxt ^= 1;}gen_primes(m);int sum = 0, maxd = 0;for (int i = 1; i <= m; i++)if (dp[cur][i] >= 0) {//printf("dp[%d]=%d(%d)\n", i, dp[cur][i], primes[m - i]);if (primes[m - i]) sum += dp[cur][i];if (maxd < dp[cur][i]) maxd = dp[cur][i];}printf("%d\n", sum + maxd);return 0;}