oj.uz

Submission #473008

# Submission time Handle Problem Language Result Execution time Memory
473008 2021-09-14T18:01:37 Z hidden1 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 948 ms 235816 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const int MAX_N = 1e5 + 10;
const int MAX_Q = 3e7 + 10;
int arr[MAX_N];
int dp[MAX_Q], best[MAX_Q];
int n, m;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> arr[i];
        for(int j = arr[i] - 1; j < MAX_Q; j += arr[i]) {
            chkmax(best[j], arr[i] - 1);
        }
    }
    for(int i = MAX_Q - 2; i >= 0; i --) {
        chkmax(best[i], best[i + 1] - 1);
    }
    fill_n(dp, MAX_Q - 1, mod);
    dp[0] = 0;
    for(int i = 1; i < MAX_Q; i ++) {
        dp[i] = dp[i - best[i]] + 1;
    }

    while(m --) {
        int x;
        cin >> x;
        if(dp[x] > mod) {
            cout << "oo" << endl;
        } else {
            cout << dp[x] << endl;
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 235132 KB Output is correct
2 Correct 371 ms 235132 KB Output is correct
3 Correct 321 ms 235256 KB Output is correct
4 Correct 345 ms 235080 KB Output is correct
5 Correct 336 ms 235132 KB Output is correct
6 Correct 302 ms 235188 KB Output is correct
7 Correct 318 ms 235112 KB Output is correct
8 Correct 341 ms 235120 KB Output is correct
9 Correct 390 ms 235204 KB Output is correct
10 Correct 440 ms 235080 KB Output is correct
11 Correct 421 ms 235228 KB Output is correct
12 Correct 284 ms 235132 KB Output is correct
13 Correct 704 ms 235108 KB Output is correct
14 Correct 717 ms 235236 KB Output is correct
15 Correct 388 ms 235100 KB Output is correct
16 Correct 372 ms 235260 KB Output is correct
17 Correct 363 ms 235216 KB Output is correct
18 Correct 296 ms 235096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 235096 KB Output is correct
2 Correct 359 ms 235380 KB Output is correct
3 Correct 853 ms 235588 KB Output is correct
4 Correct 399 ms 235180 KB Output is correct
5 Correct 605 ms 235280 KB Output is correct
6 Correct 359 ms 235076 KB Output is correct
7 Correct 326 ms 235180 KB Output is correct
8 Correct 394 ms 235332 KB Output is correct
9 Correct 710 ms 235460 KB Output is correct
10 Correct 855 ms 235372 KB Output is correct
11 Correct 838 ms 235360 KB Output is correct
12 Correct 497 ms 235120 KB Output is correct
13 Correct 312 ms 235196 KB Output is correct
14 Correct 393 ms 235148 KB Output is correct
15 Correct 703 ms 235260 KB Output is correct
16 Correct 365 ms 235508 KB Output is correct
17 Correct 734 ms 235180 KB Output is correct
18 Correct 700 ms 235488 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 235396 KB Output is correct
2 Correct 894 ms 235388 KB Output is correct
3 Correct 935 ms 235376 KB Output is correct
4 Correct 530 ms 235460 KB Output is correct
5 Correct 415 ms 235624 KB Output is correct
6 Correct 693 ms 235512 KB Output is correct
7 Correct 636 ms 235652 KB Output is correct
8 Correct 726 ms 235400 KB Output is correct
9 Correct 727 ms 235364 KB Output is correct
10 Correct 583 ms 235156 KB Output is correct
11 Correct 504 ms 235164 KB Output is correct
12 Correct 674 ms 235356 KB Output is correct
13 Correct 837 ms 235484 KB Output is correct
14 Correct 502 ms 235616 KB Output is correct
15 Correct 688 ms 235172 KB Output is correct
16 Correct 772 ms 235136 KB Output is correct
17 Correct 689 ms 235332 KB Output is correct
18 Correct 925 ms 235340 KB Output is correct
19 Correct 330 ms 235156 KB Output is correct
20 Correct 866 ms 235484 KB Output is correct
21 Correct 567 ms 235816 KB Output is correct
22 Correct 873 ms 235648 KB Output is correct
23 Correct 408 ms 235476 KB Output is correct
24 Correct 344 ms 235364 KB Output is correct
25 Correct 582 ms 235460 KB Output is correct
26 Correct 534 ms 235296 KB Output is correct
27 Correct 948 ms 235616 KB Output is correct
28 Correct 360 ms 235460 KB Output is correct
29 Correct 835 ms 235620 KB Output is correct
30 Correct 764 ms 235748 KB Output is correct
31 Correct 397 ms 235280 KB Output is correct
32 Correct 447 ms 235412 KB Output is correct
33 Correct 309 ms 235444 KB Output is correct
34 Correct 641 ms 235588 KB Output is correct
35 Correct 369 ms 235332 KB Output is correct
36 Correct 850 ms 235584 KB Output is correct
37 Correct 411 ms 235612 KB Output is correct
38 Correct 719 ms 235360 KB Output is correct
39 Correct 374 ms 235360 KB Output is correct
40 Correct 619 ms 235448 KB Output is correct
41 Correct 570 ms 235716 KB Output is correct
42 Correct 793 ms 235604 KB Output is correct