Submission #576894

#	Time	Username	Problem	Language	Result	Execution time	Memory
576894		wiwiho	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	2929 ms	15936 KiB

vault

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define ef emplace_front
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << setw(4) << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MAX = 1LL << 60;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int M, L;
    cin >> M >> L;
    assert(M <= 100);

    vector<ll> cnt(2 * M + 1);
    ll mx = 0, mn = 0;
    for(int i = 0; i <= 2 * M; i++){
        cin >> cnt[i];
        assert(cnt[i] <= 100);
        if(i - M > 0) mx += (i - M) * cnt[i];
        if(i - M < 0) mn += (i - M) * cnt[i];
    }
    //cerr << "ok\n";

    if(L < mn || mx < L){
        cout << "impossible\n";
        return 0;
    }

    ll total = mx - mn + 1;
    vector<ll> dp(total + 1, -1);
    dp[-mn] = cnt[M];

    //cerr << "test " << 0 << "  ";
    //printv(dp, cerr);
    
    for(int i = 0; i < M; i++){
        int t = -(i - M);
        auto calc = [&](int x){
            return dp[x] + x / t;
        };
        vector<deque<pll>> dq(t);
        for(int j = total - 1; j >= 0; j--){
            int id = j % t;
            while(!dq[id].empty() && dq[id].front().F / t > j / t + cnt[i]) dq[id].pof;
            while(!dq[id].empty() && dq[id].back().S <= calc(j)) dq[id].pob;
            if(dp[j] != -1){
                //cerr << "push " << j << " " << calc(j) << "\n";
                dq[id].eb(mp(j, calc(j)));
            }
            if(dq[id].empty()) continue;
            dp[j] = dq[id].front().S - j / t;
        }
        //cerr << "test " << -t << "  ";
        //printv(dp, cerr);
    }

    vector<ll> dp2(total, -MAX);

    for(int i = M + 1; i <= 2 * M; i++){
        int t = i - M;
        auto calc = [&](int x){
            return dp[x] - x / t;
        };
        vector<deque<pii>> dq(t);
        for(int j = 0; j < total; j++){
            int id = j % t;
            while(!dq[id].empty() && dq[id].front().F / t < j / t - cnt[i]) dq[id].pof;
            while(!dq[id].empty() && dq[id].back().S <= calc(j)) dq[id].pob;
            if(dp[j] != -1){
                //cerr << "push " << j << " " << calc(j) << "\n";
                dq[id].eb(mp(j, calc(j)));
            }
            if(dq[id].empty()) continue;
            dp[j] = dq[id].front().S + j / t;
        }
        //cerr << "test " << t << "  ";
        //printv(dp, cerr);
    }

    if(dp[-mn + L] < 0) cout << "impossible\n";
    else cout << dp[-mn + L] << "\n";
    
    return 0;
}

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