Submission #155745

#TimeUsernameProblemLanguageResultExecution timeMemory
155745Flying_dragon_02Brunhilda’s Birthday (BOI13_brunhilda)C++14
0 / 100
1095 ms149208 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], p[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 < 2 * N) { val = min(val, bit[x]); x += x & (-x); } return val; } int m, q; int main() { scanf("%d%d", &m, &q); for(int i = 0; i < N; i++) p[i] = 0; for(int i = 1; i <= N - 5; i++) bit[i] = inf; for(int i = 1; i <= m; i++) { int x; scanf("%d", &x); for(int l = 0; l < N; l++) { if(x * l >= N) break; p[x * l] = max(p[x * l], x); } } for(int i = 0; i <= N - 5; i++) { dp[i] = get(i); if(!p[i]) continue; update(i + p[i] - 1, dp[i] + 1); } for(int i = 1; i <= q; i++) { int x; scanf("%d", &x); if(dp[x] == inf) printf("oo\n"); else printf("%d\n", dp[x]); } }

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
brunhilda.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...