oj.uz

Submission #860606

# Submission time Handle Problem Language Result Execution time Memory
860606 2023-10-13T13:59:26 Z E869120 Uplifting Excursion (BOI22_vault) C++14
20 / 100
 1804 ms 47664 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 = M * M * M;
    long long Border = 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 51 ms 45744 KB Output is correct
2 Correct 78 ms 46280 KB Output is correct
3 Correct 33 ms 44608 KB Output is correct
4 Correct 193 ms 44844 KB Output is correct
5 Correct 841 ms 44548 KB Output is correct
6 Correct 847 ms 44564 KB Output is correct
7 Correct 867 ms 44968 KB Output is correct
8 Correct 813 ms 46104 KB Output is correct
9 Correct 838 ms 44340 KB Output is correct
10 Correct 906 ms 45080 KB Output is correct
11 Correct 925 ms 44332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 45744 KB Output is correct
2 Correct 78 ms 46280 KB Output is correct
3 Correct 33 ms 44608 KB Output is correct
4 Correct 193 ms 44844 KB Output is correct
5 Correct 841 ms 44548 KB Output is correct
6 Correct 847 ms 44564 KB Output is correct
7 Correct 867 ms 44968 KB Output is correct
8 Correct 813 ms 46104 KB Output is correct
9 Correct 838 ms 44340 KB Output is correct
10 Correct 906 ms 45080 KB Output is correct
11 Correct 925 ms 44332 KB Output is correct
12 Correct 52 ms 46004 KB Output is correct
13 Correct 75 ms 44600 KB Output is correct
14 Correct 32 ms 45604 KB Output is correct
15 Correct 196 ms 45312 KB Output is correct
16 Correct 838 ms 45976 KB Output is correct
17 Correct 843 ms 44912 KB Output is correct
18 Correct 871 ms 46236 KB Output is correct
19 Correct 830 ms 46104 KB Output is correct
20 Correct 813 ms 45728 KB Output is correct
21 Correct 895 ms 45160 KB Output is correct
22 Correct 883 ms 45800 KB Output is correct
23 Correct 1679 ms 45264 KB Output is correct
24 Correct 1640 ms 44604 KB Output is correct
25 Correct 1729 ms 47664 KB Output is correct
26 Correct 1654 ms 45224 KB Output is correct
27 Correct 1665 ms 44272 KB Output is correct
28 Correct 1804 ms 46028 KB Output is correct
29 Correct 1754 ms 45896 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 44532 KB Output is correct
2 Incorrect 30 ms 3412 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 191 ms 44532 KB Output is correct
2 Incorrect 30 ms 3412 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 191 ms 44532 KB Output is correct
2 Incorrect 30 ms 3412 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 51 ms 45744 KB Output is correct
2 Correct 78 ms 46280 KB Output is correct
3 Correct 33 ms 44608 KB Output is correct
4 Correct 193 ms 44844 KB Output is correct
5 Correct 841 ms 44548 KB Output is correct
6 Correct 847 ms 44564 KB Output is correct
7 Correct 867 ms 44968 KB Output is correct
8 Correct 813 ms 46104 KB Output is correct
9 Correct 838 ms 44340 KB Output is correct
10 Correct 906 ms 45080 KB Output is correct
11 Correct 925 ms 44332 KB Output is correct
12 Correct 191 ms 44532 KB Output is correct
13 Incorrect 30 ms 3412 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 191 ms 44532 KB Output is correct
2 Incorrect 30 ms 3412 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 51 ms 45744 KB Output is correct
2 Correct 78 ms 46280 KB Output is correct
3 Correct 33 ms 44608 KB Output is correct
4 Correct 193 ms 44844 KB Output is correct
5 Correct 841 ms 44548 KB Output is correct
6 Correct 847 ms 44564 KB Output is correct
7 Correct 867 ms 44968 KB Output is correct
8 Correct 813 ms 46104 KB Output is correct
9 Correct 838 ms 44340 KB Output is correct
10 Correct 906 ms 45080 KB Output is correct
11 Correct 925 ms 44332 KB Output is correct
12 Correct 52 ms 46004 KB Output is correct
13 Correct 75 ms 44600 KB Output is correct
14 Correct 32 ms 45604 KB Output is correct
15 Correct 196 ms 45312 KB Output is correct
16 Correct 838 ms 45976 KB Output is correct
17 Correct 843 ms 44912 KB Output is correct
18 Correct 871 ms 46236 KB Output is correct
19 Correct 830 ms 46104 KB Output is correct
20 Correct 813 ms 45728 KB Output is correct
21 Correct 895 ms 45160 KB Output is correct
22 Correct 883 ms 45800 KB Output is correct
23 Correct 1679 ms 45264 KB Output is correct
24 Correct 1640 ms 44604 KB Output is correct
25 Correct 1729 ms 47664 KB Output is correct
26 Correct 1654 ms 45224 KB Output is correct
27 Correct 1665 ms 44272 KB Output is correct
28 Correct 1804 ms 46028 KB Output is correct
29 Correct 1754 ms 45896 KB Output is correct
30 Correct 191 ms 44532 KB Output is correct
31 Incorrect 30 ms 3412 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 191 ms 44532 KB Output is correct
2 Incorrect 30 ms 3412 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 51 ms 45744 KB Output is correct
2 Correct 78 ms 46280 KB Output is correct
3 Correct 33 ms 44608 KB Output is correct
4 Correct 193 ms 44844 KB Output is correct
5 Correct 841 ms 44548 KB Output is correct
6 Correct 847 ms 44564 KB Output is correct
7 Correct 867 ms 44968 KB Output is correct
8 Correct 813 ms 46104 KB Output is correct
9 Correct 838 ms 44340 KB Output is correct
10 Correct 906 ms 45080 KB Output is correct
11 Correct 925 ms 44332 KB Output is correct
12 Correct 52 ms 46004 KB Output is correct
13 Correct 75 ms 44600 KB Output is correct
14 Correct 32 ms 45604 KB Output is correct
15 Correct 196 ms 45312 KB Output is correct
16 Correct 838 ms 45976 KB Output is correct
17 Correct 843 ms 44912 KB Output is correct
18 Correct 871 ms 46236 KB Output is correct
19 Correct 830 ms 46104 KB Output is correct
20 Correct 813 ms 45728 KB Output is correct
21 Correct 895 ms 45160 KB Output is correct
22 Correct 883 ms 45800 KB Output is correct
23 Correct 1679 ms 45264 KB Output is correct
24 Correct 1640 ms 44604 KB Output is correct
25 Correct 1729 ms 47664 KB Output is correct
26 Correct 1654 ms 45224 KB Output is correct
27 Correct 1665 ms 44272 KB Output is correct
28 Correct 1804 ms 46028 KB Output is correct
29 Correct 1754 ms 45896 KB Output is correct
30 Correct 191 ms 44532 KB Output is correct
31 Incorrect 30 ms 3412 KB Output isn't correct
32 Halted 0 ms 0 KB -