Submission #486857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
486857	2021-11-13T03:17:15 Z	huyhoangdz123	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	77.4603 / 100	276 ms	81092 KB

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 20000007
#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];
    int mx = 1e7;
    for (int i = 1; i <= m; i ++)
        for (int j = a[i] - 1; j <= mx; j += a[i])
            best[j] = max(best[j], a[i] - 1);
    for (int i = mx - 1; i >= 0; i --)
        best[i] = max(best[i], best[i + 1] - 1);
    for (int x = 1; x <= mx; x ++) dp[x] = oo;
    dp[0] = 0;
    for (int x = 1; x <= mx; 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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	78532 KB	Output is correct
2	Correct	116 ms	78616 KB	Output is correct
3	Correct	101 ms	78532 KB	Output is correct
4	Correct	94 ms	78708 KB	Output is correct
5	Correct	102 ms	78588 KB	Output is correct
6	Correct	96 ms	78588 KB	Output is correct
7	Correct	102 ms	78532 KB	Output is correct
8	Correct	107 ms	78532 KB	Output is correct
9	Correct	121 ms	78524 KB	Output is correct
10	Correct	134 ms	78504 KB	Output is correct
11	Correct	128 ms	78500 KB	Output is correct
12	Correct	93 ms	78472 KB	Output is correct
13	Correct	207 ms	78532 KB	Output is correct
14	Correct	210 ms	78588 KB	Output is correct
15	Correct	119 ms	78500 KB	Output is correct
16	Correct	122 ms	78496 KB	Output is correct
17	Correct	113 ms	78704 KB	Output is correct
18	Correct	92 ms	78660 KB	Output is correct

Subtask #2

18.8888888889 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	78616 KB	Output is correct
2	Correct	123 ms	79544 KB	Output is correct
3	Correct	254 ms	79300 KB	Output is correct
4	Correct	121 ms	78528 KB	Output is correct
5	Correct	184 ms	79044 KB	Output is correct
6	Correct	112 ms	78500 KB	Output is correct
7	Correct	106 ms	78628 KB	Output is correct
8	Correct	121 ms	78496 KB	Output is correct
9	Correct	211 ms	79280 KB	Output is correct
10	Correct	251 ms	79300 KB	Output is correct
11	Incorrect	242 ms	78904 KB	Output isn't correct
12	Correct	153 ms	78532 KB	Output is correct
13	Correct	99 ms	78628 KB	Output is correct
14	Correct	127 ms	78528 KB	Output is correct
15	Correct	211 ms	78928 KB	Output is correct
16	Correct	115 ms	79548 KB	Output is correct
17	Correct	216 ms	78648 KB	Output is correct
18	Correct	217 ms	79684 KB	Output is correct

Subtask #3

38.5714285714 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	79616 KB	Output is correct
2	Correct	260 ms	79452 KB	Output is correct
3	Correct	272 ms	79812 KB	Output is correct
4	Incorrect	171 ms	79872 KB	Output isn't correct
5	Incorrect	137 ms	81092 KB	Output isn't correct
6	Correct	220 ms	79896 KB	Output is correct
7	Correct	193 ms	80384 KB	Output is correct
8	Correct	220 ms	79684 KB	Output is correct
9	Correct	218 ms	79756 KB	Output is correct
10	Correct	176 ms	78804 KB	Output is correct
11	Incorrect	162 ms	78916 KB	Output isn't correct
12	Correct	218 ms	79064 KB	Output is correct
13	Correct	251 ms	80232 KB	Output is correct
14	Correct	157 ms	80196 KB	Output is correct
15	Incorrect	208 ms	78964 KB	Output isn't correct
16	Correct	226 ms	79016 KB	Output is correct
17	Correct	202 ms	79232 KB	Output is correct
18	Correct	264 ms	79488 KB	Output is correct
19	Incorrect	104 ms	79044 KB	Output isn't correct
20	Correct	258 ms	79876 KB	Output is correct
21	Incorrect	175 ms	80324 KB	Output isn't correct
22	Correct	276 ms	81008 KB	Output is correct
23	Correct	138 ms	80208 KB	Output is correct
24	Correct	134 ms	79980 KB	Output is correct
25	Incorrect	200 ms	79980 KB	Output isn't correct
26	Incorrect	170 ms	79812 KB	Output isn't correct
27	Correct	275 ms	80308 KB	Output is correct
28	Incorrect	117 ms	80068 KB	Output isn't correct
29	Correct	255 ms	80964 KB	Output is correct
30	Correct	237 ms	80708 KB	Output is correct
31	Correct	134 ms	79864 KB	Output is correct
32	Incorrect	147 ms	79872 KB	Output isn't correct
33	Incorrect	113 ms	79868 KB	Output isn't correct
34	Correct	192 ms	80408 KB	Output is correct
35	Incorrect	124 ms	80088 KB	Output isn't correct
36	Correct	270 ms	80964 KB	Output is correct
37	Incorrect	141 ms	81036 KB	Output isn't correct
38	Correct	220 ms	79952 KB	Output is correct
39	Incorrect	129 ms	79968 KB	Output isn't correct
40	Correct	191 ms	79968 KB	Output is correct
41	Correct	171 ms	80412 KB	Output is correct
42	Incorrect	246 ms	80164 KB	Output isn't correct