Submission #310124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310124	2020-10-05T22:06:26 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<int, int> dp;
int n, m; 
vi prim;

int solve(int 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) {
            int 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++) {
        int x; cin >> x;
        prim.pb(x);
    }
    for (int i = 0; i < m; i++) {
        int 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	576 KB	Output isn't correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	9 ms	1088 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Incorrect	1 ms	576 KB	Output isn't correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	768 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	896 KB	Output is correct
11	Correct	3 ms	896 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	78 ms	1212 KB	Output is correct
14	Correct	76 ms	1212 KB	Output is correct
15	Correct	2 ms	768 KB	Output is correct
16	Correct	4 ms	768 KB	Output is correct
17	Correct	7 ms	1088 KB	Output is correct
18	Correct	9 ms	1088 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1063 ms	5364 KB	Time limit exceeded
2	Execution timed out	1097 ms	21236 KB	Time limit exceeded
3	Execution timed out	1103 ms	124856 KB	Time limit exceeded
4	Execution timed out	1089 ms	34684 KB	Time limit exceeded
5	Execution timed out	1089 ms	38392 KB	Time limit exceeded
6	Execution timed out	1091 ms	14708 KB	Time limit exceeded
7	Execution timed out	1091 ms	5352 KB	Time limit exceeded
8	Execution timed out	1093 ms	17644 KB	Time limit exceeded
9	Execution timed out	1088 ms	28540 KB	Time limit exceeded
10	Execution timed out	1103 ms	124784 KB	Time limit exceeded
11	Execution timed out	1101 ms	262136 KB	Time limit exceeded
12	Execution timed out	1095 ms	78264 KB	Time limit exceeded
13	Execution timed out	1093 ms	36476 KB	Time limit exceeded
14	Execution timed out	1093 ms	34936 KB	Time limit exceeded
15	Execution timed out	1097 ms	65528 KB	Time limit exceeded
16	Execution timed out	1094 ms	21236 KB	Time limit exceeded
17	Execution timed out	1102 ms	260860 KB	Time limit exceeded
18	Execution timed out	1101 ms	174324 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1107 ms	240888 KB	Time limit exceeded
2	Execution timed out	1096 ms	14456 KB	Time limit exceeded
3	Execution timed out	1100 ms	184824 KB	Time limit exceeded
4	Execution timed out	1097 ms	111996 KB	Time limit exceeded
5	Execution timed out	1086 ms	2300 KB	Time limit exceeded
6	Execution timed out	1105 ms	169936 KB	Time limit exceeded
7	Execution timed out	1095 ms	36852 KB	Time limit exceeded
8	Execution timed out	1061 ms	240892 KB	Time limit exceeded
9	Execution timed out	1107 ms	240888 KB	Time limit exceeded
10	Execution timed out	1090 ms	9740 KB	Time limit exceeded
11	Execution timed out	1098 ms	46652 KB	Time limit exceeded
12	Execution timed out	1098 ms	131340 KB	Time limit exceeded
13	Execution timed out	1095 ms	88696 KB	Time limit exceeded
14	Runtime error	807 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Execution timed out	1068 ms	250764 KB	Time limit exceeded
16	Execution timed out	1101 ms	149424 KB	Time limit exceeded
17	Execution timed out	1092 ms	17608 KB	Time limit exceeded
18	Execution timed out	1098 ms	14456 KB	Time limit exceeded
19	Execution timed out	1057 ms	15112 KB	Time limit exceeded
20	Execution timed out	1067 ms	184768 KB	Time limit exceeded
21	Runtime error	263 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1102 ms	188016 KB	Time limit exceeded
23	Execution timed out	1094 ms	2152 KB	Time limit exceeded
24	Execution timed out	1086 ms	11744 KB	Time limit exceeded
25	Execution timed out	1078 ms	9256 KB	Time limit exceeded
26	Execution timed out	1078 ms	111868 KB	Time limit exceeded
27	Execution timed out	1093 ms	185460 KB	Time limit exceeded
28	Execution timed out	1088 ms	53428 KB	Time limit exceeded
29	Execution timed out	1095 ms	54772 KB	Time limit exceeded
30	Execution timed out	1066 ms	30204 KB	Time limit exceeded
31	Execution timed out	1098 ms	37132 KB	Time limit exceeded
32	Execution timed out	1087 ms	41176 KB	Time limit exceeded
33	Execution timed out	1095 ms	11952 KB	Time limit exceeded
34	Execution timed out	1092 ms	36852 KB	Time limit exceeded
35	Execution timed out	1094 ms	18164 KB	Time limit exceeded
36	Execution timed out	1089 ms	31988 KB	Time limit exceeded
37	Execution timed out	1082 ms	2428 KB	Time limit exceeded
38	Execution timed out	1098 ms	169836 KB	Time limit exceeded
39	Execution timed out	1080 ms	11424 KB	Time limit exceeded
40	Execution timed out	1099 ms	63984 KB	Time limit exceeded
41	Execution timed out	1097 ms	55412 KB	Time limit exceeded
42	Runtime error	1025 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)