Submission #310127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310127	2020-10-05T22:08:32 Z	caoash	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.7778 / 100	1000 ms	262148 KB

brunhilda

#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

gp_hash_table<ll, int> dp;
int n, m; 
vector<ll> prim;

int solve(ll x) {
    if (dp.find(x) != dp.end()) {
        return dp[x];
    } else if (x == 0) {
        return dp[x] = 0;
    } else {
        int curr = INT_MAX;
        for (auto p : prim) {
            ll to = x - (x % p);
            if (to != x) {
                curr = min(curr, solve(to) + 1); 
            }
        }
        return dp[x] = curr;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        prim.pb(x);
    }
    for (int i = 0; i < m; i++) {
        ll v; cin >> v;
        int ans = solve(v);
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
}

Subtask #1

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	768 KB	Output isn't correct
2	Correct	4 ms	1088 KB	Output is correct
3	Correct	1 ms	768 KB	Output is correct
4	Correct	9 ms	1664 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Incorrect	1 ms	768 KB	Output isn't correct
7	Correct	1 ms	768 KB	Output is correct
8	Correct	2 ms	1088 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	1216 KB	Output is correct
11	Correct	3 ms	1216 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	91 ms	1896 KB	Output is correct
14	Correct	76 ms	1652 KB	Output is correct
15	Correct	4 ms	1088 KB	Output is correct
16	Correct	4 ms	1088 KB	Output is correct
17	Correct	9 ms	1660 KB	Output is correct
18	Correct	9 ms	1664 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1087 ms	5904 KB	Time limit exceeded
2	Execution timed out	1048 ms	20908 KB	Time limit exceeded
3	Execution timed out	1096 ms	124656 KB	Time limit exceeded
4	Execution timed out	1095 ms	37192 KB	Time limit exceeded
5	Execution timed out	1092 ms	38516 KB	Time limit exceeded
6	Execution timed out	1092 ms	16884 KB	Time limit exceeded
7	Execution timed out	1095 ms	5940 KB	Time limit exceeded
8	Execution timed out	1086 ms	22108 KB	Time limit exceeded
9	Execution timed out	1043 ms	28440 KB	Time limit exceeded
10	Execution timed out	1093 ms	124616 KB	Time limit exceeded
11	Execution timed out	1067 ms	262112 KB	Time limit exceeded
12	Execution timed out	1096 ms	80644 KB	Time limit exceeded
13	Execution timed out	1061 ms	38664 KB	Time limit exceeded
14	Execution timed out	1073 ms	37076 KB	Time limit exceeded
15	Execution timed out	1086 ms	65448 KB	Time limit exceeded
16	Execution timed out	1092 ms	20900 KB	Time limit exceeded
17	Execution timed out	1033 ms	262148 KB	Time limit exceeded
18	Execution timed out	1104 ms	174064 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1107 ms	240600 KB	Time limit exceeded
2	Execution timed out	1088 ms	14308 KB	Time limit exceeded
3	Execution timed out	1101 ms	184668 KB	Time limit exceeded
4	Execution timed out	1099 ms	114176 KB	Time limit exceeded
5	Execution timed out	1096 ms	1956 KB	Time limit exceeded
6	Execution timed out	1103 ms	170228 KB	Time limit exceeded
7	Execution timed out	1094 ms	36400 KB	Time limit exceeded
8	Execution timed out	1110 ms	240728 KB	Time limit exceeded
9	Execution timed out	1108 ms	240728 KB	Time limit exceeded
10	Execution timed out	1097 ms	10824 KB	Time limit exceeded
11	Execution timed out	1091 ms	47620 KB	Time limit exceeded
12	Execution timed out	1097 ms	132408 KB	Time limit exceeded
13	Execution timed out	1074 ms	88736 KB	Time limit exceeded
14	Runtime error	512 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Execution timed out	1087 ms	251812 KB	Time limit exceeded
16	Execution timed out	1100 ms	150548 KB	Time limit exceeded
17	Execution timed out	1096 ms	17648 KB	Time limit exceeded
18	Execution timed out	1090 ms	14312 KB	Time limit exceeded
19	Execution timed out	1097 ms	16032 KB	Time limit exceeded
20	Execution timed out	1105 ms	184820 KB	Time limit exceeded
21	Runtime error	252 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1107 ms	187628 KB	Time limit exceeded
23	Execution timed out	1086 ms	2372 KB	Time limit exceeded
24	Execution timed out	1089 ms	13912 KB	Time limit exceeded
25	Execution timed out	1086 ms	11652 KB	Time limit exceeded
26	Execution timed out	1105 ms	114180 KB	Time limit exceeded
27	Execution timed out	1107 ms	184816 KB	Time limit exceeded
28	Execution timed out	1096 ms	58216 KB	Time limit exceeded
29	Execution timed out	1047 ms	54384 KB	Time limit exceeded
30	Execution timed out	1092 ms	30188 KB	Time limit exceeded
31	Execution timed out	1067 ms	38172 KB	Time limit exceeded
32	Execution timed out	1094 ms	43396 KB	Time limit exceeded
33	Execution timed out	1072 ms	14200 KB	Time limit exceeded
34	Execution timed out	1092 ms	36460 KB	Time limit exceeded
35	Execution timed out	1087 ms	20472 KB	Time limit exceeded
36	Execution timed out	1086 ms	31540 KB	Time limit exceeded
37	Execution timed out	1093 ms	1948 KB	Time limit exceeded
38	Execution timed out	1096 ms	170268 KB	Time limit exceeded
39	Execution timed out	1085 ms	13548 KB	Time limit exceeded
40	Execution timed out	1097 ms	64284 KB	Time limit exceeded
41	Execution timed out	1084 ms	55032 KB	Time limit exceeded
42	Runtime error	683 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)