#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |