Submission #1105085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105085		MateiKing80	Uplifting Excursion (BOI22_vault)	C++14	80 / 100	5054 ms	18300 KiB

vault

#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 300;
int MAX_S;
int MIN_S;
const long long INF = 1e18;
int m;
unordered_map<int, long long> tk, ntk;
unordered_map<int, long long> dp, dpp;

void add(int x, int i)
{
    swap(dp, dpp);

    for(int s = MIN_S; s <= MAX_S; s ++)
        dp[s] = dpp[s];

    for(int s = MIN_S; s - i * x <= MAX_S; s ++)
        if(MIN_S <= s - i * x && s - i * x <= MAX_S)
            dp[s] = max(dp[s], dpp[s - i * x] + x);

    for(int s = MIN_S; s <= MAX_S; s ++)
        dp[s] = (dp[s] <= -INF + m ? -INF : dp[s]);
}

void substract(int x, int i)
{
    swap(dp, dpp);

    for(int s = MIN_S; s <= MAX_S; s ++)
        dp[s] = dpp[s];
    for(int s = MIN_S; s <= MAX_S; s ++)
        if(MIN_S <= s + i * x && s + i * x <= MAX_S)
            dp[s] = max(dp[s], dpp[s + i * x] - x);

    for(int s = MIN_S; s <= MAX_S; s ++)
        dp[s] = (dp[s] <= -INF + m ? -INF : dp[s]);
}

void afis()
{
    for(int s = MIN_S; s <= MAX_S; s ++)
        cout << dp[s] << " ";
    cout << "\n";
}

int main()
{
    long long l, u = 0, t = 0;

    cin >> m >> l;
    MIN_S = -m * m;
    MAX_S = m * m;
    for(int i = -m; i <= m; i ++)
    {
        cin >> ntk[i];
        u += ntk[i];
    }

    if(l < 0)
    {
        for(int i = 1; i <= m; i ++)
            swap(ntk[i], ntk[-i]);
        l = -l;
    }

    long long s = 0;
    for(int i = -m; i <= 0; i ++)
    {
        long long x = ntk[i];
        s += i * x;
        tk[i] += x;
        ntk[i] -= x;
        t += x;
        u -= x;
    }
    for(int i = 1; i <= m; i ++)
    {
        long long x = min(ntk[i], (l - s) / i);
        s += i * x;
        tk[i] += x;
        ntk[i] -= x;
        t += x;
        u -= x;
    }
    if(s + m < l)
    {
        for(int i = -m; i < 0; i ++)
        {
            long long x = min(tk[i], (l - s) / (-i));
            s -= i * x;
            tk[i] -= x;
            ntk[i] += x;
            t -= x;
            u += x;
        }
    }

    for(int s = MIN_S; s <= MAX_S; s ++)
        dp[s] = -INF;
    dp[0] = 0;

    for(int i = -m; i <= m; i ++)
    {
        int k, s;

        s = 0;
        k = min((long long)m, ntk[i]);
        for(int b = 0; s + (1 << b) <= k; s += (1 << b), b ++)
            add((1 << b), i);
        add(k - s, i);

        s = 0;
        k = min((long long)m, tk[i]);
        for(int b = 0; s + (1 << b) <= k; s += (1 << b), b ++)
            substract((1 << b), i);
        substract(k - s, i);
    }


    if(l - s > MAX_S || dp[l - s] == -INF)
        cout << "impossible\n";
    else
        cout << t + dp[l - s] << '\n';

    return 0;
}

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