ZeroJudge F174: Slicing Cake

Little Ming celebrates his birthday, and his family prepares a rectangular fruit cake for him. As the birthday boy, he can cut the cake first to eat. The cake is divided into N pieces, each with a different filling. Little Ming has different preferences for each filling. A positive preference value indicates liking, a negative value indicates dislike, and zero indicates no preference. To save time, Little Ming only chooses a continuous segment of the cake to eat, requiring only one or two cuts. Moreover, to allow others to have some cake too, he will only choose at most K pieces of cake (he may not take all K pieces or even none at all). For example, if N = 7 and K = 3, and Little Ming's preference scores for each piece of cake are as follows: 3, 7, -1, 9, 2, 2, 1. Taking the three pieces [7, -1, 9] gives the highest total score of 15, even though he doesn't like the middle one. Though he likes all the pieces in [9, 2, 2], the total score is only 13. Please write a program to calculate the highest total score Little Ming can get from the cake.

Sample Inputs/Outputs

Thought Process

You can achieve this by first calculating the prefix sum and storing it in an array. Then, you can use a for loop to iterate through each number and check if subtracting the minimum value of the previous K numbers from the current number is greater than the current maximum value (the answer). You can use a segment tree to efficiently record the minimum value of each segment to prevent timeouts.

Additionally, during the search in the segment tree, you can also check if the current number in the for loop minus the value of the current node exceeds the answer. If it is less than or equal to the answer, you can directly return from the function to save time. It's advisable to use long long int for calculating prefix sums and determining the answer to prevent overflow.

Sample Code－ZeroJudge F174: Slicing Cake

#include <iostream>
#include <vector>
using namespace std;

long long int tree[999999] = {}, ans;
int N, K;
vector<long long int>num;

long long int max(long long int a, long long int b)
{
    if (a > b) return a;
    return b;
}

long long int build(int l, int r, int index)
{
    if (l == r)
    {
        tree[index] = num[l];
        return num[l];
    }
    long long int left = build(l, (l+r)/2, (index*2)+1);
    long long int right = build(((l+r)/2)+1, r, (index*2)+2);
    tree[index] = min(left, right);
    return tree[index];
}

long long int query(int l, int r, int cl, int cr, int index, long long int value)
{
    if (value - tree[index] < ans) return 999999999;
    if (l == cl && r == cr) return tree[index];
    if (cl == cr) return tree[index];
    if (r <= (cl+cr)/2) return query(l, r, cl, (cl+cr)/2, (index*2)+1, value);
    else if (l > (cl+cr)/2) return query(l, r, ((cl+cr)/2)+1, cr, (index*2)+2, value);
    return min(query(l, r, cl, (cl+cr)/2, (index*2)+1, value), query(l, r, ((cl+cr)/2)+1, cr, (index*2)+2, value));
}

long long int math(int l, int r, long long int value)
{
    return query(l, r, 0, N-1, 0, value);
}

long long int calc(long long int hi, int l, int r)
{
    return hi - math(l, r, hi);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    long long int count = 0;
    for (int i = 0; i<N; i++)
    {
        long long int tmp;
        cin >> tmp;
        count += tmp;
        num.push_back(count);
    }
    ans = num[0];
    long long int hi = build(0, N-1, 0);
    for (int i = 1; i<K; i++)
    {
        ans = max(ans, calc(num[i], 0, i-1));
    }
    for (int i = K; i<N; i++)
    {
        ans = max(ans, calc(num[i], i-K, i-1));
    }
    cout << max(ans, 0) << "\n";
}

//ZeroJudge F174
//Dr. SeanXD