oj.uz

Submission #473007

# Submission time Handle Problem Language Result Execution time Memory
473007 2021-09-14T18:00:43 Z hidden1 Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 328 ms 79936 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 = 1e7 + 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 103 ms 78496 KB Output is correct
2 Correct 122 ms 78508 KB Output is correct
3 Correct 115 ms 78488 KB Output is correct
4 Correct 99 ms 78644 KB Output is correct
5 Correct 114 ms 78476 KB Output is correct
6 Correct 102 ms 78580 KB Output is correct
7 Correct 116 ms 78464 KB Output is correct
8 Correct 119 ms 78484 KB Output is correct
9 Correct 138 ms 78472 KB Output is correct
10 Correct 150 ms 78612 KB Output is correct
11 Correct 149 ms 78488 KB Output is correct
12 Correct 96 ms 78484 KB Output is correct
13 Correct 233 ms 78492 KB Output is correct
14 Correct 236 ms 78536 KB Output is correct
15 Correct 131 ms 78488 KB Output is correct
16 Correct 124 ms 78500 KB Output is correct
17 Correct 123 ms 78660 KB Output is correct
18 Correct 97 ms 78528 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 78632 KB Output is correct
2 Correct 133 ms 78968 KB Output is correct
3 Correct 292 ms 78916 KB Output is correct
4 Correct 131 ms 78612 KB Output is correct
5 Correct 229 ms 78852 KB Output is correct
6 Correct 121 ms 78500 KB Output is correct
7 Correct 113 ms 78712 KB Output is correct
8 Correct 132 ms 78496 KB Output is correct
9 Correct 258 ms 78980 KB Output is correct
10 Correct 285 ms 78912 KB Output is correct
11 Incorrect 300 ms 78788 KB Output isn't correct
12 Correct 165 ms 78496 KB Output is correct
13 Correct 104 ms 78500 KB Output is correct
14 Correct 149 ms 78512 KB Output is correct
15 Correct 235 ms 78788 KB Output is correct
16 Correct 130 ms 78964 KB Output is correct
17 Correct 262 ms 78548 KB Output is correct
18 Correct 240 ms 78996 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 78892 KB Output is correct
2 Correct 303 ms 78856 KB Output is correct
3 Correct 303 ms 79032 KB Output is correct
4 Incorrect 199 ms 79092 KB Output isn't correct
5 Incorrect 163 ms 79216 KB Output isn't correct
6 Correct 253 ms 79020 KB Output is correct
7 Correct 235 ms 79112 KB Output is correct
8 Correct 243 ms 79008 KB Output is correct
9 Correct 243 ms 78944 KB Output is correct
10 Correct 198 ms 78664 KB Output is correct
11 Incorrect 171 ms 78780 KB Output isn't correct
12 Correct 229 ms 78792 KB Output is correct
13 Correct 289 ms 79052 KB Output is correct
14 Correct 181 ms 79780 KB Output is correct
15 Incorrect 244 ms 78704 KB Output isn't correct
16 Correct 261 ms 78776 KB Output is correct
17 Correct 245 ms 78876 KB Output is correct
18 Correct 300 ms 78896 KB Output is correct
19 Incorrect 114 ms 78660 KB Output isn't correct
20 Correct 302 ms 79008 KB Output is correct
21 Incorrect 204 ms 79936 KB Output isn't correct
22 Correct 325 ms 79316 KB Output is correct
23 Correct 165 ms 79020 KB Output is correct
24 Correct 140 ms 78880 KB Output is correct
25 Correct 218 ms 79300 KB Output is correct
26 Incorrect 206 ms 78952 KB Output isn't correct
27 Correct 328 ms 79128 KB Output is correct
28 Incorrect 137 ms 79292 KB Output isn't correct
29 Correct 308 ms 79224 KB Output is correct
30 Correct 279 ms 79204 KB Output is correct
31 Correct 152 ms 78928 KB Output is correct
32 Incorrect 175 ms 78880 KB Output isn't correct
33 Incorrect 123 ms 78872 KB Output isn't correct
34 Correct 234 ms 79140 KB Output is correct
35 Incorrect 144 ms 79472 KB Output isn't correct
36 Correct 308 ms 79132 KB Output is correct
37 Incorrect 158 ms 79172 KB Output isn't correct
38 Correct 259 ms 79000 KB Output is correct
39 Incorrect 148 ms 78992 KB Output isn't correct
40 Correct 221 ms 78952 KB Output is correct
41 Correct 202 ms 79200 KB Output is correct
42 Correct 271 ms 79704 KB Output is correct