oj.uz

답안 #1015926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015926 2024-07-07T05:34:59 Z caterpillow Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 1736 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

there is the obvious 1e14 dp where your transitions are trying out each mod
if ur number is below the largest prime, you can instantly kill all of the kids
you always want to choose the prime that leaves the largest remainder
the game only ends if your number is a multiple of all of the primes
the second last prime used will never be the largest prime

can consider multiples of each prime a "platform", and each operation is falling onto the next platform in one of the chutes
if the query is greater than the product of the primes, then u will always get blocked somewhere

if a number is the optimal choice, itll continue being the optimal choice up until the next multiple of itself



*/


int m, q; 
int dp[10005];
vt<int> primes;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> q;
    primes.resize(m);
    F0R (i, m) cin >> primes[i]; 
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    FOR (i, 1, 10005) {
        for (int p : primes) {
            dp[i] = min(dp[i], 1 + dp[i - (i % p)]);
        }
    }
    F0R (i, q) {
        int v; cin >> v;
        if (dp[v] > 1e6) cout << "oo\n";
        else cout << dp[v] << endl;
    }
}

Compilation message

brunhilda.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 21 ms 508 KB Output is correct
14 Correct 20 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 219 ms 600 KB Execution killed with signal 11
2 Execution timed out 1069 ms 1372 KB Time limit exceeded
3 Execution timed out 1043 ms 1112 KB Time limit exceeded
4 Runtime error 62 ms 596 KB Execution killed with signal 11
5 Runtime error 904 ms 1304 KB Execution killed with signal 11
6 Runtime error 24 ms 600 KB Execution killed with signal 11
7 Runtime error 212 ms 620 KB Execution killed with signal 11
8 Runtime error 22 ms 604 KB Execution killed with signal 11
9 Execution timed out 1088 ms 1116 KB Time limit exceeded
10 Execution timed out 1071 ms 1116 KB Time limit exceeded
11 Runtime error 759 ms 1172 KB Execution killed with signal 11
12 Runtime error 38 ms 592 KB Execution killed with signal 11
13 Runtime error 57 ms 592 KB Execution killed with signal 11
14 Runtime error 56 ms 592 KB Execution killed with signal 11
15 Runtime error 738 ms 1104 KB Execution killed with signal 11
16 Execution timed out 1026 ms 1368 KB Time limit exceeded
17 Runtime error 64 ms 524 KB Execution killed with signal 11
18 Execution timed out 1072 ms 1372 KB Time limit exceeded

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 892 ms 1436 KB Execution killed with signal 11
2 Runtime error 928 ms 1456 KB Execution killed with signal 11
3 Incorrect 915 ms 1488 KB Output isn't correct
4 Runtime error 63 ms 604 KB Execution killed with signal 11
5 Execution timed out 1035 ms 1628 KB Time limit exceeded
6 Runtime error 156 ms 744 KB Execution killed with signal 11
7 Execution timed out 1026 ms 1624 KB Time limit exceeded
8 Runtime error 940 ms 1432 KB Execution killed with signal 11
9 Runtime error 885 ms 1432 KB Execution killed with signal 11
10 Runtime error 105 ms 856 KB Execution killed with signal 11
11 Runtime error 80 ms 604 KB Execution killed with signal 11
12 Runtime error 112 ms 604 KB Execution killed with signal 11
13 Runtime error 549 ms 1212 KB Execution killed with signal 11
14 Runtime error 1 ms 604 KB Execution killed with signal 11
15 Runtime error 104 ms 620 KB Execution killed with signal 11
16 Runtime error 125 ms 600 KB Execution killed with signal 11
17 Runtime error 790 ms 1312 KB Execution killed with signal 11
18 Runtime error 896 ms 1364 KB Execution killed with signal 11
19 Runtime error 89 ms 604 KB Execution killed with signal 11
20 Runtime error 837 ms 1540 KB Execution killed with signal 11
21 Runtime error 3 ms 600 KB Execution killed with signal 11
22 Execution timed out 1089 ms 1628 KB Time limit exceeded
23 Runtime error 503 ms 1104 KB Execution killed with signal 11
24 Runtime error 22 ms 600 KB Execution killed with signal 11
25 Runtime error 59 ms 608 KB Execution killed with signal 11
26 Runtime error 64 ms 616 KB Execution killed with signal 11
27 Execution timed out 1090 ms 1624 KB Time limit exceeded
28 Runtime error 20 ms 520 KB Execution killed with signal 11
29 Execution timed out 1070 ms 1628 KB Time limit exceeded
30 Execution timed out 1048 ms 1372 KB Time limit exceeded
31 Runtime error 79 ms 620 KB Execution killed with signal 11
32 Runtime error 53 ms 604 KB Execution killed with signal 11
33 Runtime error 23 ms 504 KB Execution killed with signal 11
34 Execution timed out 1060 ms 1628 KB Time limit exceeded
35 Runtime error 42 ms 524 KB Execution killed with signal 11
36 Execution timed out 1054 ms 1628 KB Time limit exceeded
37 Execution timed out 1034 ms 1736 KB Time limit exceeded
38 Runtime error 142 ms 848 KB Execution killed with signal 11
39 Runtime error 44 ms 592 KB Execution killed with signal 11
40 Runtime error 166 ms 852 KB Execution killed with signal 11
41 Execution timed out 1081 ms 1628 KB Time limit exceeded
42 Runtime error 55 ms 856 KB Execution killed with signal 11