답안 #472991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472991	2021-09-14T17:38:46 Z	hidden1	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	57.7778 / 100	1000 ms	1124 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const int MAX_N = 1e5 + 10;
vector<int> arr;
int n, q;

const int MAX_Q = 1e8 + 10;
int dp[MAX_Q];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> q;
    arr.resize(n);
    for(int i = 0; i < n; i ++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());
    arr.resize(unique(arr.begin(), arr.end()) - arr.begin());

    while(q --) {
        int now;
        int cnt = 0;
        cin >> now;
        while(now) {
            int best = 0;
            for(int i = n - 1; i >= max(0, n - 300); i --) {
                chkmax(best, now % arr[i]);
            }
            if(best == 0) {
                cout << "oo" << endl;
                break;
            }
            now -= best;
            cnt ++;
        }
        if(!now) {
            cout << cnt << endl;
        }
    }
    return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	204 KB	Output is correct
2	Correct	2 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	9 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	5 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	7 ms	204 KB	Output is correct
11	Correct	21 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	2 ms	204 KB	Output is correct
14	Correct	16 ms	340 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	2 ms	204 KB	Output is correct
17	Correct	35 ms	332 KB	Output is correct
18	Correct	9 ms	332 KB	Output is correct

Subtask #2

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	52 ms	588 KB	Output is correct
3	Correct	8 ms	592 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	28 ms	460 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	9 ms	588 KB	Output is correct
10	Correct	37 ms	588 KB	Output is correct
11	Incorrect	5 ms	460 KB	Output isn't correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	332 KB	Output is correct
14	Correct	1 ms	208 KB	Output is correct
15	Correct	5 ms	468 KB	Output is correct
16	Correct	12 ms	588 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Incorrect	13 ms	716 KB	Output isn't correct

Subtask #3

20.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	574 ms	552 KB	Output is correct
2	Correct	319 ms	660 KB	Output is correct
3	Execution timed out	1052 ms	648 KB	Time limit exceeded
4	Execution timed out	1088 ms	328 KB	Time limit exceeded
5	Correct	508 ms	840 KB	Output is correct
6	Execution timed out	1093 ms	344 KB	Time limit exceeded
7	Correct	374 ms	872 KB	Output is correct
8	Correct	551 ms	656 KB	Output is correct
9	Correct	569 ms	716 KB	Output is correct
10	Execution timed out	1086 ms	464 KB	Time limit exceeded
11	Execution timed out	1083 ms	456 KB	Time limit exceeded
12	Execution timed out	1045 ms	344 KB	Time limit exceeded
13	Execution timed out	1080 ms	664 KB	Time limit exceeded
14	Execution timed out	1086 ms	204 KB	Time limit exceeded
15	Execution timed out	1087 ms	584 KB	Time limit exceeded
16	Execution timed out	1087 ms	452 KB	Time limit exceeded
17	Correct	142 ms	496 KB	Output is correct
18	Correct	320 ms	544 KB	Output is correct
19	Correct	275 ms	452 KB	Output is correct
20	Execution timed out	1022 ms	912 KB	Time limit exceeded
21	Execution timed out	1090 ms	204 KB	Time limit exceeded
22	Execution timed out	1046 ms	1124 KB	Time limit exceeded
23	Execution timed out	1093 ms	644 KB	Time limit exceeded
24	Execution timed out	1094 ms	340 KB	Time limit exceeded
25	Execution timed out	1092 ms	316 KB	Time limit exceeded
26	Execution timed out	1088 ms	452 KB	Time limit exceeded
27	Correct	568 ms	716 KB	Output is correct
28	Execution timed out	1089 ms	320 KB	Time limit exceeded
29	Execution timed out	1050 ms	1080 KB	Time limit exceeded
30	Execution timed out	1098 ms	836 KB	Time limit exceeded
31	Execution timed out	1096 ms	508 KB	Time limit exceeded
32	Execution timed out	1074 ms	328 KB	Time limit exceeded
33	Execution timed out	1085 ms	484 KB	Time limit exceeded
34	Correct	376 ms	780 KB	Output is correct
35	Execution timed out	1090 ms	328 KB	Time limit exceeded
36	Correct	671 ms	772 KB	Output is correct
37	Correct	512 ms	960 KB	Output is correct
38	Execution timed out	1095 ms	488 KB	Time limit exceeded
39	Execution timed out	1099 ms	448 KB	Time limit exceeded
40	Execution timed out	1090 ms	496 KB	Time limit exceeded
41	Correct	113 ms	724 KB	Output is correct
42	Execution timed out	1090 ms	320 KB	Time limit exceeded