Submission #155727

#TimeUsernameProblemLanguageResultExecution timeMemory
155727Flying_dragon_02Brunhilda’s Birthday (BOI13_brunhilda)C++14
0 / 100
426 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; const int mod = 1e9 + 7; const int inf = 1e9; int add(int x, int y) { return (1ll * x + 1ll * y) % mod; } int del(int x, int y) { return ((1ll * x - 1ll * y) % mod + mod) % mod; } int mul(int x, int y) { return (1ll * x * 1ll * y) % mod; } const int N = 1e7 + 5; int dp[N]; bool used[N]; vector<int> vec[N]; int bit[2 * N]; void update(int x, int val) { while(x > 0) { bit[x] = min(bit[x], val); x -= x & (-x); } } int get(int x) { if(x == 0) return 0; int val = inf; while(x < N) { val = min(val, bit[x]); x += x & (-x); } return val; } int m, q; int main() { cin.tie(0), ios_base::sync_with_stdio(0); cin >> m >> q; for(int i = 1; i <= m; i++) { int x; cin >> x; if(used[x]) continue; used[x] = 1; for(int l = 0; l < N; l++) { if(x * l >= N) break; vec[x * l].pb(x); } } for(int i = 1; i <= N - 5; i++) bit[i] = dp[i] = inf; for(int i = 0; i <= N - 5; i++) { dp[i] = get(i); for(int j = 0; j < vec[i].size(); j++) update(i + vec[i][j] - 1, min(inf, dp[i] + 1)); } for(int i = 1; i <= q; i++) { int x; cin >> x; if(dp[x] == inf) cout << "oo\n"; else cout << dp[x] << "\n"; } }

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < vec[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...