Submission #655147

#	Time	Username	Problem	Language	Result	Execution time	Memory
655147		prvocislo	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	1693 ms	3308 KiB

vault

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

const int maxn = 305;
const ll inf = 1e18 + 5, z = 2 * maxn * maxn;
int m;
ll l;
vector<ll> a(maxn * 2 + 5);
vector<ll> g(maxn * 2 + 5); // volba pazraveho riesenia
ll cnt = 0;
vector<ll> dp(z * 2 + 5, -inf); // dp[layer][zero + sucet oproti povodnemu greedy]
void upd(ll& a, ll b)
{
    a = max(a, b);
}
void apply(ll siz, ll cost)
{
    if (siz > 0)
    {
        for (ll j = z - siz; j >= -z; j--) if (dp[z + j] != -inf) upd(dp[z + j + siz], dp[z + j] + cost);
    }
    else
    {
        for (ll j = -z - siz; j <= z; j++) if (dp[z + j] != -inf) upd(dp[z + j + siz], dp[z + j] + cost);
    }
}
ll divup(ll a, ll b)
{
    return (a + b - 1) / b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> l;
    ll sum = 0;
    for (ll i = -m; i <= m; i++) cin >> a[m + i], sum += a[m + i] * i;
    if (sum > l)
    {
        l *= -1ll;
        reverse(a.begin(), a.begin() + 2 * m + 1);
    }
    // sum < l -> v greedy rieseni zoberieme vsetky kladne a nejaky prefix zapornych
    sum = 0;
    for (ll i = 0; i <= m; i++) g[m + i] = a[m + i], sum += a[m + i] * i, cnt += a[m + i];
    if (sum < l)
    {
        cout << "impossible\n";
        return 0;
    }
    for (ll i = -1; i >= -m; i--)
    {
        if (l <= sum + a[m + i] * i) g[m + i] = a[m + i], sum += a[m + i] * i, cnt += a[m + i];
        else
        {
            ll k = divup(sum - l, -i);
            g[m + i] = k, sum += k * i, cnt += k;
            break;
        }
    }
    int ly = 0;
    dp[z] = cnt;
    for (ll i = -m; i <= m; i++)
    {
        vector<ll> jump;
        ll neg = min(g[m + i], 2ll * m);
        if (neg > 0)
        {
            for (ll j = 1; j <= neg; j <<= 1ll) if (j - 1 <= neg) jump.push_back(j), neg -= j;
            jump.push_back(neg);
            for (ll j : jump) apply(j * -i, -j);
        }
        ll pos = min(a[m + i] - g[m + i], 2ll * m);
        if (pos > 0)
        {
            for (ll j = 1; j <= pos; j <<= 1ll) if (j - 1 <= pos) jump.push_back(j), pos -= j;
            jump.push_back(pos);
            for (ll j : jump) apply(j * i, j);
        }
    }
    ll d = l - sum;
    if (d > (ll)z || dp[z + d] == -inf) cout << "impossible\n";
    else cout << dp[z + d] << "\n";
    return 0;
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:77:9: warning: unused variable 'ly' [-Wunused-variable]
   77 |     int ly = 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: 10 / 10
• Subtask 6-2: 10 / 10