Submission #1300447

#TimeUsernameProblemLanguageResultExecution timeMemory
1300447doqHeat Stroke (JOI24_heat)C++20
0 / 100
1 ms568 KiB
#include <bits/stdc++.h>
using namespace std;

// O(N^3) DP for JOI Heat (for teaching purposes, NOT for OJ)

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, N;
    cin >> L;
    vector<int> C(L+2);
    for (int i = 1; i <= L; i++) cin >> C[i];

    cin >> N;
    vector<int> X(N+1);
    for (int i = 1; i <= N; i++) cin >> X[i];

    // For each road i: store the times of patients
    vector<vector<int>> tim(L+2);
    for (int t = 1; t <= N; t++) {
        int r = X[t];
        tim[r].push_back(t);
    }

    // dp[i][j][t] : after processing road i,
    // sent j people to the right on road i,
    // and BV i+1 becomes full at time t (t = N+1 => never full)
    // dp value = max helicopters
    vector<vector<vector<int>>> dp(L+2,
        vector<vector<int>>(N+2, vector<int>(N+3, -INF)));

    // Base case: before processing any road
    dp[0][0][N+1] = 0;

    // Process each road i from 1..L-1
    for (int i = 1; i <= L-1; i++) {
        int Z = tim[i].size(); // number of patients on this road

        // Precompute prefix count:
        // cnt[k] = number of patients with time <= tim[i][k-1]
        vector<int> cnt(Z+1);
        for (int k = 1; k <= Z; k++) cnt[k] = k;

        // Try all j = number sent right on this road
        for (int j = 0; j <= Z; j++) {
            // You send j to the right, Z-j to the left

            for (int t = 1; t <= N+1; t++) {
                int best = dp[i-1][j][t];
                if (best < -1e8) continue;

                // left hospital = i, right hospital = i+1
                // It has capacity C[i] and C[i+1]

                // Let’s decide how many left we send to each hospital:
                // left_count = Z - j
                // right_count = j

                // Compute time BV i becomes full:
                int left_need = C[i];
                int right_need = C[i+1];

                int T_left = N+1, T_right = N+1;

                if (Z - j >= C[i]) T_left = tim[i][C[i]-1];
                if (j >= C[i+1])  T_right = tim[i][j-1];

                int full_time = max(T_left, T_right);

                // helicopters = number of patients whose time > full_time
                int heli = 0;
                for (int k = 0; k < Z; k++)
                    if (tim[i][k] > full_time) heli++;

                // Now update dp[i][j][t_new],
                // where t_new = T_right (time BV i+1 becomes full)
                int t_new = T_right;

                dp[i][j][t_new] = max(dp[i][j][t_new], best + heli);
            }
        }
    }

    // Final answer = max dp[L-1][0][t]
    int ans = 0;
    for (int t = 1; t <= N+1; t++)
        ans = max(ans, dp[L-1][0][t]);

    cout << ans << "\n";
    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...