結果
問題 | No.385 カップ麺生活 |
ユーザー |
👑 |
提出日時 | 2022-08-20 23:14:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 887 ms / 2,000 ms |
コード長 | 1,039 bytes |
コンパイル時間 | 813 ms |
コンパイル使用メモリ | 76,780 KB |
最終ジャッジ日時 | 2025-01-31 02:09:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <iostream>#include <vector>using namespace std;struct SieveEratos{vector<bool> t;vector<int> primes;SieveEratos(int n):t(n+1,true){t[0] = t[1] = false;for(int i = 2; n >= i; i++){if(t[i]){primes.emplace_back(i);for(int j = i+i; n >= j; j+=i){t[j] = false;}}}}bool operator[](int x){return t[x];}};int main(){int m,n;cin>>m>>n;vector<long long> A(10001,10001);A[0] = 0;int mn = 1000;for(int i = 0; n > i; i++){int c;cin>>c;mn = min(c,mn);for(int j = 0; 10000 >= j; j++){if(A[j] == 10001)continue;for(int k = j+c; 10000 >= k; k+=c){if(A[k] == 10001)A[k] = A[j]+((k-j)/c);else A[k] = max(A[k],A[j]+((k-j)/c));}}}SieveEratos P(10001);long long ans = 0;for(int i = 1; m > i; i++){if(P[i] && A[m-i] != 10001){ans += A[m-i];}}cout << ans+m/mn << endl;}