답안 #310125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310125	2020-10-05T22:07:17 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) {
            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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 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	10 ms	1788 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	2 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	101 ms	1784 KB	Output is correct
14	Correct	85 ms	1656 KB	Output is correct
15	Correct	3 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	10 ms	1660 KB	Output is correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1081 ms	5868 KB	Time limit exceeded
2	Execution timed out	1044 ms	20544 KB	Time limit exceeded
3	Execution timed out	1098 ms	124444 KB	Time limit exceeded
4	Execution timed out	1093 ms	37112 KB	Time limit exceeded
5	Execution timed out	1096 ms	38264 KB	Time limit exceeded
6	Execution timed out	1092 ms	17004 KB	Time limit exceeded
7	Execution timed out	1049 ms	5808 KB	Time limit exceeded
8	Execution timed out	1095 ms	22116 KB	Time limit exceeded
9	Execution timed out	1094 ms	28148 KB	Time limit exceeded
10	Execution timed out	1062 ms	124404 KB	Time limit exceeded
11	Execution timed out	1098 ms	262024 KB	Time limit exceeded
12	Execution timed out	1098 ms	80628 KB	Time limit exceeded
13	Execution timed out	1089 ms	38640 KB	Time limit exceeded
14	Execution timed out	1057 ms	34808 KB	Time limit exceeded
15	Execution timed out	1097 ms	65400 KB	Time limit exceeded
16	Execution timed out	1092 ms	20556 KB	Time limit exceeded
17	Execution timed out	1104 ms	260724 KB	Time limit exceeded
18	Execution timed out	1098 ms	173684 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1108 ms	240464 KB	Time limit exceeded
2	Execution timed out	1091 ms	14176 KB	Time limit exceeded
3	Execution timed out	1112 ms	184568 KB	Time limit exceeded
4	Execution timed out	1097 ms	114232 KB	Time limit exceeded
5	Execution timed out	1092 ms	1656 KB	Time limit exceeded
6	Execution timed out	1101 ms	170252 KB	Time limit exceeded
7	Execution timed out	1093 ms	36084 KB	Time limit exceeded
8	Execution timed out	1101 ms	240632 KB	Time limit exceeded
9	Execution timed out	1101 ms	240632 KB	Time limit exceeded
10	Execution timed out	1090 ms	10760 KB	Time limit exceeded
11	Execution timed out	1094 ms	47752 KB	Time limit exceeded
12	Execution timed out	1102 ms	132396 KB	Time limit exceeded
13	Execution timed out	1102 ms	88824 KB	Time limit exceeded
14	Runtime error	515 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Execution timed out	1111 ms	251784 KB	Time limit exceeded
16	Execution timed out	1093 ms	150532 KB	Time limit exceeded
17	Execution timed out	1095 ms	17528 KB	Time limit exceeded
18	Execution timed out	1094 ms	14176 KB	Time limit exceeded
19	Execution timed out	1097 ms	16132 KB	Time limit exceeded
20	Execution timed out	1093 ms	184540 KB	Time limit exceeded
21	Runtime error	254 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1085 ms	187232 KB	Time limit exceeded
23	Execution timed out	1091 ms	2164 KB	Time limit exceeded
24	Execution timed out	1100 ms	13808 KB	Time limit exceeded
25	Execution timed out	1095 ms	11776 KB	Time limit exceeded
26	Execution timed out	1098 ms	114356 KB	Time limit exceeded
27	Execution timed out	1101 ms	184568 KB	Time limit exceeded
28	Execution timed out	1087 ms	58140 KB	Time limit exceeded
29	Execution timed out	1096 ms	54004 KB	Time limit exceeded
30	Execution timed out	1095 ms	29684 KB	Time limit exceeded
31	Execution timed out	1092 ms	38156 KB	Time limit exceeded
32	Execution timed out	1092 ms	43368 KB	Time limit exceeded
33	Execution timed out	1092 ms	14316 KB	Time limit exceeded
34	Execution timed out	1085 ms	36084 KB	Time limit exceeded
35	Execution timed out	1094 ms	20588 KB	Time limit exceeded
36	Execution timed out	1092 ms	31184 KB	Time limit exceeded
37	Execution timed out	1094 ms	1532 KB	Time limit exceeded
38	Execution timed out	1096 ms	170208 KB	Time limit exceeded
39	Execution timed out	1081 ms	13536 KB	Time limit exceeded
40	Execution timed out	1093 ms	64420 KB	Time limit exceeded
41	Execution timed out	1079 ms	54660 KB	Time limit exceeded
42	Runtime error	682 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

답안 #310125

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