답안 #856574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856574 2023-10-04T02:07:34 Z ngjabach Brunhilda’s Birthday (BOI13_brunhilda) C++14
77.4603 / 100
175 ms 41300 KB
// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=10000000,M=1000000000;
const ll INF=1e18+7;
int dp[N+50];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//    freopen(".inp","r",stdin);
//    freopen(".out","w",stdout);
    int n,q,a;
    cin>>n>>q;
    mset(dp);
    while(n--){
        cin>>a;
        for(int i=a-1;i<=N;i+=a) dp[i]=max(dp[i],a-1);
    }
    for(int i=N;i>0;--i) dp[i]=max(dp[i],dp[i+1]-1);
    for(int i=1;i<=N;++i){
        if(dp[i]>0) dp[i]=dp[i-dp[i]]+1;
        else dp[i]=M;
    }
    while(q--){
        cin>>a;
        if(dp[a]>=M) cout<<"oo";
        else cout<<dp[a];
        cout<<endl;
    }
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 39512 KB Output is correct
2 Correct 64 ms 39600 KB Output is correct
3 Correct 59 ms 39512 KB Output is correct
4 Correct 52 ms 39516 KB Output is correct
5 Correct 58 ms 39516 KB Output is correct
6 Correct 55 ms 39512 KB Output is correct
7 Correct 60 ms 39768 KB Output is correct
8 Correct 65 ms 39516 KB Output is correct
9 Correct 70 ms 39576 KB Output is correct
10 Correct 87 ms 39512 KB Output is correct
11 Correct 74 ms 39516 KB Output is correct
12 Correct 51 ms 39588 KB Output is correct
13 Correct 122 ms 39584 KB Output is correct
14 Correct 140 ms 39512 KB Output is correct
15 Correct 69 ms 39576 KB Output is correct
16 Correct 66 ms 39512 KB Output is correct
17 Correct 64 ms 39592 KB Output is correct
18 Correct 54 ms 39592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 39512 KB Output is correct
2 Correct 73 ms 40272 KB Output is correct
3 Correct 158 ms 39852 KB Output is correct
4 Correct 70 ms 39512 KB Output is correct
5 Correct 108 ms 39936 KB Output is correct
6 Correct 62 ms 39516 KB Output is correct
7 Correct 62 ms 39676 KB Output is correct
8 Correct 71 ms 39516 KB Output is correct
9 Correct 127 ms 40100 KB Output is correct
10 Correct 151 ms 40020 KB Output is correct
11 Incorrect 154 ms 39588 KB Output isn't correct
12 Correct 85 ms 39516 KB Output is correct
13 Correct 55 ms 39516 KB Output is correct
14 Correct 68 ms 39512 KB Output is correct
15 Correct 128 ms 39764 KB Output is correct
16 Correct 72 ms 40280 KB Output is correct
17 Correct 117 ms 39516 KB Output is correct
18 Correct 132 ms 40276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 40272 KB Output is correct
2 Correct 148 ms 40100 KB Output is correct
3 Correct 157 ms 40272 KB Output is correct
4 Incorrect 102 ms 40528 KB Output isn't correct
5 Incorrect 87 ms 41228 KB Output isn't correct
6 Correct 131 ms 40528 KB Output is correct
7 Correct 120 ms 40612 KB Output is correct
8 Correct 130 ms 40276 KB Output is correct
9 Correct 133 ms 40276 KB Output is correct
10 Correct 100 ms 39516 KB Output is correct
11 Incorrect 89 ms 39764 KB Output isn't correct
12 Correct 122 ms 39848 KB Output is correct
13 Correct 146 ms 40528 KB Output is correct
14 Correct 113 ms 40784 KB Output is correct
15 Incorrect 123 ms 39760 KB Output isn't correct
16 Correct 134 ms 39764 KB Output is correct
17 Correct 127 ms 39988 KB Output is correct
18 Correct 148 ms 40116 KB Output is correct
19 Incorrect 63 ms 39684 KB Output isn't correct
20 Correct 160 ms 40324 KB Output is correct
21 Incorrect 113 ms 41092 KB Output isn't correct
22 Correct 161 ms 41040 KB Output is correct
23 Correct 88 ms 40724 KB Output is correct
24 Correct 75 ms 40360 KB Output is correct
25 Incorrect 111 ms 40628 KB Output isn't correct
26 Incorrect 109 ms 40452 KB Output isn't correct
27 Correct 175 ms 40712 KB Output is correct
28 Incorrect 72 ms 40528 KB Output isn't correct
29 Correct 157 ms 41136 KB Output is correct
30 Correct 135 ms 41040 KB Output is correct
31 Correct 83 ms 40380 KB Output is correct
32 Incorrect 91 ms 40580 KB Output isn't correct
33 Incorrect 70 ms 40464 KB Output isn't correct
34 Correct 122 ms 40712 KB Output is correct
35 Incorrect 75 ms 40520 KB Output isn't correct
36 Correct 175 ms 41040 KB Output is correct
37 Incorrect 90 ms 41300 KB Output isn't correct
38 Correct 154 ms 40612 KB Output is correct
39 Incorrect 82 ms 40524 KB Output isn't correct
40 Correct 117 ms 40584 KB Output is correct
41 Correct 111 ms 40792 KB Output is correct
42 Incorrect 136 ms 40612 KB Output isn't correct