/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
template<typename T, typename U> using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0 //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt" : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg) ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg arg,Args... args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg arg,Args... args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const long long N = 1e7 + 1;
const int LIM = 20;
int dp[N];
void run() {
int m, q;
read(m, q);
vint primes;
int p[m];
v<pair<int, int>> vals;
rep(i, 0, m) {
get p[i];
if (p[i] > LIM)
for (int j = 1; j * p[i] < N; j++)
vals.pb({j * p[i], i});
else
primes.pb(p[i]);
}
sort(vals.begin(), vals.end());
int pt = 0;
long long mul = 1;
rep(i, 0, m) {
mul *= p[i];
if (mul > N) {
mul = 1e9;
break;
}
}
dp[0] = 0;
int cur[m];
rep(i, 0, m)
cur[i] = 1;
int pen = 0;
map<int, int> mx;
rep(i, 0, m)
if (p[i] > LIM)
mx[1]++;
rep(i, 1, N) {
while (vals[pt].fs == i) {
int j = vals[pt++].sc;
mx[cur[j]]--;
if (mx[cur[j]] == 0)
mx.erase(cur[j]);
cur[j] = -pen;
mx[cur[j]]++;
}
int d = 0;
if (!mx.empty())
d = ((*mx.rbegin()).fs) + pen;
for (int j : primes)
d = max(d, i % j);
dp[i] = dp[i - d] + 1;
pen++;
}
rep(i, 0, q) {
int n;
get n;
if (n >= mul)
put "oo";
else
put dp[n];
eol;
}
}
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
42976 KB |
Output is correct |
| 2 |
Correct |
778 ms |
55228 KB |
Output is correct |
| 3 |
Correct |
313 ms |
55228 KB |
Output is correct |
| 4 |
Correct |
418 ms |
55228 KB |
Output is correct |
| 5 |
Correct |
493 ms |
55228 KB |
Output is correct |
| 6 |
Correct |
219 ms |
55228 KB |
Output is correct |
| 7 |
Correct |
316 ms |
55228 KB |
Output is correct |
| 8 |
Correct |
327 ms |
55228 KB |
Output is correct |
| 9 |
Correct |
560 ms |
55228 KB |
Output is correct |
| 10 |
Execution timed out |
1037 ms |
59824 KB |
Time limit exceeded |
| 11 |
Correct |
969 ms |
61676 KB |
Output is correct |
| 12 |
Correct |
299 ms |
61676 KB |
Output is correct |
| 13 |
Execution timed out |
1089 ms |
132084 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1073 ms |
132092 KB |
Time limit exceeded |
| 15 |
Correct |
923 ms |
132092 KB |
Output is correct |
| 16 |
Correct |
844 ms |
132092 KB |
Output is correct |
| 17 |
Execution timed out |
1083 ms |
132092 KB |
Time limit exceeded |
| 18 |
Correct |
412 ms |
132092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
132092 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1066 ms |
132092 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1087 ms |
132220 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1084 ms |
132220 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1080 ms |
132220 KB |
Time limit exceeded |
| 6 |
Correct |
946 ms |
132220 KB |
Output is correct |
| 7 |
Execution timed out |
1081 ms |
132220 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1076 ms |
132220 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1090 ms |
132220 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1085 ms |
132220 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1092 ms |
132220 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1083 ms |
132220 KB |
Time limit exceeded |
| 13 |
Correct |
554 ms |
132220 KB |
Output is correct |
| 14 |
Execution timed out |
1073 ms |
132220 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1092 ms |
132220 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1085 ms |
132220 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1074 ms |
132220 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1077 ms |
132220 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
132220 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1089 ms |
132220 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1094 ms |
132220 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1085 ms |
132220 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1090 ms |
132220 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1094 ms |
132220 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1081 ms |
132284 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1079 ms |
132284 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1075 ms |
132284 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1085 ms |
132284 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1055 ms |
132284 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1067 ms |
132284 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1064 ms |
132284 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1055 ms |
132284 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1061 ms |
132284 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1076 ms |
132284 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1054 ms |
132284 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1063 ms |
132284 KB |
Time limit exceeded |
| 19 |
Correct |
920 ms |
132284 KB |
Output is correct |
| 20 |
Execution timed out |
1067 ms |
132284 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1076 ms |
132284 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1080 ms |
132284 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1082 ms |
132284 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1024 ms |
132284 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1080 ms |
132284 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1067 ms |
132284 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1071 ms |
132284 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1073 ms |
132284 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1073 ms |
132284 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1076 ms |
132284 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1077 ms |
132284 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1071 ms |
132284 KB |
Time limit exceeded |
| 33 |
Correct |
565 ms |
132284 KB |
Output is correct |
| 34 |
Execution timed out |
1075 ms |
132312 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1060 ms |
132312 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1070 ms |
132328 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1078 ms |
132328 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1071 ms |
132328 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1076 ms |
132328 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1072 ms |
132328 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1080 ms |
132328 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1080 ms |
132328 KB |
Time limit exceeded |
