제출 #1352088

#제출 시각아이디문제언어결과실행 시간메모리
1352088AishaUplifting Excursion (BOI22_vault)C++20
0 / 100
5091 ms589824 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
const int inf = 1e18;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
    int m, wt; cin >> m >> wt;
    map <int, int> f, mf;
    for (int i = -m; i <= m; i ++) {
        int x; cin >> x; 
        if (i < 0) mf[-i] = x;
        else f[i] = x;
    }

    /*
    for (auto [i, x] : f) {
        if (i == 0) continue;
        if (x == 0) continue;
        x --; f[i] = 1;
        int k = 2;
        while (k <= x) {
            x -= k;
            f[i * k] ++;
            k ++;
        }
        if (x) f[i * x] ++;
    }

    for (auto [i, x] : mf) {
        if (x == 0) continue;
        x --; mf[i] = 1;
        int k = 2;
        while (k <= x) {
            x -= k;
            mf[i * k] ++;
            k ++;
        }
        if (x) mf[i * x] ++;
    }
        */

    vector <int> a;
    for (auto [i, x] : f) {
        if (i == 0) continue;
        while (x --) a.push_back(i);
    }
    for (auto [i, x] : mf) {
        while (x --) a.push_back(-i);
    }

    int n = a.size();
    map <int, int> cnt; cnt[-0] = 0;

    bool ok = false;

    for (int i = 0; i < n; i ++) {
       // cout << a[i] << endl;
        if (a[i] < 0 && !ok) {
            map <int, int> cntc;
            for (auto [x, c] : cnt) {
                cntc[-x] = c;
            }
            cnt = cntc;
            ok = true;
        }
        for (auto [x, c] : cnt) {
           // cout << x << ' ' << c << endl;
            // -x kattadan kichikka qarab
            if (!ok) cnt[x - a[i]] = max(cnt[x - a[i]], cnt[x] + 1);
            else cnt[x + a[i]] = max(cnt[x + a[i]], cnt[x] + 1);
        }
    }

    if (ok && cnt.find(wt) == cnt.end() || !ok && cnt.find(-wt) == cnt.end()) cout << "impossible" << endl;
    else cout << (ok ? cnt[wt] : cnt[-wt]) + f[0] << endl;
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...