結果
問題 | No.385 カップ麺生活 |
ユーザー |
|
提出日時 | 2016-09-07 19:31:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 630 ms |
コンパイル使用メモリ | 73,292 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 22:50:04 |
合計ジャッジ時間 | 1,513 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <vector>#include <iostream>#include <algorithm>#include <iomanip>void primes(std::vector<int>&prime_list, int n) {if(n<2)return;prime_list.resize(n - 2);for (int i = 2; i<n; i++) {prime_list.at(i - 2) = i;}int front_index=0;while (1) {int front = prime_list.at(front_index);auto it = prime_list.begin();while (it != prime_list.end()) {if (*it%front == 0 && *it != front) {it = prime_list.erase(it);} else {++it;}}if (front*front>n)break;++front_index;}}void run(int*node_list, int length, std::vector<int>&cs,int value,int count) {for (auto c : cs) {if (c + value < length&&node_list[c + value]<count) {node_list[c+value]=count;run(node_list,length,cs,c+value,count+1);}}}int buy(int*node_list, std::vector<int>&prime_list,int maney,std::vector<int>&cs) {int sum=0;for (auto v : prime_list) {if (node_list[maney-v] > 0) {sum+=node_list[maney - v];}}sum+=maney/ cs[0];return sum;}int main() {int n, m;std::cin >> m >> n;std::vector<int> cs(n);for (int i = 0; i<n; i++) {std::cin >> cs.at(i);}std::sort(cs.begin(),cs.end());std::vector<int> prime_list;int*node_list=new int[m];for (int i = 0; i < m;i++) {node_list[i]=-1;}node_list[0]=0;run(node_list,m,cs,0,1);primes(prime_list, m);std::cout<<buy(node_list,prime_list,m,cs)<<std::endl;delete[] node_list;}