Submission #310128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310128	2020-10-05T22:09:37 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);
        if (ans == INT_MAX) cout << "oo" << '\n';
        else cout << 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	12 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	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	81 ms	1784 KB	Output is correct
14	Correct	76 ms	1784 KB	Output is correct
15	Correct	3 ms	1088 KB	Output is correct
16	Correct	4 ms	1088 KB	Output is correct
17	Correct	7 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	1063 ms	5952 KB	Time limit exceeded
2	Execution timed out	1059 ms	20972 KB	Time limit exceeded
3	Execution timed out	1053 ms	124656 KB	Time limit exceeded
4	Execution timed out	1043 ms	37252 KB	Time limit exceeded
5	Execution timed out	1092 ms	38504 KB	Time limit exceeded
6	Execution timed out	1083 ms	16884 KB	Time limit exceeded
7	Execution timed out	1085 ms	6068 KB	Time limit exceeded
8	Execution timed out	1094 ms	22116 KB	Time limit exceeded
9	Execution timed out	1097 ms	28656 KB	Time limit exceeded
10	Execution timed out	1098 ms	124656 KB	Time limit exceeded
11	Execution timed out	1104 ms	262132 KB	Time limit exceeded
12	Execution timed out	1097 ms	80516 KB	Time limit exceeded
13	Execution timed out	1093 ms	38708 KB	Time limit exceeded
14	Execution timed out	1084 ms	37124 KB	Time limit exceeded
15	Execution timed out	1068 ms	65652 KB	Time limit exceeded
16	Execution timed out	1089 ms	20848 KB	Time limit exceeded
17	Runtime error	1036 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Execution timed out	1105 ms	173932 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1080 ms	240684 KB	Time limit exceeded
2	Execution timed out	1076 ms	14512 KB	Time limit exceeded
3	Execution timed out	1092 ms	184688 KB	Time limit exceeded
4	Execution timed out	1097 ms	114188 KB	Time limit exceeded
5	Execution timed out	1064 ms	2092 KB	Time limit exceeded
6	Execution timed out	1054 ms	170276 KB	Time limit exceeded
7	Execution timed out	1090 ms	36400 KB	Time limit exceeded
8	Execution timed out	1095 ms	240756 KB	Time limit exceeded
9	Execution timed out	1102 ms	240884 KB	Time limit exceeded
10	Execution timed out	1084 ms	10912 KB	Time limit exceeded
11	Execution timed out	1102 ms	47648 KB	Time limit exceeded
12	Execution timed out	1097 ms	132512 KB	Time limit exceeded
13	Execution timed out	1090 ms	88860 KB	Time limit exceeded
14	Runtime error	506 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Execution timed out	1107 ms	252068 KB	Time limit exceeded
16	Execution timed out	1099 ms	150432 KB	Time limit exceeded
17	Execution timed out	1094 ms	17524 KB	Time limit exceeded
18	Execution timed out	1095 ms	14324 KB	Time limit exceeded
19	Execution timed out	1097 ms	16156 KB	Time limit exceeded
20	Execution timed out	1110 ms	184816 KB	Time limit exceeded
21	Runtime error	253 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1108 ms	187632 KB	Time limit exceeded
23	Execution timed out	1098 ms	2360 KB	Time limit exceeded
24	Execution timed out	1093 ms	13812 KB	Time limit exceeded
25	Execution timed out	1097 ms	11780 KB	Time limit exceeded
26	Execution timed out	1105 ms	114176 KB	Time limit exceeded
27	Execution timed out	1109 ms	184944 KB	Time limit exceeded
28	Execution timed out	1093 ms	58084 KB	Time limit exceeded
29	Execution timed out	1089 ms	54384 KB	Time limit exceeded
30	Execution timed out	1093 ms	30064 KB	Time limit exceeded
31	Execution timed out	1097 ms	38304 KB	Time limit exceeded
32	Execution timed out	1101 ms	43388 KB	Time limit exceeded
33	Execution timed out	1091 ms	14196 KB	Time limit exceeded
34	Execution timed out	1096 ms	36464 KB	Time limit exceeded
35	Execution timed out	1073 ms	20600 KB	Time limit exceeded
36	Execution timed out	1090 ms	31600 KB	Time limit exceeded
37	Execution timed out	1097 ms	2032 KB	Time limit exceeded
38	Execution timed out	1108 ms	170272 KB	Time limit exceeded
39	Execution timed out	1098 ms	13492 KB	Time limit exceeded
40	Execution timed out	1094 ms	64396 KB	Time limit exceeded
41	Execution timed out	1098 ms	55148 KB	Time limit exceeded
42	Runtime error	629 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Submission #310128

Compilation message

Subtask #1 17.7777777778 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
17.7777777778 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0