제출 #1229881

#제출 시각아이디문제언어결과실행 시간메모리
1229881kawaiiFeast (NOI19_feast)C++20
30 / 100
90 ms8604 KiB
#include <vector> #include <numeric> #include <algorithm> #include <iostream> using namespace std; const long long INF = -3e18; // Needs to be smaller than any possible penalized value struct Result { long long value; int count; // For lexicographical comparison (maximize value, then minimize count) bool operator<(const Result& other) const { if (value != other.value) { return value < other.value; } return count > other.count; // Minimize count for ties } }; // O(N) DP function for the modified problem with penalty C Result solve_modified(int n, int k, const vector<long long>& a, const vector<long long>& prefix_sum, long long C) { vector<long long> dp(n + 1, INF); vector<int> count(n + 1, 0); dp[0] = 0; // 0 plates, 0 segments, 0 penalized value // best_prev_state stores (dp[k] - prefix_sum[k], count[k]) for k < i // Used to calculate max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) Result best_prev_state = {0LL, 0}; // Represents dp[0] - prefix_sum[0] for (int i = 1; i <= n; ++i) { // Option 1: Plate i is not the end of a segment. // Use result from dp[i-1], count[i-1]. // We initialize dp[i], count[i] with this implicitly in the loop structure, // but let's be explicit for clarity in the max comparison. Result option1 = {dp[i-1], count[i-1]}; // Option 2: Plate i is the end of a segment. // Value = max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + prefix_sum[i] - C // Count = count for max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + 1 Result option2 = {INF, 0}; // Default in case best_prev_state is INF (shouldn't happen with dp[0]=0) if (best_prev_state.value != INF) { // Check if best_prev_state is valid option2.value = best_prev_state.value + prefix_sum[i] - C; option2.count = best_prev_state.count + 1; } // Choose the better result for dp[i], count[i] if (option2.value > option1.value) { dp[i] = option2.value; count[i] = option2.count; } else if (option1.value > option2.value) { dp[i] = option1.value; count[i] = option1.count; } else { // option1.value == option2.value dp[i] = option1.value; count[i] = min(option1.count, option2.count); // Minimize count on tie } // Update best_prev_state for the next iteration (i+1) // It needs to include the state from dp[i] Result current_state_contribution = {dp[i] - prefix_sum[i], count[i]}; // Update best_prev_state if current_state_contribution is better if (current_state_contribution < best_prev_state) { // Using the overloaded < operator // best_prev_state is already better or equal with lower count } else { best_prev_state = current_state_contribution; } if (count[i] >= k){ return {0, k}; } } return {dp[n], count[n]}; } Result real_solve_modified(int n, int k, const vector<long long>& a, const vector<long long>& prefix_sum, long long C) { vector<long long> dp(n + 1, INF); vector<int> count(n + 1, 0); dp[0] = 0; // 0 plates, 0 segments, 0 penalized value // best_prev_state stores (dp[k] - prefix_sum[k], count[k]) for k < i // Used to calculate max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) Result best_prev_state = {0LL, 0}; // Represents dp[0] - prefix_sum[0] for (int i = 1; i <= n; ++i) { // Option 1: Plate i is not the end of a segment. // Use result from dp[i-1], count[i-1]. // We initialize dp[i], count[i] with this implicitly in the loop structure, // but let's be explicit for clarity in the max comparison. Result option1 = {dp[i-1], count[i-1]}; // Option 2: Plate i is the end of a segment. // Value = max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + prefix_sum[i] - C // Count = count for max_{0 <= k <= i-1} (dp[k] - prefix_sum[k]) + 1 Result option2 = {INF, 0}; // Default in case best_prev_state is INF (shouldn't happen with dp[0]=0) if (best_prev_state.value != INF) { // Check if best_prev_state is valid option2.value = best_prev_state.value + prefix_sum[i] - C; option2.count = best_prev_state.count + 1; } // Choose the better result for dp[i], count[i] if (option2.value > option1.value) { dp[i] = option2.value; count[i] = option2.count; } else if (option1.value > option2.value) { dp[i] = option1.value; count[i] = option1.count; } else { // option1.value == option2.value dp[i] = option1.value; count[i] = min(option1.count, option2.count); // Minimize count on tie } // Update best_prev_state for the next iteration (i+1) // It needs to include the state from dp[i] Result current_state_contribution = {dp[i] - prefix_sum[i], count[i]}; // Update best_prev_state if current_state_contribution is better if (current_state_contribution < best_prev_state) { // Using the overloaded < operator // best_prev_state is already better or equal with lower count } else { best_prev_state = current_state_contribution; } } return {dp[n], count[n]}; } // Main binary search logic int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<long long> prefix_sum(n + 1, 0); long long mx = 0, mn_sum = 0; for (int i = 0; i < n; ++i) { prefix_sum[i + 1] = prefix_sum[i] + a[i]; mn_sum = min(mn_sum, prefix_sum[i + 1]); mx = max(mx, prefix_sum[i + 1] - mn_sum); } // Binary search for penalty C long long low = -1e9 - 1, high = 1e18; // Sufficiently wide range for penalty Result final_result = {INF, 0}; // Store the best result found where count >= K for(int iter = 0; iter < 100; ++iter) { // Fixed iterations for precision long long mid = low + (high - low) / 2; Result current_res = solve_modified(n, k, a, prefix_sum, mid); if (current_res.count >= k) { // Penalty is too low or just right. Store this as a potential answer. // Try higher penalty to get closer to K or potentially a slightly better value at >= K. low = mid; } else { // Penalty is too high, got less than K segments. Need lower penalty. high = mid; } } // The final_result contains (penalized_value, count) from the DP run // with the optimal penalty C_opt (which is 'low' or 'high' after binary search). // We need the true max satisfaction for EXACTLY K segments. // MaxSat(K) = PenalizedValue + C_opt * K // Since final_result was obtained with penalty 'low' (the C_opt), // MaxSat(final_result.count) = final_result.value + low * final_result.count. // The answer for K segments is: final_result = real_solve_modified(n, k, a, prefix_sum, low); long long max_satisfaction_k = final_result.value + low * final_result.count; cout << max_satisfaction_k << endl; 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...