oj.uz

Submission #486858

# Submission time Handle Problem Language Result Execution time Memory
486858 2021-11-13T03:21:41 Z huyhoangdz123 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 604 ms 157872 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 20000007
#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];
    for (int i = 1; i <= m; i ++)
        for (int j = a[i] - 1; j < maxx; j += a[i])
            best[j] = max(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 181 ms 156864 KB Output is correct
2 Correct 253 ms 156828 KB Output is correct
3 Correct 202 ms 156788 KB Output is correct
4 Correct 184 ms 156836 KB Output is correct
5 Correct 195 ms 156740 KB Output is correct
6 Correct 177 ms 156836 KB Output is correct
7 Correct 201 ms 156744 KB Output is correct
8 Correct 203 ms 156860 KB Output is correct
9 Correct 231 ms 156740 KB Output is correct
10 Correct 263 ms 156764 KB Output is correct
11 Correct 244 ms 156840 KB Output is correct
12 Correct 187 ms 156888 KB Output is correct
13 Correct 412 ms 156800 KB Output is correct
14 Correct 425 ms 156844 KB Output is correct
15 Correct 232 ms 156788 KB Output is correct
16 Correct 219 ms 156792 KB Output is correct
17 Correct 221 ms 156916 KB Output is correct
18 Correct 182 ms 156916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 156908 KB Output is correct
2 Correct 219 ms 157216 KB Output is correct
3 Correct 505 ms 157168 KB Output is correct
4 Correct 247 ms 156804 KB Output is correct
5 Correct 390 ms 156996 KB Output is correct
6 Correct 210 ms 156800 KB Output is correct
7 Correct 217 ms 156844 KB Output is correct
8 Correct 240 ms 156800 KB Output is correct
9 Correct 460 ms 157044 KB Output is correct
10 Correct 506 ms 157064 KB Output is correct
11 Correct 524 ms 157064 KB Output is correct
12 Correct 310 ms 156756 KB Output is correct
13 Correct 184 ms 156820 KB Output is correct
14 Correct 261 ms 157124 KB Output is correct
15 Correct 408 ms 156992 KB Output is correct
16 Correct 229 ms 157148 KB Output is correct
17 Correct 439 ms 156832 KB Output is correct
18 Correct 429 ms 157252 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 157280 KB Output is correct
2 Correct 544 ms 157168 KB Output is correct
3 Correct 509 ms 157388 KB Output is correct
4 Correct 339 ms 157380 KB Output is correct
5 Correct 246 ms 157788 KB Output is correct
6 Correct 429 ms 157444 KB Output is correct
7 Correct 391 ms 157548 KB Output is correct
8 Correct 445 ms 157272 KB Output is correct
9 Correct 414 ms 157284 KB Output is correct
10 Correct 359 ms 156888 KB Output is correct
11 Correct 309 ms 157028 KB Output is correct
12 Correct 416 ms 156996 KB Output is correct
13 Correct 497 ms 157596 KB Output is correct
14 Correct 298 ms 157772 KB Output is correct
15 Correct 406 ms 157028 KB Output is correct
16 Correct 476 ms 156924 KB Output is correct
17 Correct 404 ms 157000 KB Output is correct
18 Correct 515 ms 157252 KB Output is correct
19 Correct 201 ms 157000 KB Output is correct
20 Correct 525 ms 157332 KB Output is correct
21 Correct 348 ms 157804 KB Output is correct
22 Correct 526 ms 157824 KB Output is correct
23 Correct 254 ms 157504 KB Output is correct
24 Correct 211 ms 157392 KB Output is correct
25 Correct 358 ms 157540 KB Output is correct
26 Correct 349 ms 157460 KB Output is correct
27 Correct 604 ms 157448 KB Output is correct
28 Correct 225 ms 157432 KB Output is correct
29 Correct 488 ms 157772 KB Output is correct
30 Correct 472 ms 157708 KB Output is correct
31 Correct 262 ms 157380 KB Output is correct
32 Correct 263 ms 157508 KB Output is correct
33 Correct 196 ms 157396 KB Output is correct
34 Correct 379 ms 157568 KB Output is correct
35 Correct 241 ms 157508 KB Output is correct
36 Correct 500 ms 157744 KB Output is correct
37 Correct 247 ms 157872 KB Output is correct
38 Correct 426 ms 157436 KB Output is correct
39 Correct 232 ms 157556 KB Output is correct
40 Correct 365 ms 157448 KB Output is correct
41 Correct 337 ms 157524 KB Output is correct
42 Correct 490 ms 157592 KB Output is correct