oj.uz

Submission #860607

# Submission time Handle Problem Language Result Execution time Memory
860607 2023-10-13T14:00:30 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1799 ms 47636 KB 
#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

vector<long long> SolveDP(long long N, long long LIM, vector<long long> List, vector<long long> Init) {
    vector<long long> dp(LIM + 1, -(1LL << 60));
    if (Init.size() == 0) dp[0] = 0;
    else {
        for (int i = 0; i < (int)Init.size(); i++) dp[i] = Init[i];
    }

    // DP Start
    for (int i = 0; i < N; i++) {
        vector<long long> ndp(LIM + 1, -(1LL << 60));
        long long kazu = i + 1;
        for (int j = 0; j < kazu; j++) {
            vector<pair<long long, long long>> maxi;
            int cur = 0;
            for (int k = j; k <= LIM; k += kazu) {
                long long val = dp[k] - (k / kazu);
                while (maxi.size() >= cur + 1) {
                    if (maxi[maxi.size() - 1].second <= val) maxi.pop_back();
                    else break;
                }
                maxi.push_back(make_pair(1LL * k, val));
                if (maxi[cur].second >= -(1LL << 59)) ndp[k] = maxi[cur].second + (k / kazu);
                while (cur < (int)maxi.size() && maxi[cur].first <= k - 1LL * kazu * List[i]) cur += 1;
            }
        }
        dp = ndp;
    }

    // Return
    return dp;
}

void Solve_Subtask2(long long M, long long L, vector<long long> A) {
    // Step 1. Calculate
    vector<long long> A1;
    vector<long long> A2;
    for (int i = M - 1; i >= 0; i--) A1.push_back(A[i]);
    for (int i = M + 1; i <= 2 * M; i++) A2.push_back(A[i]);
    vector<long long> DP1 = SolveDP(M, 700000, A1, vector<long long>{});
    vector<long long> DP2 = SolveDP(M, 700000, A2, vector<long long>{});

    // Step 2. Output
    long long Answer = -(1LL << 60);
    for (long long i = 0; i <= 700000LL - abs(L); i++) {
        long long idx1 = i;
        long long idx2 = i + abs(L); if (L < 0) swap(idx1, idx2);
        Answer = max(Answer, DP1[idx1] + DP2[idx2]);
    }
    if (Answer < 0LL) cout << "impossible" << endl;
    else cout << Answer + A[M] << endl;
}

void Solve_Subtask3(long long M, long long L, vector<long long> A) {
    long long Baseln = 2 * M * M * M;
    long long Border = 2 * M * M;
    vector<long long> L1(M + 1, 0);
    vector<long long> L2(M + 1, 0);
    vector<long long> L3(M, 0);
    vector<long long> L4(M, 0);
    vector<long long> M1(M + 1, 0);
    vector<long long> M2(M + 1, 0);
    vector<pair<long long, long long>> Cand1; Cand1.push_back(make_pair(0, 0));
    vector<pair<long long, long long>> Cand2; Cand2.push_back(make_pair(0, 0));

    // Step 1. Set Up
    for (int i = 0; i <= M - 1; i++) {
        int idx = M - i;
        long long Threshold = Border / idx;
        L1[idx - 0] = A[i] - min(A[i], Threshold);
        L3[idx - 1] = min(A[i], Threshold);
    }
    for (int i = M + 1; i <= 2 * M; i++) {
        int idx = i - M;
        long long Threshold = Border / idx;
        L2[idx - 0] = A[i] - min(A[i], Threshold);
        L4[idx - 1] = min(A[i], Threshold);
    }

    // Step 2. Base DP
    vector<long long> dp1 = SolveDP(M, Baseln, L3, vector<long long>{});
    vector<long long> dp2 = vector<long long>(Baseln + 1, -(1LL << 60));
    for (int i = 0; i <= Baseln; i++) dp2[Baseln - i] = dp1[i];
    vector<long long> dp3 = SolveDP(M, Baseln * 2, L4, dp2);

    // Step 3. Get Theoritical Value
    long long a1 = 0;
    long long a2 = 0;
    for (int i = 1; i <= M; i++) a1 += 1LL * i * L1[i];
    for (int i = 1; i <= M; i++) a2 += 1LL * i * L2[i];
    if (a2 - a1 > L) a2 = a1 + L;
    else a1 = a2 - L;
    if (a1 + Baseln < 0 || a2 + Baseln < 0) {
        cout << "impossible" << endl;
        return;
    }

    // Step 4. Get Candiates for L1
    long long rem1 = a1 + Baseln;
    long long cnt1 = 0;
    for (int i = 1; i <= M; i++) {
        M1[i] = min(L1[i], rem1 / i);
        rem1 -= 1LL * i * M1[i];
        cnt1 += M1[i];
    }
    for (int i = M; i >= 1; i--) {
        for (long long j = 0; j < M1[i]; j++) {
            rem1 += 1LL * i;
            cnt1 -= 1LL;
            if (rem1 > 2LL * Baseln) break;
            Cand1.push_back(make_pair((a1 + Baseln) - rem1, cnt1));
        }
        if (rem1 > 2LL * Baseln) break;
    }
    // cout << "L1 = "; for (int i = 1; i <= M; i++) cout << L1[i] << " "; cout << endl;
    // cout << "L2 = "; for (int i = 1; i <= M; i++) cout << L2[i] << " "; cout << endl;
    // cout << "Cand1 = "; for (int i = 0; i < Cand1.size(); i++) cout << "(" << Cand1[i].first << "," << Cand1[i].second << ") "; cout << endl;
    // cout << "Cand2 = "; for (int i = 0; i < Cand2.size(); i++) cout << "(" << Cand2[i].first << "," << Cand2[i].second << ") "; cout << endl;

    // Step 6. Brute Force
    long long Answer = -(1LL << 60);
    for (pair<long long, long long> v1 : Cand1) {
        for (pair<long long, long long> v2 : Cand2) {
            long long diff = L - (v2.first - v1.first);
            if (diff < -Baseln || diff > Baseln) continue;
            if (dp3[diff + Baseln] == -(1LL << 60)) continue;
            Answer = max(Answer, v1.second + v2.second + dp3[diff + Baseln]);
        }
    }

    // Step 7. Output
    if (Answer == -(1LL << 60)) cout << "impossible" << endl;
    else cout << Answer + A[M] << endl;
}

int main() {
    // Input
    long long M, L;
    cin >> M >> L;
    vector<long long> A(2 * M + 1, 0);
    for (int i = 0; i <= 2 * M; i++) cin >> A[i];

    // Judge if Subtask 2
    bool Subtask2 = true;
    if (M > 100) Subtask2 = false;
    for (int i = 0; i <= 2 * M; i++) {
        if (A[i] > 100) Subtask2 = false;
    }

    // Execution
    if (Subtask2 == true) Solve_Subtask2(M, L, A);
    else Solve_Subtask3(M, L, A);
    return 0;
}

Compilation message

vault.cpp: In function 'std::vector<long long int> SolveDP(long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
vault.cpp:25:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |                 while (maxi.size() >= cur + 1) {
      |                        ~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45236 KB Output is correct
2 Correct 70 ms 46016 KB Output is correct
3 Correct 32 ms 46012 KB Output is correct
4 Correct 193 ms 45220 KB Output is correct
5 Correct 800 ms 45160 KB Output is correct
6 Correct 832 ms 45812 KB Output is correct
7 Correct 874 ms 45296 KB Output is correct
8 Correct 830 ms 46424 KB Output is correct
9 Correct 829 ms 44524 KB Output is correct
10 Correct 885 ms 45936 KB Output is correct
11 Correct 892 ms 45480 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45236 KB Output is correct
2 Correct 70 ms 46016 KB Output is correct
3 Correct 32 ms 46012 KB Output is correct
4 Correct 193 ms 45220 KB Output is correct
5 Correct 800 ms 45160 KB Output is correct
6 Correct 832 ms 45812 KB Output is correct
7 Correct 874 ms 45296 KB Output is correct
8 Correct 830 ms 46424 KB Output is correct
9 Correct 829 ms 44524 KB Output is correct
10 Correct 885 ms 45936 KB Output is correct
11 Correct 892 ms 45480 KB Output is correct
12 Correct 55 ms 45304 KB Output is correct
13 Correct 73 ms 44312 KB Output is correct
14 Correct 34 ms 44692 KB Output is correct
15 Correct 194 ms 45312 KB Output is correct
16 Correct 812 ms 45236 KB Output is correct
17 Correct 801 ms 44248 KB Output is correct
18 Correct 845 ms 45328 KB Output is correct
19 Correct 819 ms 45308 KB Output is correct
20 Correct 844 ms 44452 KB Output is correct
21 Correct 891 ms 45788 KB Output is correct
22 Correct 881 ms 47636 KB Output is correct
23 Correct 1635 ms 44704 KB Output is correct
24 Correct 1579 ms 45456 KB Output is correct
25 Correct 1680 ms 45816 KB Output is correct
26 Correct 1630 ms 44524 KB Output is correct
27 Correct 1710 ms 44804 KB Output is correct
28 Correct 1799 ms 44504 KB Output is correct
29 Correct 1760 ms 45012 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 44392 KB Output is correct
2 Incorrect 60 ms 6320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 44392 KB Output is correct
2 Incorrect 60 ms 6320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 44392 KB Output is correct
2 Incorrect 60 ms 6320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45236 KB Output is correct
2 Correct 70 ms 46016 KB Output is correct
3 Correct 32 ms 46012 KB Output is correct
4 Correct 193 ms 45220 KB Output is correct
5 Correct 800 ms 45160 KB Output is correct
6 Correct 832 ms 45812 KB Output is correct
7 Correct 874 ms 45296 KB Output is correct
8 Correct 830 ms 46424 KB Output is correct
9 Correct 829 ms 44524 KB Output is correct
10 Correct 885 ms 45936 KB Output is correct
11 Correct 892 ms 45480 KB Output is correct
12 Correct 193 ms 44392 KB Output is correct
13 Incorrect 60 ms 6320 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 44392 KB Output is correct
2 Incorrect 60 ms 6320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45236 KB Output is correct
2 Correct 70 ms 46016 KB Output is correct
3 Correct 32 ms 46012 KB Output is correct
4 Correct 193 ms 45220 KB Output is correct
5 Correct 800 ms 45160 KB Output is correct
6 Correct 832 ms 45812 KB Output is correct
7 Correct 874 ms 45296 KB Output is correct
8 Correct 830 ms 46424 KB Output is correct
9 Correct 829 ms 44524 KB Output is correct
10 Correct 885 ms 45936 KB Output is correct
11 Correct 892 ms 45480 KB Output is correct
12 Correct 55 ms 45304 KB Output is correct
13 Correct 73 ms 44312 KB Output is correct
14 Correct 34 ms 44692 KB Output is correct
15 Correct 194 ms 45312 KB Output is correct
16 Correct 812 ms 45236 KB Output is correct
17 Correct 801 ms 44248 KB Output is correct
18 Correct 845 ms 45328 KB Output is correct
19 Correct 819 ms 45308 KB Output is correct
20 Correct 844 ms 44452 KB Output is correct
21 Correct 891 ms 45788 KB Output is correct
22 Correct 881 ms 47636 KB Output is correct
23 Correct 1635 ms 44704 KB Output is correct
24 Correct 1579 ms 45456 KB Output is correct
25 Correct 1680 ms 45816 KB Output is correct
26 Correct 1630 ms 44524 KB Output is correct
27 Correct 1710 ms 44804 KB Output is correct
28 Correct 1799 ms 44504 KB Output is correct
29 Correct 1760 ms 45012 KB Output is correct
30 Correct 193 ms 44392 KB Output is correct
31 Incorrect 60 ms 6320 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 44392 KB Output is correct
2 Incorrect 60 ms 6320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 45236 KB Output is correct
2 Correct 70 ms 46016 KB Output is correct
3 Correct 32 ms 46012 KB Output is correct
4 Correct 193 ms 45220 KB Output is correct
5 Correct 800 ms 45160 KB Output is correct
6 Correct 832 ms 45812 KB Output is correct
7 Correct 874 ms 45296 KB Output is correct
8 Correct 830 ms 46424 KB Output is correct
9 Correct 829 ms 44524 KB Output is correct
10 Correct 885 ms 45936 KB Output is correct
11 Correct 892 ms 45480 KB Output is correct
12 Correct 55 ms 45304 KB Output is correct
13 Correct 73 ms 44312 KB Output is correct
14 Correct 34 ms 44692 KB Output is correct
15 Correct 194 ms 45312 KB Output is correct
16 Correct 812 ms 45236 KB Output is correct
17 Correct 801 ms 44248 KB Output is correct
18 Correct 845 ms 45328 KB Output is correct
19 Correct 819 ms 45308 KB Output is correct
20 Correct 844 ms 44452 KB Output is correct
21 Correct 891 ms 45788 KB Output is correct
22 Correct 881 ms 47636 KB Output is correct
23 Correct 1635 ms 44704 KB Output is correct
24 Correct 1579 ms 45456 KB Output is correct
25 Correct 1680 ms 45816 KB Output is correct
26 Correct 1630 ms 44524 KB Output is correct
27 Correct 1710 ms 44804 KB Output is correct
28 Correct 1799 ms 44504 KB Output is correct
29 Correct 1760 ms 45012 KB Output is correct
30 Correct 193 ms 44392 KB Output is correct
31 Incorrect 60 ms 6320 KB Output isn't correct
32 Halted 0 ms 0 KB -