159342025-03-24 18:25:21peti1234Az óvodai lét elviselhetetlen könnyűsége #2cpp17Elfogadva 100/1001.157s78916 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int m, q;
const int maxn=1e7+1;
int f[maxn];
int dp[maxn];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

	cin>>m>>q;
    
    for (int i=0;i<m;i++){
        int a;
        cin>>a;
        for (int j=a-1;j<maxn;j+=a) f[j]=max(f[j], a-1);
        f[maxn-1]=max(f[maxn-1], (maxn-1)%a);
    }
    for (int i=maxn-2;i>0;i--) f[i]=max(f[i], f[i+1]-1);
    
    dp[0]=0;
    int pos=maxn;
    for (int i=1;i<maxn;i++){
        if (!f[i]) pos=min(pos,i);
        dp[i]=dp[i-f[i]]+1;
    }

    for (int i=0;i<q;i++){
        int n;
        cin>>n;
        if (n>=pos) {
            cout<<"0\n";
            continue;
        }
        cout<<dp[n]<<"\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva128ms78648 KiB
2Elfogadva287ms78900 KiB
subtask220/20
3Elfogadva268ms78644 KiB
4Elfogadva326ms78644 KiB
5Elfogadva298ms78708 KiB
6Elfogadva298ms78644 KiB
7Elfogadva388ms78644 KiB
8Elfogadva533ms78596 KiB
9Elfogadva994ms78628 KiB
10Elfogadva1.157s78644 KiB
subtask310/10
11Elfogadva326ms78900 KiB
12Elfogadva460ms78900 KiB
13Elfogadva414ms78644 KiB
14Elfogadva432ms78644 KiB
15Elfogadva372ms78644 KiB
16Elfogadva340ms78896 KiB
17Elfogadva272ms78644 KiB
subtask415/15
18Elfogadva165ms78644 KiB
19Elfogadva231ms78644 KiB
20Elfogadva194ms78644 KiB
21Elfogadva268ms78668 KiB
22Elfogadva305ms78480 KiB
23Elfogadva486ms78472 KiB
24Elfogadva500ms78644 KiB
25Elfogadva414ms78644 KiB
26Elfogadva354ms78644 KiB
27Elfogadva741ms78644 KiB
subtask555/55
28Elfogadva409ms78900 KiB
29Elfogadva195ms78644 KiB
30Elfogadva279ms78900 KiB
31Elfogadva207ms78908 KiB
32Elfogadva243ms78900 KiB
33Elfogadva298ms78916 KiB
34Elfogadva477ms78900 KiB
35Elfogadva463ms78900 KiB
36Elfogadva453ms78900 KiB
37Elfogadva247ms78900 KiB
38Elfogadva324ms78900 KiB
39Elfogadva215ms78804 KiB