Submission #673996

#	Time	Username	Problem	Language	Result	Execution time	Memory
673996		stanislavpolyn	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	2598 ms	524288 KiB

vault

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e5 + 15e3;
const int M = 1e5;

int m;
ll l;
ve<int> a;

int dp_[N];

int& dp(int x) {
//    if (x + M < 0 || x + M >= N) {
//        cout << "GO " << x << "\n";
//        exit(0);
//    }
    x += M;
    assert(x >= 0 && x < N);
    return dp_[x];
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif


    cin >> m >> l;
//
//    ll sum = 0;
//    fr (i, 1, m) {
//        sum += 100 * i;
//    }


    fill(dp_, dp_ + N, -1e9);

//    cout << dp(M) << "\n";
//    cout << dp(-M) << "\n";
//
//    return 0;

    fr (i, -m, m) {
        int x;
        cin >> x;

        fr (j, 1, x) a.pb(i);
    }

//    l += N / 2;
    if (l + M < 0 || l + M >= N) {
        cout << "impossible\n";
        return 0;
    }

    dp(0) = 0;
//
//    dp(M);
//    dp(-M);

    fe (cur, a) {
//        cout << cur << " " << M << " " << -M + cur << "\n";
        if (cur >= 0) {
            rf (i, M, (-M + cur)) {
                umx(dp(i), dp(i - cur) + 1);
            }
        } else {
            fr (i, -M, M - cur) {
                umx(dp(i), dp(i - cur) + 1);
            }
        }
    }
//    return 0;

    if (dp(l) < 0) {
        cout << "impossible\n";
        return 0;
    }
//    fr (i, -10, 10) {
//        cout << i << " " << dp(i) << "\n";
//    }

    cout << dp(l) << "\n";
//    cout << sum << "\n";
    return 0;
}

• Subtask 1: 5 / 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