답안 #710790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710790	2023-03-15T19:44:28 Z	pls33	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	243 ms	81100 KB

brunhilda

// 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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