oj.uz

Submission #710790

# Submission time Handle Problem Language Result Execution time Memory
710790 2023-03-15T19:44:28 Z pls33 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 243 ms 81100 KB 
// boi2013 day2 task1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("gim.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int p, n;
    cin >> p >> n;

    vi32 prime(p);
    for (auto &i : prime)
    {
        cin >> i;
    }

    int upper = 0;
    vi32 group(n);
    for (auto &i : group)
    {
        cin >> i;
        upper = max(upper, i);
    }

    vi32 max_decrease(upper + 1, 0);
    max_decrease[1] = 1;
    for (auto &i : prime)
    {
        for (int j = 1; i * j <= upper + 1; j++)
        {
            max_decrease[i * j - 1] = i - 1;
        }
    }

    for (auto &j : prime)
    {
        max_decrease.back() = max(max_decrease.back(), upper % j);
    }

    for (int i = (int)max_decrease.size() - 1; i > 0; i--)
    {
        max_decrease[i - 1] = max(max_decrease[i - 1], max_decrease[i] - 1);
    }

    /*for (int i = 0; i < (int)max_decrease.size(); i++)
    {
        int ans = 0;
        for (auto &j : prime)
        {
            ans = max(ans, i % j);
        }
    }*/

    vi32 dp(upper + 1, INT_MAX);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i < (int)dp.size(); i++)
    {
        if (!max_decrease[i] || dp[i - max_decrease[i]] == INT_MAX)
        {
            continue;
        }
        dp[i] = 1 + dp[i - max_decrease[i]];
    }

    for (auto &i : group)
    {
        if (dp[i] == INT_MAX)
        {
            cout << "oo\n";
        }
        else
        {
            cout << dp[i] << '\n';
        }
    }

    return 0;
}

Compilation message

brunhilda.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
brunhilda.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 2 ms 412 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 77812 KB Output is correct
2 Correct 77 ms 71828 KB Output is correct
3 Correct 113 ms 37936 KB Output is correct
4 Correct 88 ms 71100 KB Output is correct
5 Correct 41 ms 21168 KB Output is correct
6 Correct 33 ms 27336 KB Output is correct
7 Correct 72 ms 77816 KB Output is correct
8 Correct 34 ms 29616 KB Output is correct
9 Correct 43 ms 21396 KB Output is correct
10 Correct 107 ms 37884 KB Output is correct
11 Correct 215 ms 78916 KB Output is correct
12 Correct 110 ms 67128 KB Output is correct
13 Correct 77 ms 77916 KB Output is correct
14 Correct 94 ms 71088 KB Output is correct
15 Correct 58 ms 25804 KB Output is correct
16 Correct 76 ms 71900 KB Output is correct
17 Correct 196 ms 77548 KB Output is correct
18 Correct 175 ms 79608 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 79624 KB Output is correct
2 Correct 243 ms 79460 KB Output is correct
3 Correct 163 ms 56828 KB Output is correct
4 Correct 151 ms 79808 KB Output is correct
5 Correct 104 ms 81100 KB Output is correct
6 Correct 209 ms 80076 KB Output is correct
7 Correct 111 ms 57364 KB Output is correct
8 Correct 196 ms 79660 KB Output is correct
9 Correct 201 ms 79636 KB Output is correct
10 Correct 137 ms 78812 KB Output is correct
11 Correct 119 ms 78904 KB Output is correct
12 Correct 170 ms 78936 KB Output is correct
13 Correct 112 ms 41804 KB Output is correct
14 Correct 99 ms 49648 KB Output is correct
15 Correct 192 ms 78996 KB Output is correct
16 Correct 196 ms 79052 KB Output is correct
17 Correct 181 ms 79132 KB Output is correct
18 Correct 231 ms 79436 KB Output is correct
19 Correct 86 ms 78900 KB Output is correct
20 Correct 150 ms 56876 KB Output is correct
21 Correct 176 ms 80312 KB Output is correct
22 Correct 223 ms 81100 KB Output is correct
23 Correct 104 ms 80244 KB Output is correct
24 Correct 97 ms 79916 KB Output is correct
25 Correct 168 ms 79972 KB Output is correct
26 Correct 160 ms 79808 KB Output is correct
27 Correct 177 ms 57316 KB Output is correct
28 Correct 98 ms 80076 KB Output is correct
29 Correct 216 ms 81092 KB Output is correct
30 Correct 175 ms 80720 KB Output is correct
31 Correct 112 ms 79860 KB Output is correct
32 Correct 119 ms 79876 KB Output is correct
33 Correct 103 ms 79772 KB Output is correct
34 Correct 127 ms 57332 KB Output is correct
35 Correct 101 ms 80088 KB Output is correct
36 Correct 236 ms 80920 KB Output is correct
37 Correct 102 ms 81068 KB Output is correct
38 Correct 201 ms 79944 KB Output is correct
39 Correct 101 ms 79928 KB Output is correct
40 Correct 170 ms 79992 KB Output is correct
41 Correct 112 ms 57388 KB Output is correct
42 Correct 211 ms 80344 KB Output is correct