Submission #486710

#	Time	Username	Problem	Language	Result	Execution time	Memory
486710		huyhoangdz123	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	23.65 / 100	1101 ms	41680 KiB

brunhilda

//ngqminh.cl2735
/*
🛸　　　 　🌎　°　　🌓　•　　.°•　　　🚀 ✯
　　　★　*　　　　　°　　　　🛰 　°·　　                           🪐
.　　　•　° ★　•  ☄
______________________________________________________
    myv    myv    myv    myv    myv
        BUH BUH LMAO
*/
#include <bits/stdc++.h>
#define PB push_back
#define Random(lf, rt) (lf + rand() % (rt - lf + 1))
#define pii pair <int,int>
#define vi vector <int>
#define vii vector <pii>
#define mpa make_pair
#define oo 1e9 + 5
#define F first
#define S second
#define reset(x, i) memset(x,i,sizeof(x))
#define sz(x) int(x.size())
#define maxn 100005
#define maxx 10000007
#define MOD
#define all(x) x.begin(), x.end()
#define cosdo(x) cos((x)/180 * Pi)
#define sindo(x) sin((x)/180 * Pi)
#define tando(x) tan((x)/180 * Pi)
#define cotdo(x) 1/tando(x)
#define Task "BirthDay"
using namespace std;
const double Pi = acos(-1);
typedef long long ll;
typedef long double ld;
int dp[maxx], a[maxn];
int n[maxn];
int m, q;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
//    freopen(Task".inp", "r", stdin);
//    freopen(Task".out", "w", stdout);
    cin >> m >> q;
    for (int i = 1; i <= m; i ++)
        cin >> a[i];
    for (int i = 1; i <= q; i ++)
        cin >> n[i];
    sort(a + 1, a + m + 1);
    int mx = *max_element(n + 1, n + q + 1);
    for (int x = 1; x <= mx; x ++) dp[x] = oo;
    dp[0] = 0;
    for (int x = 1; x < a[m]; x ++) dp[x] = 1;
    for (int x = a[m]; x <= mx; x ++)
    {
        for (int i = 1; i <= m; i ++) if(x % a[i])
            dp[x] = min(dp[x], dp[x - x % a[i]] + 1);
    }
    for (int i = 1; i <= q; i ++){
        if(dp[n[i]] >= oo) cout << "oo\n";
        else cout << dp[n[i]] << "\n";
    }

}

• Subtask 1: 20 / 20
• Subtask 2: 2.2222222222222223 / 20
• Subtask 3: 1.4285714285714286 / 60