結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2016-07-02 02:18:36 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,421 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 88,756 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-04 22:32:29 |
合計ジャッジ時間 | 1,913 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#define _USE_MATH_DEFINES#include <sstream> //string stream its useful!#include<string>#include<iostream>#include<utility> //pair#include <vector> // vector#include <algorithm> // swap,sort,binary_search#include <functional> // std::greater#include <map> //map#include<set> //set#include<queue> //queue#include<list> //list#include<cmath>#include<numeric>#include<cassert>#include <iomanip> //cout<<setprecisiontypedef long long ll;#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))using namespace std;void omajinai() {cin.tie(0);ios::sync_with_stdio(false);cout<<setprecision(15);//freopen("txt.csv","r",stdin);}template<int T>vector<int> makesosuarray(){vector<int> ve(T,1);int k = ceil(sqrt(T));for(int j = 2; j < k;j++){if(ve[j] == 0) continue;for(int l = j*2; l<=T;l+=j) ve[l] = 0;}ve[0] = 0; ve[1] = 0;return ve;}vector<int> sosu = makesosuarray<10000>();int main(){omajinai();int m,n;cin>>m>>n;vector<int> c(n); for_each(c.begin(),c.end(),[](int &c){cin>>c;});vector<int> l(m+1,-1);l[m] = 0;for(int t: c){for(int i = m-t;i>=0;i--) if(l[i+t]!=-1)l[i] = max(l[i],l[i+t] + 1);}ll ans = 0;for(int i = 0 ; i<=m;i++) if(sosu[i] ==1) ans+=max(0,l[i]);ans += *max_element(l.begin(),l.end());cout<<ans<<endl;}