Submission #1015926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015926		caterpillow	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	1090 ms	1736 KiB

brunhilda

#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 (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60