Submission #710790

#	Time	Username	Problem	Language	Result	Execution time	Memory
710790		pls33	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	243 ms	81100 KiB

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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60