結果

問題 No.385 カップ麺生活
ユーザー srup٩(๑`н´๑)۶
提出日時 2016-07-15 17:13:44
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,306 bytes
コンパイル時間 789 ms
コンパイル使用メモリ 66,320 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-04 22:42:04
合計ジャッジ時間 1,697 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
int dp[10010];
int prime[10010];//i
bool isprime[10010];//truei
//
void eratos(int m){
for (int i = 0; i <= m; ++i) isprime[i] = true;
isprime[0] = isprime[1] = false;
//ii
int p = 0;
for (int i = 2; i <= m; ++i){
if(isprime[i]){
prime[p] = i; p++;
for (int j = 2 * i; j <= m; j += i){
isprime[j] = false;
}
}
}
return;
}
int main(void){
int m, n; cin >> m >> n;
eratos(m);
vector<int> c(n);
rep(i, n) cin >> c[i];
sort(c.begin(), c.end());
memset(dp, -1, sizeof(dp));
dp[m] = 0;
for (int i = m; i >= 0; --i){//
for (int j = 0; j < n; ++j){//調
if(i - c[j] >= 0 && dp[i] >= 0){
dp[i - c[j]] = max(dp[i - c[j]], dp[i] + 1);
}
}
}
int ans = 0;
//
for (int i = 0; i <= m; ++i){
if(dp[i] != -1 && isprime[i] == true) ans += dp[i];
}
//
while(m > 0){
if(m - c[0] >= 0) ans++;
m -= c[0];
}
printf("%d\n", ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0