oj.uz

Submission #486860

# Submission time Handle Problem Language Result Execution time Memory
486860 2021-11-13T03:25:50 Z huyhoangdz123 Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 240 ms 79612 KB 
    //ngqminh.cl2735
    /*
    🛸　　　 　🌎　°　　🌓　•　　.°•　　　🚀 ✯
    　　　★　*　　　　　°　　　　🛰 　°·　　                           🪐
    .　　　•　° ★　•  ☄
    ______________________________________________________
        myv    myv    myv    myv    myv
            BUH BUH LMAO
    */
    #include <bits/stdc++.h>
    #define PB push_back
    #define Random(lf, rt) (lf + rand() % (rt - lf + 1))
    #define pii pair <int,int>
    #define vi vector <int>
    #define vii vector <pii>
    #define mpa make_pair
    #define oo 1e9 + 1000009
    #define F first
    #define S second
    #define reset(x, i) memset(x,i,sizeof(x))
    #define sz(x) int(x.size())
    #define maxn 100005
    #define maxx 10000007
    #define MOD
    #define all(x) x.begin(), x.end()
    #define cosdo(x) cos((x)/180 * Pi)
    #define sindo(x) sin((x)/180 * Pi)
    #define tando(x) tan((x)/180 * Pi)
    #define cotdo(x) 1/tando(x)
    #define Task "BirthDay"
    using namespace std;
    const double Pi = acos(-1);
    typedef long long ll;
    typedef long double ld;
    int dp[maxx], a[maxn];
    int n[maxn], best[maxx];
    int m, q;
    int main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //    freopen(Task".inp", "r", stdin);
    //    freopen(Task".out", "w", stdout);
        cin >> m >> q;
        for (int i = 1; i <= m; i ++)
            cin >> a[i];
        for (int i = 1; i <= q; i ++)
            cin >> n[i];
        sort(a + 1, a + m + 1);
        for (int i = 1; i <= m; i ++)
            for (int j = a[i] - 1; j < maxx; j += a[i])
                best[j] = a[i] - 1;
        for (int i = maxx - 2; i >= 0; i --)
            best[i] = max(best[i], best[i + 1] - 1);
        fill(dp, dp + maxx, oo);
        dp[0] = 0;
        for (int x = 1; x < maxx; x ++)
            dp[x] = dp[x - best[x]] + 1;
        for (int i = 1; i <= q; i ++){
            if(dp[n[i]] > oo) cout << "oo\n";
            else cout << dp[n[i]] << "\n";
        }
    }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 78500 KB Output is correct
2 Correct 96 ms 78500 KB Output is correct
3 Correct 88 ms 78504 KB Output is correct
4 Correct 82 ms 78544 KB Output is correct
5 Correct 88 ms 78556 KB Output is correct
6 Correct 83 ms 78496 KB Output is correct
7 Correct 90 ms 78520 KB Output is correct
8 Correct 95 ms 78532 KB Output is correct
9 Correct 105 ms 78488 KB Output is correct
10 Correct 118 ms 78584 KB Output is correct
11 Correct 113 ms 78532 KB Output is correct
12 Correct 81 ms 78500 KB Output is correct
13 Correct 180 ms 78532 KB Output is correct
14 Correct 176 ms 78528 KB Output is correct
15 Correct 100 ms 78504 KB Output is correct
16 Correct 95 ms 78492 KB Output is correct
17 Correct 97 ms 78528 KB Output is correct
18 Correct 82 ms 78528 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 78556 KB Output is correct
2 Correct 104 ms 78916 KB Output is correct
3 Correct 218 ms 78768 KB Output is correct
4 Correct 107 ms 78612 KB Output is correct
5 Correct 156 ms 78788 KB Output is correct
6 Correct 95 ms 78496 KB Output is correct
7 Correct 92 ms 78540 KB Output is correct
8 Correct 107 ms 78496 KB Output is correct
9 Correct 179 ms 78772 KB Output is correct
10 Correct 211 ms 78788 KB Output is correct
11 Incorrect 213 ms 78648 KB Output isn't correct
12 Correct 132 ms 78532 KB Output is correct
13 Correct 85 ms 78516 KB Output is correct
14 Correct 107 ms 78536 KB Output is correct
15 Correct 176 ms 78640 KB Output is correct
16 Correct 105 ms 78916 KB Output is correct
17 Correct 183 ms 78516 KB Output is correct
18 Correct 180 ms 78880 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 78968 KB Output is correct
2 Correct 222 ms 78880 KB Output is correct
3 Correct 223 ms 79044 KB Output is correct
4 Incorrect 161 ms 79172 KB Output isn't correct
5 Incorrect 124 ms 79548 KB Output isn't correct
6 Correct 196 ms 79152 KB Output is correct
7 Correct 170 ms 79220 KB Output is correct
8 Correct 185 ms 78916 KB Output is correct
9 Correct 190 ms 78936 KB Output is correct
10 Correct 154 ms 78684 KB Output is correct
11 Incorrect 136 ms 78664 KB Output isn't correct
12 Correct 176 ms 78700 KB Output is correct
13 Correct 215 ms 79300 KB Output is correct
14 Correct 140 ms 79428 KB Output is correct
15 Incorrect 179 ms 78660 KB Output isn't correct
16 Correct 203 ms 78700 KB Output is correct
17 Correct 178 ms 78788 KB Output is correct
18 Correct 221 ms 78916 KB Output is correct
19 Incorrect 94 ms 78660 KB Output isn't correct
20 Correct 227 ms 79140 KB Output is correct
21 Incorrect 157 ms 79464 KB Output isn't correct
22 Correct 231 ms 79520 KB Output is correct
23 Correct 129 ms 79244 KB Output is correct
24 Correct 113 ms 79224 KB Output is correct
25 Correct 165 ms 79172 KB Output is correct
26 Incorrect 154 ms 79172 KB Output isn't correct
27 Correct 240 ms 79264 KB Output is correct
28 Incorrect 105 ms 79268 KB Output isn't correct
29 Correct 219 ms 79428 KB Output is correct
30 Correct 212 ms 79556 KB Output is correct
31 Correct 133 ms 79172 KB Output is correct
32 Incorrect 131 ms 79124 KB Output isn't correct
33 Incorrect 102 ms 79124 KB Output isn't correct
34 Correct 168 ms 79224 KB Output is correct
35 Incorrect 112 ms 79172 KB Output isn't correct
36 Correct 228 ms 79612 KB Output is correct
37 Incorrect 124 ms 79536 KB Output isn't correct
38 Correct 193 ms 79140 KB Output is correct
39 Incorrect 115 ms 79244 KB Output isn't correct
40 Correct 171 ms 79136 KB Output is correct
41 Correct 154 ms 79204 KB Output is correct
42 Correct 206 ms 79300 KB Output is correct