Submission #655124

#	Time	Username	Problem	Language	Result	Execution time	Memory
655124		prvocislo	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	107 ms	12188 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<vector<ll> > dp(2, vector<ll>(z * 2 + 5, -inf)); // dp[layer][zero + sucet oproti povodnemu greedy]
void upd(ll& a, ll b)
{
    a = max(a, 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);
    }
    // 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;
    }
    vector<ll> tr;
    for (int i = 0; (1 << i) <= 2 * m; i++) tr.push_back((1 << i)), tr.push_back(-(1 << i));
    int ly = 0;
    dp[0][z] = cnt;
    for (ll i = -m; i <= m; i++)
    {
        dp[ly ^ 1] = dp[ly];
        for (ll sum = -z; sum <= z; sum++) if (dp[ly][z + sum] != -inf)
        {
            ll neg = g[m + i];
            if (i < 0) neg = min(neg, (z + sum) / (-i));
            if (i > 0) neg = min(neg, (z - sum) / i);
            vector<ll> jump;
            for (ll j = 2; j <= neg; j <<= 1ll) if (j - 1 <= neg) jump.push_back(j - 1), neg -= j - 1;
            jump.push_back(neg);
            for (ll j : jump) upd(dp[ly ^ 1][z + sum - j * i], dp[ly][z + sum] - j);
            ll pos = min(a[m + i] - g[m + i], 2ll * m);
            if (i > 0) pos = min(pos, (z + sum) / i);
            if (i < 0) pos = min(pos, (z - sum) / (-i));
            jump.clear();
            for (ll j = 2; j <= pos; j <<= 1ll) if (j - 1 <= pos) jump.push_back(j - 1), pos -= j - 1;
            jump.push_back(pos);
            for (ll j : jump) upd(dp[ly ^ 1][z + sum + j * i], dp[ly][z + sum] + j);
        }
        ly ^= 1;
    }
    ll d = l - sum;
    if (d > (ll)z || dp[ly][z + d] == -inf) cout << "impossible\n";
    else cout << dp[ly][z + d] << "\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