Submission #310126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310126	2020-10-05T22:08:04 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; 
vi 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++) {
        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	768 KB	Output isn't correct
2	Correct	4 ms	1088 KB	Output is correct
3	Correct	2 ms	768 KB	Output is correct
4	Correct	9 ms	1660 KB	Output is correct
5	Correct	0 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	1 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	80 ms	1784 KB	Output is correct
14	Correct	76 ms	1656 KB	Output is correct
15	Correct	3 ms	1216 KB	Output is correct
16	Correct	5 ms	1088 KB	Output is correct
17	Correct	7 ms	1660 KB	Output is correct
18	Correct	9 ms	1660 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1085 ms	5808 KB	Time limit exceeded
2	Execution timed out	1093 ms	20440 KB	Time limit exceeded
3	Execution timed out	1062 ms	124396 KB	Time limit exceeded
4	Execution timed out	1094 ms	37112 KB	Time limit exceeded
5	Execution timed out	1089 ms	38264 KB	Time limit exceeded
6	Execution timed out	1094 ms	16920 KB	Time limit exceeded
7	Execution timed out	1093 ms	5944 KB	Time limit exceeded
8	Execution timed out	1101 ms	22116 KB	Time limit exceeded
9	Execution timed out	1101 ms	28156 KB	Time limit exceeded
10	Execution timed out	1107 ms	124404 KB	Time limit exceeded
11	Execution timed out	1114 ms	261752 KB	Time limit exceeded
12	Execution timed out	1104 ms	80504 KB	Time limit exceeded
13	Execution timed out	1097 ms	38648 KB	Time limit exceeded
14	Execution timed out	1094 ms	37236 KB	Time limit exceeded
15	Execution timed out	1101 ms	65400 KB	Time limit exceeded
16	Execution timed out	1051 ms	20724 KB	Time limit exceeded
17	Execution timed out	1060 ms	262148 KB	Time limit exceeded
18	Execution timed out	1102 ms	173684 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1102 ms	240500 KB	Time limit exceeded
2	Execution timed out	1091 ms	14200 KB	Time limit exceeded
3	Execution timed out	1100 ms	184488 KB	Time limit exceeded
4	Execution timed out	1097 ms	114136 KB	Time limit exceeded
5	Execution timed out	1093 ms	1576 KB	Time limit exceeded
6	Execution timed out	1102 ms	170124 KB	Time limit exceeded
7	Execution timed out	1095 ms	36084 KB	Time limit exceeded
8	Execution timed out	1101 ms	240632 KB	Time limit exceeded
9	Execution timed out	1108 ms	240504 KB	Time limit exceeded
10	Execution timed out	1094 ms	10884 KB	Time limit exceeded
11	Execution timed out	1095 ms	47700 KB	Time limit exceeded
12	Execution timed out	1099 ms	132360 KB	Time limit exceeded
13	Execution timed out	1092 ms	88824 KB	Time limit exceeded
14	Runtime error	508 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Execution timed out	1110 ms	251912 KB	Time limit exceeded
16	Execution timed out	1100 ms	149132 KB	Time limit exceeded
17	Execution timed out	1095 ms	17528 KB	Time limit exceeded
18	Execution timed out	1090 ms	14136 KB	Time limit exceeded
19	Execution timed out	1097 ms	16008 KB	Time limit exceeded
20	Execution timed out	1109 ms	184568 KB	Time limit exceeded
21	Runtime error	249 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1102 ms	187204 KB	Time limit exceeded
23	Execution timed out	1061 ms	2296 KB	Time limit exceeded
24	Execution timed out	1091 ms	13896 KB	Time limit exceeded
25	Execution timed out	1095 ms	11636 KB	Time limit exceeded
26	Execution timed out	1099 ms	114116 KB	Time limit exceeded
27	Execution timed out	1096 ms	184436 KB	Time limit exceeded
28	Execution timed out	1097 ms	58144 KB	Time limit exceeded
29	Execution timed out	1092 ms	54000 KB	Time limit exceeded
30	Execution timed out	1094 ms	29552 KB	Time limit exceeded
31	Execution timed out	1095 ms	38164 KB	Time limit exceeded
32	Execution timed out	1091 ms	43252 KB	Time limit exceeded
33	Execution timed out	1087 ms	14132 KB	Time limit exceeded
34	Execution timed out	1089 ms	36084 KB	Time limit exceeded
35	Execution timed out	1073 ms	20716 KB	Time limit exceeded
36	Execution timed out	1092 ms	31220 KB	Time limit exceeded
37	Execution timed out	1064 ms	1652 KB	Time limit exceeded
38	Execution timed out	1106 ms	170124 KB	Time limit exceeded
39	Execution timed out	1095 ms	13640 KB	Time limit exceeded
40	Execution timed out	1094 ms	64492 KB	Time limit exceeded
41	Execution timed out	1087 ms	54644 KB	Time limit exceeded
42	Runtime error	654 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)