제출 #1186396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186396		qwusha	Uplifting Excursion (BOI22_vault)	C++20	5 / 100	5094 ms	8784 KiB

vault

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;


const int K = 5e5;


signed main() {
    int m, L;
    cin >> m >> L;
    vector<int> a(2 * m + 1);
    for (int i = 0; i < 2 * m + 1; i++) {
        cin >> a[i];
    }
    vector<pair<int, int>> ch;
    if (m <= 100) {
        bitset<K> bs, nb;
        vector<int> maxi(K, -1);
        int cen = K / 2;
        bs[cen] = 1;
        maxi[cen] = 0;
        for (int i = 0; i < 2 * m + 1; i++) {
            int val = i - m;
            for (int j = 0; j < a[i]; j++) {
                if (val > 0) {
                    nb = (bs << val);
                } else {
                    nb = (bs >> abs(val));
                }
                int cur = nb._Find_next(0);
                ch.clear();
                while (cur < K) {
                    ch.push_back({cur, max(maxi[cur], maxi[cur - val] + 1)}) ;
                    cur = nb._Find_next(cur);
                }
                for (auto [ind, nv] : ch) {
                    maxi[ind] = max(maxi[ind], nv);
                }
                bs |= nb;
            }
        }
        if (abs(L) >= K / 2) {
            cout << "impossible" << '\n';
        } else {
            int val = L + cen;
            if (bs[val]) {
                cout << maxi[val] << '\n';
            } else {
                cout << "impossible" << '\n';
            }
        }
    }
}

• 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