제출 #486859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486859		huyhoangdz123	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	80.32 / 100	280 ms	79556 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 + 1000009
#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], best[maxx];
int m, q;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    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];
    for (int i = 1; i <= m; i ++)
        for (int j = a[i] - 1; j < maxx; j += a[i])
            best[j] = max(best[j], a[i] - 1);
    for (int i = maxx - 2; i >= 0; i --)
        best[i] = max(best[i], best[i + 1] - 1);
    fill(dp, dp + maxx, oo);
    dp[0] = 0;
    for (int x = 1; x < maxx; x ++)
        dp[x] = dp[x - best[x]] + 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: 18.88888888888889 / 20
• Subtask 3: 41.42857142857143 / 60