結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2024-08-21 22:45:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 2,071 ms |
コンパイル使用メモリ | 193,072 KB |
最終ジャッジ日時 | 2025-02-23 23:16:45 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair<ll,ll>#define pii pair<ll,pair<ll,ll>>#define iip pair<pair<ll,ll>,ll>#define ppii pair<pair<ll,ll>,pair<ll,ll>>#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i<=r;i++)#define _For(i,l,r) for(int i=r;i>=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=21,M=1e4+10;inline ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;}inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}ll m,n,ans,Min=1e9,cnt;ll a[N],dp[M],P[M];bool F[M];void init(){memset(dp,-1,sizeof(dp));dp[m]=0;_For(i,0,m)if(dp[i]>=0)For(j,1,n)if(a[j]<=i)dp[i-a[j]]=max(dp[i-a[j]],dp[i]+1);For(i,2,m){if(!F[i])P[++cnt]=i;For(j,1,cnt){if(i*P[j]>m)break;F[i*P[j]]=1;if(i%P[j]==0)break;}}}bool End;int main(){m=read(),n=read();For(i,1,n){a[i]=read();Min=min(Min,a[i]);}init();ans=m/Min;For(i,2,m)if(!F[i]&&dp[i]>0)ans+=dp[i];write(ans);//cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";return 0;}