| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 74689 | 2018-09-06T14:41:09 Z | kjain_1810 | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 349 ms | 78528 KB |
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ind(n) scanf("%d", &n)
#define ind2(n, m) scanf("%d%d", &n, &m)
#define ind3(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define inlld(n) scanf("%lld", &n)
#define inlld2(n, m) scanf("%lld%lld", &n, &m)
#define inlld3(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
using namespace std;
const int N=1e7+5;
const int MOD=1e9+7;
typedef long long ll;
typedef long double ld;
int n, q;
int arr[N], dp[N];
int solve(int i)
{
if(i==0)
return 0;
if(dp[i]!=-1)
return dp[i];
int ans=-1e8, best=0;
if(q==1)
{
for(int a=n; a>=1; a--)
{
if(i%arr[a]==0)
continue;
if(i%arr[a]>ans)
{
ans=i%arr[a];
best=a;
}
}
}
else
{
for(int a=n; a>=max(1, n-500); a--)
{
if(i%arr[a]==0)
continue;
if(i%arr[a]>ans)
{
ans=i%arr[a];
best=a;
}
}
}
if(best)
return dp[i]=solve(i-ans)+1;
else
return 1e8;
}
signed main()
{
ind2(n, q);
for(int a=1; a<=n; a++)
ind(arr[a]);
memset(dp, -1, sizeof(dp));
while(q--)
{
int x;
ind(x);
int ans=solve(x);
if(ans<1e8)
printf("%d\n", ans);
else
printf("oo\n");
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 32 ms | 39544 KB | Output is correct |
| 2 | Correct | 34 ms | 39556 KB | Output is correct |
| 3 | Correct | 32 ms | 39556 KB | Output is correct |
| 4 | Correct | 38 ms | 39656 KB | Output is correct |
| 5 | Correct | 32 ms | 39760 KB | Output is correct |
| 6 | Correct | 32 ms | 39760 KB | Output is correct |
| 7 | Correct | 31 ms | 39760 KB | Output is correct |
| 8 | Correct | 33 ms | 39760 KB | Output is correct |
| 9 | Correct | 33 ms | 39844 KB | Output is correct |
| 10 | Correct | 33 ms | 39844 KB | Output is correct |
| 11 | Correct | 32 ms | 39916 KB | Output is correct |
| 12 | Correct | 33 ms | 39916 KB | Output is correct |
| 13 | Correct | 35 ms | 39916 KB | Output is correct |
| 14 | Correct | 55 ms | 39992 KB | Output is correct |
| 15 | Correct | 32 ms | 39992 KB | Output is correct |
| 16 | Correct | 32 ms | 39992 KB | Output is correct |
| 17 | Correct | 38 ms | 40028 KB | Output is correct |
| 18 | Correct | 37 ms | 40076 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 34 ms | 40128 KB | Output is correct |
| 2 | Correct | 50 ms | 41228 KB | Output is correct |
| 3 | Correct | 43 ms | 41572 KB | Output is correct |
| 4 | Correct | 38 ms | 41572 KB | Output is correct |
| 5 | Correct | 46 ms | 41828 KB | Output is correct |
| 6 | Correct | 33 ms | 41828 KB | Output is correct |
| 7 | Correct | 35 ms | 41912 KB | Output is correct |
| 8 | Correct | 34 ms | 41912 KB | Output is correct |
| 9 | Correct | 45 ms | 42540 KB | Output is correct |
| 10 | Correct | 41 ms | 43012 KB | Output is correct |
| 11 | Incorrect | 44 ms | 43108 KB | Output isn't correct |
| 12 | Correct | 33 ms | 43108 KB | Output is correct |
| 13 | Correct | 35 ms | 43108 KB | Output is correct |
| 14 | Correct | 33 ms | 43108 KB | Output is correct |
| 15 | Correct | 42 ms | 43560 KB | Output is correct |
| 16 | Correct | 46 ms | 44464 KB | Output is correct |
| 17 | Correct | 34 ms | 44464 KB | Output is correct |
| 18 | Incorrect | 48 ms | 45192 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 162 ms | 45660 KB | Output is correct |
| 2 | Correct | 114 ms | 46176 KB | Output is correct |
| 3 | Correct | 168 ms | 47096 KB | Output is correct |
| 4 | Correct | 302 ms | 47908 KB | Output is correct |
| 5 | Correct | 308 ms | 49576 KB | Output is correct |
| 6 | Correct | 324 ms | 50084 KB | Output is correct |
| 7 | Correct | 189 ms | 51448 KB | Output is correct |
| 8 | Correct | 154 ms | 51808 KB | Output is correct |
| 9 | Correct | 155 ms | 52400 KB | Output is correct |
| 10 | Correct | 102 ms | 52404 KB | Output is correct |
| 11 | Correct | 122 ms | 52528 KB | Output is correct |
| 12 | Correct | 128 ms | 52844 KB | Output is correct |
| 13 | Correct | 261 ms | 54080 KB | Output is correct |
| 14 | Correct | 90 ms | 55632 KB | Output is correct |
| 15 | Correct | 153 ms | 55632 KB | Output is correct |
| 16 | Correct | 141 ms | 55632 KB | Output is correct |
| 17 | Correct | 201 ms | 55632 KB | Output is correct |
| 18 | Correct | 116 ms | 55912 KB | Output is correct |
| 19 | Correct | 102 ms | 56260 KB | Output is correct |
| 20 | Correct | 167 ms | 57032 KB | Output is correct |
| 21 | Correct | 124 ms | 58188 KB | Output is correct |
| 22 | Correct | 310 ms | 59640 KB | Output is correct |
| 23 | Correct | 304 ms | 60448 KB | Output is correct |
| 24 | Correct | 289 ms | 60920 KB | Output is correct |
| 25 | Correct | 313 ms | 61784 KB | Output is correct |
| 26 | Correct | 321 ms | 62392 KB | Output is correct |
| 27 | Correct | 176 ms | 63700 KB | Output is correct |
| 28 | Correct | 275 ms | 64392 KB | Output is correct |
| 29 | Correct | 336 ms | 66156 KB | Output is correct |
| 30 | Correct | 314 ms | 67320 KB | Output is correct |
| 31 | Correct | 275 ms | 67744 KB | Output is correct |
| 32 | Correct | 349 ms | 68436 KB | Output is correct |
| 33 | Correct | 276 ms | 69144 KB | Output is correct |
| 34 | Correct | 188 ms | 70468 KB | Output is correct |
| 35 | Correct | 288 ms | 71300 KB | Output is correct |
| 36 | Correct | 305 ms | 72776 KB | Output is correct |
| 37 | Correct | 309 ms | 74356 KB | Output is correct |
| 38 | Correct | 322 ms | 74796 KB | Output is correct |
| 39 | Correct | 312 ms | 75624 KB | Output is correct |
| 40 | Correct | 322 ms | 76420 KB | Output is correct |
| 41 | Correct | 187 ms | 77832 KB | Output is correct |
| 42 | Correct | 286 ms | 78528 KB | Output is correct |