Submission #655141

#	Time	Username	Problem	Language	Result	Execution time	Memory
655141		prvocislo	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	188 ms	3208 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);
    }
}
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);
    }
    // l < sum -> v greedy rieseni zoberieme vsetky zaporne a nejaky prefix kladnych
    sum = 0;
    for (ll i = -m; i <= m; i++)
    {
        ll k = min(a[m + i], (i <= 0 ? inf : (l - sum) / i));
        g[m + i] += k, sum += k * i, cnt += k;
    }
    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:62:9: warning: unused variable 'ly' [-Wunused-variable]
   62 |     int ly = 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