oj.uz

Submission #310806

# Submission time Handle Problem Language Result Execution time Memory
310806 2020-10-08T03:41:43 Z VROOM_VARUN Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 606 ms 119160 KB 
/*
ID: varunra2
LANG: C++
TASK: birthday
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

const int N = (int)(1.5e7);
// int dp[N];
// int best[N];
VI dp(N, INF);
VI best(N, 0);

int main() {
  // #ifndef ONLINE_JUDGE
  // freopen("birthday.in", "r", stdin);
  // freopen("birthday.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  int m, q;
  cin >> m >> q;

  dp[0] = 0;

  while (m--) {
    int p;
    cin >> p;

    for (int j = p - 1; j < N; j += p) {
      best[j] = max(best[j], p - 1);
    }
  }

  for (int i = N - 1; i > 0; i--) {
    best[i - 1] = max(best[i - 1], best[i] - 1);
  }

  for (int i = 1; i < N; i++) {
    dp[i] = dp[i - best[i]] + 1;
  }

  while (q--) {
    int n;
    cin >> n;
    if (dp[n] >= N) {
      cout << "oo\n";
    } else
      cout << dp[n] << '\n';
  }

  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 117752 KB Output is correct
2 Correct 216 ms 117752 KB Output is correct
3 Correct 172 ms 117752 KB Output is correct
4 Correct 141 ms 117752 KB Output is correct
5 Correct 166 ms 117812 KB Output is correct
6 Correct 143 ms 117752 KB Output is correct
7 Correct 178 ms 117752 KB Output is correct
8 Correct 200 ms 117912 KB Output is correct
9 Correct 229 ms 117752 KB Output is correct
10 Correct 256 ms 117880 KB Output is correct
11 Correct 230 ms 117880 KB Output is correct
12 Correct 137 ms 117752 KB Output is correct
13 Correct 427 ms 117800 KB Output is correct
14 Correct 435 ms 117752 KB Output is correct
15 Correct 221 ms 117880 KB Output is correct
16 Correct 216 ms 117752 KB Output is correct
17 Correct 194 ms 117880 KB Output is correct
18 Correct 141 ms 117752 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 117856 KB Output is correct
2 Correct 196 ms 117752 KB Output is correct
3 Correct 541 ms 117880 KB Output is correct
4 Correct 219 ms 117752 KB Output is correct
5 Correct 363 ms 117752 KB Output is correct
6 Correct 199 ms 117752 KB Output is correct
7 Correct 169 ms 117880 KB Output is correct
8 Correct 207 ms 117752 KB Output is correct
9 Correct 427 ms 117880 KB Output is correct
10 Correct 535 ms 117880 KB Output is correct
11 Correct 529 ms 117752 KB Output is correct
12 Correct 287 ms 117752 KB Output is correct
13 Correct 154 ms 117880 KB Output is correct
14 Correct 212 ms 117752 KB Output is correct
15 Correct 435 ms 117752 KB Output is correct
16 Correct 192 ms 117752 KB Output is correct
17 Correct 451 ms 117716 KB Output is correct
18 Correct 425 ms 117880 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 117944 KB Output is correct
2 Correct 552 ms 117880 KB Output is correct
3 Correct 563 ms 118136 KB Output is correct
4 Correct 316 ms 118648 KB Output is correct
5 Correct 231 ms 118648 KB Output is correct
6 Correct 442 ms 118520 KB Output is correct
7 Correct 376 ms 118264 KB Output is correct
8 Correct 447 ms 118008 KB Output is correct
9 Correct 448 ms 118008 KB Output is correct
10 Correct 337 ms 117752 KB Output is correct
11 Correct 282 ms 118008 KB Output is correct
12 Correct 405 ms 117880 KB Output is correct
13 Correct 507 ms 118652 KB Output is correct
14 Correct 300 ms 119160 KB Output is correct
15 Correct 424 ms 118008 KB Output is correct
16 Correct 483 ms 117960 KB Output is correct
17 Correct 413 ms 117752 KB Output is correct
18 Correct 553 ms 117880 KB Output is correct
19 Correct 186 ms 117880 KB Output is correct
20 Correct 547 ms 118136 KB Output is correct
21 Correct 353 ms 119160 KB Output is correct
22 Correct 565 ms 118648 KB Output is correct
23 Correct 237 ms 118648 KB Output is correct
24 Correct 189 ms 118780 KB Output is correct
25 Correct 364 ms 118776 KB Output is correct
26 Correct 317 ms 118648 KB Output is correct
27 Correct 606 ms 118136 KB Output is correct
28 Correct 192 ms 118904 KB Output is correct
29 Correct 500 ms 118648 KB Output is correct
30 Correct 463 ms 118648 KB Output is correct
31 Correct 223 ms 118520 KB Output is correct
32 Correct 256 ms 118648 KB Output is correct
33 Correct 168 ms 118776 KB Output is correct
34 Correct 371 ms 118136 KB Output is correct
35 Correct 210 ms 118776 KB Output is correct
36 Correct 549 ms 118520 KB Output is correct
37 Correct 233 ms 118584 KB Output is correct
38 Correct 443 ms 118648 KB Output is correct
39 Correct 208 ms 118904 KB Output is correct
40 Correct 379 ms 118588 KB Output is correct
41 Correct 339 ms 118264 KB Output is correct
42 Correct 498 ms 118904 KB Output is correct