Submission #575480

#	Time	Username	Problem	Language	Result	Execution time	Memory
575480		_martynas	Uplifting Excursion (BOI22_vault)	C++11	100 / 100	1168 ms	1884 KiB

vault

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define DEBUG(x) cerr << #x << " = " << x << endl;

using ll = long long;

const int MXM = 305;
const ll C = 1e5;
const ll INF = 1e18;

ll m, l;
ll A[2*MXM+1];
ll cnt[2*MXM+1];
ll dp[2*C+1];
string my_ans;

void solve(istream& is, ostream &os)
{
    my_ans = "";
    memset(A, 0, sizeof(A));
    memset(cnt, 0, sizeof(cnt));
    memset(dp, 0, sizeof(dp));
    is >> m >> l;
    ll neg = 0, zeroes = 0;
    for(ll i = 0; i < 2*m+1; i++) {
        ll val = i-m;
        is >> A[i];
        if(val < 0) {
            neg += val*A[i];
        }
        else if(val == 0) {
            zeroes = A[i];
        }
    }
//    if(neg) {
//        cerr << "Not all positive\n";
//        return;
//    }
//    else {
//        cerr << "All positive\n";
//    }
    ll init_take = 0;
    ll curr = 0;
    // positive greedy take
    for(ll i = m+1; i < 2*m+1; i++) {
        ll val = i-m;
        ll left = l-curr-neg;
        ll take = min((left+val-1)/val, A[i]);
        cnt[i] += take;
        curr += val*take;
        init_take += take;
//        if(take) {
//            cerr << val << ": " << take << "\n";
//        }
    }
    // negative greedy take
    for(ll i = m-1; i >= 0; i--) {
        ll val = i-m, abs_val = labs(val);
        ll left = curr-l;
        ll take = min(left/abs_val, A[i]);
        cnt[i] += take;
        curr += val*take;
        init_take += take;
//        if(take) {
//            cerr << val << ": " << take << "\n";
//        }
    }
    DEBUG(curr);

    fill(dp, dp+2*C+1, -INF);
    dp[C] = init_take;
    for(ll i = 0; i < 2*m+1; i++) {
        ll val = i-m, abs_val = labs(val);
        if(val == 0) continue;
        // subtract used
        ll sub = min((2*C+1+abs_val-1)/abs_val, cnt[i]);
        // add unused
        ll add = min((2*C+1+abs_val-1)/abs_val, A[i]-cnt[i]);

//        if(sub || add) {
//            cerr << val << ":\n";
//            cerr << sub << " " << add << "\n";
//        }
        int sign = 1;
        if(val < 0) {
            swap(sub, add);
            sign = -1;
        }

        for(ll k = 0; k < 40 && sub > 0; k++) {
            ll w = 1LL << k;
            int times = (w & sub) ? 1 : 2;
            sub -= times*w;
            for(int t = 0; t < times; t++)
            for(ll j = w*abs_val; j < 2*C+1; j++) {
                dp[j-w*abs_val] = max(dp[j-w*abs_val], dp[j]-w*sign);
            }
        }

        for(ll k = 0; k < 40 && add > 0; k++) {
            ll w = 1LL << k;
            int times = (w & add) ? 1 : 2;
            add -= times*w;
            for(int t = 0; t < times; t++)
            for(ll j = 2*C-w*abs_val; j >= 0; j--) {
                dp[j+w*abs_val] = max(dp[j+w*abs_val], dp[j]+w*sign);
            }
        }
    }

    ll look_for = C+l-curr;
    DEBUG(look_for);
    if(look_for < 0 || look_for >= 2*C+1 || dp[look_for] < 0) {
        cout << "impossible";
        my_ans = "impossible";
    }
    else {
        cout << dp[look_for]+zeroes;
        my_ans = to_string(dp[look_for]+zeroes);
    }
    cout << "\n";
}

int main()
{
    bool manual;
    //cout << "manual (1, 0): "; cin >> manual;
    manual = true;
    if(manual) {
        solve(cin, cout);
    }
    else {
        const int TESTS = 62;
        for(int t = 1; t <= TESTS; t++) {
            auto stop = steady_clock::now();
            string input_file = "tests/" + to_string(t) + ".in";
            string output_file = "tests/" + to_string(t) + ".out";
            ifstream in(input_file);
            ifstream out(output_file);
            cerr << input_file << ":\n";
            solve(in, cout);
            if(my_ans != "") {
                cerr << "answers: ";
                string ans; getline(out, ans);
                cout << my_ans << ", expected = " << ans << "\n";
                if(my_ans != ans) {
                    break;
                }
            }
            auto dur = duration_cast<milliseconds>(steady_clock::now()-stop).count();
            cout << "Exec time: " << dur << " ms\n\n";
        }
    }

    return 0;
}
/*





*/

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 10 / 10