oj.uz

Submission #1069141

# Submission time Handle Problem Language Result Execution time Memory
1069141 2024-08-21T16:19:42 Z ortsac Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 1000 ms 86608 KB 
#include <bits/stdc++.h>
 
using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e7;
int dp[MAXN + 10];
set<pii> s;

int32_t main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        s.insert({a, a});
    }
    for (int i = 1; i <= MAXN; i++) {
        dp[i] = inf;
        int mx;
        while ((((*s.begin()).fr + (*s.begin()).se) <= i)) {
            auto u = *s.begin();
            s.erase(s.begin());
            s.insert({u.fr + u.se, u.se});
        }
        dp[i] = min(dp[i], dp[i - mx] + 1);
    }
    while (q--) {
        int x;
        cin >> x;
        if (dp[x] == inf) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
}

Compilation message

brunhilda.cpp: In function 'int32_t main()':
brunhilda.cpp:25:13: warning: 'mx' is used uninitialized in this function [-Wuninitialized]
   25 |         int mx;
      |             ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 78676 KB Output isn't correct
2 Incorrect 534 ms 78672 KB Output isn't correct
3 Incorrect 299 ms 78700 KB Output isn't correct
4 Incorrect 113 ms 78536 KB Output isn't correct
5 Incorrect 204 ms 78580 KB Output isn't correct
6 Incorrect 103 ms 78552 KB Output isn't correct
7 Incorrect 307 ms 78660 KB Output isn't correct
8 Incorrect 453 ms 78676 KB Output isn't correct
9 Incorrect 749 ms 78672 KB Output isn't correct
10 Execution timed out 1061 ms 78508 KB Time limit exceeded
11 Incorrect 766 ms 78672 KB Output isn't correct
12 Incorrect 82 ms 78528 KB Output isn't correct
13 Execution timed out 1024 ms 35152 KB Time limit exceeded
14 Execution timed out 1020 ms 32988 KB Time limit exceeded
15 Incorrect 633 ms 78500 KB Output isn't correct
16 Incorrect 568 ms 78592 KB Output isn't correct
17 Incorrect 308 ms 78552 KB Output isn't correct
18 Incorrect 120 ms 78708 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 315 ms 79440 KB Output isn't correct
2 Incorrect 298 ms 84900 KB Output isn't correct
3 Execution timed out 1085 ms 44108 KB Time limit exceeded
4 Incorrect 562 ms 78852 KB Output isn't correct
5 Execution timed out 1088 ms 54608 KB Time limit exceeded
6 Incorrect 504 ms 78676 KB Output isn't correct
7 Incorrect 297 ms 79440 KB Output isn't correct
8 Incorrect 486 ms 78724 KB Output isn't correct
9 Execution timed out 1044 ms 46160 KB Time limit exceeded
10 Execution timed out 1059 ms 44368 KB Time limit exceeded
11 Execution timed out 1049 ms 31468 KB Time limit exceeded
12 Execution timed out 1067 ms 72788 KB Time limit exceeded
13 Incorrect 214 ms 78672 KB Output isn't correct
14 Incorrect 555 ms 78816 KB Output isn't correct
15 Execution timed out 1043 ms 38512 KB Time limit exceeded
16 Incorrect 293 ms 85076 KB Output isn't correct
17 Execution timed out 1081 ms 35620 KB Time limit exceeded
18 Execution timed out 1071 ms 48632 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 38640 KB Time limit exceeded
2 Execution timed out 1060 ms 31060 KB Time limit exceeded
3 Execution timed out 1069 ms 30036 KB Time limit exceeded
4 Execution timed out 1058 ms 64200 KB Time limit exceeded
5 Incorrect 617 ms 86528 KB Output isn't correct
6 Execution timed out 1064 ms 35692 KB Time limit exceeded
7 Execution timed out 1069 ms 61504 KB Time limit exceeded
8 Execution timed out 1064 ms 37640 KB Time limit exceeded
9 Execution timed out 1066 ms 38024 KB Time limit exceeded
10 Execution timed out 1059 ms 55956 KB Time limit exceeded
11 Execution timed out 1081 ms 79236 KB Time limit exceeded
12 Execution timed out 1082 ms 39832 KB Time limit exceeded
13 Execution timed out 1044 ms 33364 KB Time limit exceeded
14 Execution timed out 1075 ms 67480 KB Time limit exceeded
15 Execution timed out 1014 ms 31008 KB Time limit exceeded
16 Execution timed out 1025 ms 27836 KB Time limit exceeded
17 Execution timed out 1037 ms 40456 KB Time limit exceeded
18 Execution timed out 1070 ms 30388 KB Time limit exceeded
19 Incorrect 392 ms 79184 KB Output isn't correct
20 Execution timed out 1031 ms 28688 KB Time limit exceeded
21 Execution timed out 1008 ms 45428 KB Time limit exceeded
22 Execution timed out 1039 ms 36656 KB Time limit exceeded
23 Incorrect 688 ms 81748 KB Output isn't correct
24 Incorrect 396 ms 79612 KB Output isn't correct
25 Execution timed out 1054 ms 55924 KB Time limit exceeded
26 Execution timed out 1037 ms 56404 KB Time limit exceeded
27 Execution timed out 1026 ms 32992 KB Time limit exceeded
28 Incorrect 482 ms 79724 KB Output isn't correct
29 Execution timed out 1066 ms 45396 KB Time limit exceeded
30 Execution timed out 1049 ms 45660 KB Time limit exceeded
31 Incorrect 599 ms 79696 KB Output isn't correct
32 Incorrect 786 ms 79696 KB Output isn't correct
33 Incorrect 262 ms 79696 KB Output isn't correct
34 Execution timed out 1006 ms 61520 KB Time limit exceeded
35 Incorrect 544 ms 79696 KB Output isn't correct
36 Execution timed out 1067 ms 38332 KB Time limit exceeded
37 Incorrect 558 ms 86608 KB Output isn't correct
38 Execution timed out 1035 ms 37920 KB Time limit exceeded
39 Incorrect 467 ms 79900 KB Output isn't correct
40 Execution timed out 1035 ms 47712 KB Time limit exceeded
41 Execution timed out 1053 ms 71320 KB Time limit exceeded
42 Execution timed out 1047 ms 32188 KB Time limit exceeded