oj.uz

Submission #621415

# Submission time Handle Problem Language Result Execution time Memory
621415 2022-08-03T18:43:00 Z 353cerega Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 387 ms 119812 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;


const int mx = 10000000;
int dp[mx+1];
int nxt[mx+1];
int g[mx+1];

void solve()
{
    ll m, q;
    cin >> m >> q;
    vector<int> p(m);
    for (ll i=0;i<m;i++) cin >> p[i];
    int mn = mx;
    for (ll i=0;i<m;i++) mn = min(mn,mx/p[i]*p[i]);
    for (int i=0;i<=mx;i++) g[i] = dp[i] = mx;
    for (int i=0;i<m;i++)
    {
        for (int j=p[i];j<=mx;j+=p[i])
        {
            g[j] = min(g[j],j-p[i]);
        }
    }
    for (int i=mx;i>=0;i--)
    {
        nxt[i] = mn;
        mn = min(mn,g[i]);
    }
    dp[0] = 0;
    for (int i=1;i<=mx;i++)
    {
        if (nxt[i]==i) break;
        dp[i] = dp[nxt[i]]+1;
    }
    while (q--)
    {
        ll N;
        cin >> N;
        if (dp[N]<mx) cout << dp[N] << "\n";
        else cout << "oo\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 117628 KB Output is correct
2 Correct 93 ms 117696 KB Output is correct
3 Correct 72 ms 117632 KB Output is correct
4 Correct 92 ms 117764 KB Output is correct
5 Correct 89 ms 117692 KB Output is correct
6 Correct 67 ms 117700 KB Output is correct
7 Correct 91 ms 117708 KB Output is correct
8 Correct 87 ms 117628 KB Output is correct
9 Correct 121 ms 117644 KB Output is correct
10 Correct 120 ms 117644 KB Output is correct
11 Correct 123 ms 117632 KB Output is correct
12 Correct 72 ms 117652 KB Output is correct
13 Correct 226 ms 117644 KB Output is correct
14 Correct 210 ms 117740 KB Output is correct
15 Correct 102 ms 117624 KB Output is correct
16 Correct 94 ms 117632 KB Output is correct
17 Correct 104 ms 117736 KB Output is correct
18 Correct 105 ms 117788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 117760 KB Output is correct
2 Correct 97 ms 118684 KB Output is correct
3 Correct 267 ms 118384 KB Output is correct
4 Correct 102 ms 117756 KB Output is correct
5 Correct 184 ms 118196 KB Output is correct
6 Correct 97 ms 117724 KB Output is correct
7 Correct 85 ms 117792 KB Output is correct
8 Correct 114 ms 117772 KB Output is correct
9 Correct 238 ms 118416 KB Output is correct
10 Correct 268 ms 118388 KB Output is correct
11 Correct 238 ms 118064 KB Output is correct
12 Correct 138 ms 117744 KB Output is correct
13 Correct 89 ms 117692 KB Output is correct
14 Correct 104 ms 117652 KB Output is correct
15 Correct 192 ms 118056 KB Output is correct
16 Correct 109 ms 118768 KB Output is correct
17 Correct 211 ms 117752 KB Output is correct
18 Correct 190 ms 118888 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 118652 KB Output is correct
2 Correct 289 ms 118428 KB Output is correct
3 Correct 360 ms 118840 KB Output is correct
4 Correct 253 ms 118664 KB Output is correct
5 Correct 270 ms 119760 KB Output is correct
6 Correct 387 ms 118740 KB Output is correct
7 Correct 260 ms 119412 KB Output is correct
8 Correct 292 ms 118568 KB Output is correct
9 Correct 273 ms 118640 KB Output is correct
10 Correct 191 ms 117868 KB Output is correct
11 Correct 175 ms 117940 KB Output is correct
12 Correct 256 ms 117968 KB Output is correct
13 Correct 353 ms 118996 KB Output is correct
14 Correct 293 ms 118948 KB Output is correct
15 Correct 248 ms 118036 KB Output is correct
16 Correct 288 ms 117940 KB Output is correct
17 Correct 247 ms 118300 KB Output is correct
18 Correct 310 ms 118492 KB Output is correct
19 Correct 146 ms 117996 KB Output is correct
20 Correct 300 ms 118936 KB Output is correct
21 Correct 302 ms 119056 KB Output is correct
22 Correct 362 ms 119812 KB Output is correct
23 Correct 267 ms 119088 KB Output is correct
24 Correct 218 ms 118700 KB Output is correct
25 Correct 280 ms 118744 KB Output is correct
26 Correct 251 ms 118672 KB Output is correct
27 Correct 339 ms 119268 KB Output is correct
28 Correct 213 ms 118732 KB Output is correct
29 Correct 362 ms 119808 KB Output is correct
30 Correct 345 ms 119440 KB Output is correct
31 Correct 230 ms 118636 KB Output is correct
32 Correct 238 ms 118660 KB Output is correct
33 Correct 192 ms 118660 KB Output is correct
34 Correct 236 ms 119292 KB Output is correct
35 Correct 241 ms 118800 KB Output is correct
36 Correct 365 ms 119672 KB Output is correct
37 Correct 247 ms 119808 KB Output is correct
38 Correct 301 ms 118660 KB Output is correct
39 Correct 219 ms 118732 KB Output is correct
40 Correct 271 ms 118768 KB Output is correct
41 Correct 223 ms 119316 KB Output is correct
42 Correct 364 ms 118960 KB Output is correct