Submission #653597

#	Time	Username	Problem	Language	Result	Execution time	Memory
653597		prvocislo	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	2277 ms	12324 KiB

vault

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxm = 35;
const int maxi = maxm * maxm * maxm;
const int inf = 1e9 + 5;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int m;
    ll l;
    cin >> m >> l;
    vector<ll> ok(m + 1, 0ll), bad(m + 1, 0ll);
    for (int i = -m; i <= m; i++)
    {
        if (i < 0) cin >> bad[abs(i)], l -= bad[abs(i)] * (ll)i;
        else cin >> ok[i];
    }
    // mame len tie, co su ok
    vector<vector<int> > pf(maxm, vector<int>(maxi, inf)); // najmensi pocet prvkov
    pf[0][0] = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < maxi; j++) if (pf[i - 1][j] != inf)
        {
            for (int d = 0; d <= min((ll)maxm, ok[i]) && j + i * d < maxi; d++)
            {
                pf[i][j + i * d] = min(pf[i][j + i * d], pf[i - 1][j] + d);
            }
        }
    }
    vector<vector<int> > sf(maxm, vector<int>(maxi, -inf)); // najvacsi pocet prvkov
    sf[m + 1][0] = 0;
    for (int i = m + 1; i > 0; i--)
    {
        for (int j = 0; j < maxi; j++) if (sf[i][j] != -inf)
        {
            for (int d = 0; d <= min((ll)maxm, ok[i - 1]) && j + i * d < maxi; d++)
            {
                sf[i - 1][j + i * d] = max(sf[i - 1][j + i * d], sf[i][j] + d);
            }
        }
    }
    ll ans = -1;
    ll sum = 0, all = ok[0];
    for (ll x = 1; x <= m; x++) // prvy z ktoreho zoberieme malo
    {
        for (ll dont = 0; dont < maxi; dont++) // tie co neberieme
        {
            if (pf[x - 1][dont] == inf) continue;
            ll need = l - (sum - dont);
            if (need < 0) continue;
            for (ll big = need % x; big < maxi; big += x) if (sf[x + 1][big] != inf)
            {
                ll take = (need - big) / x;
                if (take < 0 || take > ok[x]) continue;
                ll cnt = all - (ll)pf[x - 1][dont] + (ll)sf[x + 1][big] + take;
                ans = max(ans, cnt);
            }
        }
        sum += x * ok[x], all += ok[x];
    }
    if (ans == -1) cout << "impossible\n";
    else cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10