oj.uz

답안 #310804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310804 2020-10-08T03:39:23 Z VROOM_VARUN Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 85 ms 25208 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.5e6);
// 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] = max(best[i], 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Incorrect 17 ms 12032 KB Output isn't correct
3 Incorrect 14 ms 12160 KB Output isn't correct
4 Incorrect 11 ms 12220 KB Output isn't correct
5 Incorrect 12 ms 12032 KB Output isn't correct
6 Incorrect 11 ms 12148 KB Output isn't correct
7 Incorrect 14 ms 12032 KB Output isn't correct
8 Incorrect 18 ms 12032 KB Output isn't correct
9 Incorrect 19 ms 12032 KB Output isn't correct
10 Incorrect 20 ms 12032 KB Output isn't correct
11 Incorrect 18 ms 12032 KB Output isn't correct
12 Incorrect 10 ms 12032 KB Output isn't correct
13 Incorrect 33 ms 12152 KB Output isn't correct
14 Incorrect 32 ms 12160 KB Output isn't correct
15 Incorrect 18 ms 12032 KB Output isn't correct
16 Incorrect 18 ms 12032 KB Output isn't correct
17 Incorrect 15 ms 12160 KB Output isn't correct
18 Incorrect 12 ms 12160 KB Output isn't correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 37 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 62 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 30 ms 24268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 43 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 31 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 33 ms 24448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 34 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 50 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 64 ms 24824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 57 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 37 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 34 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 32 ms 24360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 50 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 43 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 49 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 53 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 60 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 85 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 41 ms 24344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 39 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 49 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 49 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 52 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 51 ms 24792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 42 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 36 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 44 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 54 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 39 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 46 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 51 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 50 ms 24824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 58 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 31 ms 24388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 57 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 40 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 58 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 34 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 27 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 42 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 37 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 64 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 28 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 54 ms 25208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 50 ms 24828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 30 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 32 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 27 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 49 ms 25084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 33 ms 24576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 55 ms 25180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 41 ms 25180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 48 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 29 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 44 ms 24456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 49 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 49 ms 24444 KB Execution killed with signal 11 (could be triggered by violating memory limits)