結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-01 23:25:35 |
言語 | C++14 (gcc 8.3.0) |
結果 |
AC
|
実行時間 | 8 ms |
コード長 | 1,611 Byte |
コンパイル時間 | 1,843 ms |
使用メモリ | 3,148 KB |
最終ジャッジ日時 | 2019-12-05 06:09:24 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
99_system_test1.txt | AC | 4 ms
1,548 KB |
sample01.txt | AC | 3 ms
1,540 KB |
sample02.txt | AC | 4 ms
1,568 KB |
sample03.txt | AC | 5 ms
1,644 KB |
system_test1.txt | AC | 4 ms
1,596 KB |
system_test2.txt | AC | 4 ms
1,824 KB |
system_test3.txt | AC | 5 ms
1,680 KB |
system_test4.txt | AC | 4 ms
1,676 KB |
test01.txt | AC | 4 ms
1,532 KB |
test02.txt | AC | 7 ms
3,148 KB |
test03.txt | AC | 4 ms
1,528 KB |
test04.txt | AC | 4 ms
1,676 KB |
test05.txt | AC | 5 ms
1,828 KB |
test06.txt | AC | 6 ms
2,092 KB |
z_gen_case1.txt | AC | 5 ms
1,828 KB |
z_gen_case2.txt | AC | 4 ms
1,628 KB |
z_gen_case3.txt | AC | 6 ms
2,356 KB |
z_gen_case4.txt | AC | 5 ms
1,824 KB |
z_gen_case5.txt | AC | 5 ms
1,676 KB |
z_gen_case6.txt | AC | 6 ms
1,828 KB |
z_gen_case7.txt | AC | 8 ms
2,088 KB |
z_gen_case8.txt | AC | 5 ms
1,824 KB |
z_gen_case9.txt | AC | 6 ms
2,088 KB |
z_gen_case10.txt | AC | 7 ms
2,088 KB |
z_gen_case11.txt | AC | 4 ms
1,580 KB |
z_gen_case12.txt | AC | 5 ms
1,736 KB |
z_gen_case13.txt | AC | 5 ms
1,828 KB |
z_gen_case14.txt | AC | 6 ms
1,828 KB |
z_gen_case15.txt | AC | 4 ms
1,680 KB |
z_gen_case16.txt | AC | 6 ms
2,092 KB |
z_gen_case17.txt | AC | 5 ms
1,572 KB |
z_gen_case18.txt | AC | 5 ms
1,680 KB |
z_gen_case19.txt | AC | 6 ms
2,088 KB |
z_gen_case20.txt | AC | 4 ms
1,716 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int, int> Pii; typedef tuple<int, int, int> TUPLE; typedef vector<int> V; typedef vector<V> VV; typedef vector<VV> VVV; typedef vector<vector<int>> Graph; const int inf = 1e9; const int mod = 1e9 + 7; // x > 0 bool isPrime(int n) { for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return n != 1; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int M, N; cin >> M >> N; V C(N); rep(i, N) cin >> C[i]; VV dp(N + 1, V(M + 1, -inf)); // Cの部分和 最大何個で作れるか dp[0][0] = 0; rep(i, N) { rep(j, M + 1) { if (j < C[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - C[i]] + 1); } } } // rep(i, N + 1) { // rep(j, M + 1) { // cout << dp[i][j] << " "; // } // cout << endl; // } int ans = 0; rep2(i, 1, M) { // cout << M - i << endl; if (dp[N][i] > 0 && isPrime(M - i)) { // cout << M - i << " " << ans << " " << dp[N][M - i] << endl; ans += dp[N][i]; } } ans += *max_element(all(dp[N])); cout << ans << endl; }