답안 #575663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575663	2022-06-11T07:32:54 Z	ktkerem	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	345 ms	86912 KB

brunhilda

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
/*#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 vll;
typedef unsigned __int128 uvll;
ll _i=0;
#define ffn(x) _i=x
#define llll std::pair<ll , ll>
#define stitr set<ll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e9 + 7; 
const ll ous = 1e7 + 1e6 + 7;
const ll dx[4] = {1 , 0 , 0 , -1} , dy[4] = {0,1,-1,0};
void solve(){
    ll n , q;std::cin >> n >> q;
    ll dp[ous];memset(dp , 0 , sizeof(dp));
    fora(i , n){
        ll x;std::cin >> x;
        for(ll j = x-1;ous > j;j+=x){
            dp[j] = std::max(dp[j] , x-1);
        }
    }
    for(ll i = ous - 2;i>=0;i--){
        dp[i] = std::max(dp[i] , dp[i + 1] - 1);
    }
    for(ll i = 1;ous - 2 > i ; i++){
        if(dp[i] > 0){
            dp[i] = dp[i - dp[i]] + 1;
        }
        else{
            dp[i] = limit;
        }
    }
    fora(i , q){
        ll x;std::cin >> x;
        if(dp[x] >= limit){
            std::cout << "oo" << "\n";
        }
        else{
            std::cout << dp[x] << "\n";
        }
    }
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0; 
}

Compilation message

brunhilda.cpp:12:1: warning: "/*" within comment [-Wcomment]
   12 | /**/
      |  
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:67:8: warning: unused variable 'o' [-Wunused-variable]
   67 |     ll o = 1;
      |        ^

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	86352 KB	Output is correct
2	Correct	112 ms	86416 KB	Output is correct
3	Correct	104 ms	86400 KB	Output is correct
4	Correct	82 ms	86396 KB	Output is correct
5	Correct	96 ms	86320 KB	Output is correct
6	Correct	92 ms	86332 KB	Output is correct
7	Correct	102 ms	86396 KB	Output is correct
8	Correct	107 ms	86448 KB	Output is correct
9	Correct	131 ms	86392 KB	Output is correct
10	Correct	148 ms	86528 KB	Output is correct
11	Correct	138 ms	86476 KB	Output is correct
12	Correct	76 ms	86296 KB	Output is correct
13	Correct	231 ms	86400 KB	Output is correct
14	Correct	247 ms	86336 KB	Output is correct
15	Correct	124 ms	86400 KB	Output is correct
16	Correct	109 ms	86300 KB	Output is correct
17	Correct	102 ms	86420 KB	Output is correct
18	Correct	77 ms	86348 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	86404 KB	Output is correct
2	Correct	110 ms	86400 KB	Output is correct
3	Correct	283 ms	86400 KB	Output is correct
4	Correct	121 ms	86356 KB	Output is correct
5	Correct	206 ms	86400 KB	Output is correct
6	Correct	109 ms	86348 KB	Output is correct
7	Correct	92 ms	86356 KB	Output is correct
8	Correct	116 ms	86364 KB	Output is correct
9	Correct	241 ms	86400 KB	Output is correct
10	Correct	282 ms	86400 KB	Output is correct
11	Correct	284 ms	86348 KB	Output is correct
12	Correct	156 ms	86416 KB	Output is correct
13	Correct	89 ms	86348 KB	Output is correct
14	Correct	117 ms	86396 KB	Output is correct
15	Correct	229 ms	86404 KB	Output is correct
16	Correct	112 ms	86400 KB	Output is correct
17	Correct	244 ms	86344 KB	Output is correct
18	Correct	250 ms	86356 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	255 ms	86376 KB	Output is correct
2	Correct	300 ms	86356 KB	Output is correct
3	Correct	332 ms	86484 KB	Output is correct
4	Correct	181 ms	86660 KB	Output is correct
5	Correct	152 ms	86544 KB	Output is correct
6	Correct	260 ms	86656 KB	Output is correct
7	Correct	207 ms	86512 KB	Output is correct
8	Correct	251 ms	86396 KB	Output is correct
9	Correct	247 ms	86480 KB	Output is correct
10	Correct	189 ms	86396 KB	Output is correct
11	Correct	153 ms	86348 KB	Output is correct
12	Correct	231 ms	86400 KB	Output is correct
13	Correct	289 ms	86736 KB	Output is correct
14	Correct	180 ms	86912 KB	Output is correct
15	Correct	236 ms	86384 KB	Output is correct
16	Correct	257 ms	86356 KB	Output is correct
17	Correct	228 ms	86404 KB	Output is correct
18	Correct	298 ms	86452 KB	Output is correct
19	Correct	108 ms	86400 KB	Output is correct
20	Correct	287 ms	86524 KB	Output is correct
21	Correct	203 ms	86912 KB	Output is correct
22	Correct	327 ms	86544 KB	Output is correct
23	Correct	134 ms	86556 KB	Output is correct
24	Correct	119 ms	86732 KB	Output is correct
25	Correct	207 ms	86656 KB	Output is correct
26	Correct	188 ms	86604 KB	Output is correct
27	Correct	345 ms	86476 KB	Output is correct
28	Correct	115 ms	86688 KB	Output is correct
29	Correct	284 ms	86536 KB	Output is correct
30	Correct	272 ms	86604 KB	Output is correct
31	Correct	139 ms	86528 KB	Output is correct
32	Correct	148 ms	86676 KB	Output is correct
33	Correct	102 ms	86656 KB	Output is correct
34	Correct	223 ms	86404 KB	Output is correct
35	Correct	118 ms	86684 KB	Output is correct
36	Correct	301 ms	86528 KB	Output is correct
37	Correct	145 ms	86604 KB	Output is correct
38	Correct	258 ms	86656 KB	Output is correct
39	Correct	128 ms	86660 KB	Output is correct
40	Correct	236 ms	86564 KB	Output is correct
41	Correct	208 ms	86400 KB	Output is correct
42	Correct	315 ms	86732 KB	Output is correct