Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of n sections…
- User
Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of n sections with tastiness values a1,a2,…,an . There are m creatures at the tea party, excluding Alice.
Alice will cut the cake into m+1 pieces. Formally, she will partition the cake into m+1 subarrays, where each subarray consists of some number of adjacent sections. The tastiness of a piece is the sum of tastiness of its sections. Afterwards, she will divvy these m+1 pieces up among the m creatures and herself (her piece can be empty). However, each of the m creatures will only be happy when the tastiness of its piece is v or more.
Alice wants to make sure every creature is happy. Limited by this condition, she also wants to maximize the tastiness of her own piece. Can you help Alice find the maximum tastiness her piece can have? If there is no way to make sure every creature is happy, output −1 .
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains three integers n,m,v (1≤m≤n≤2⋅105 ; 1≤v≤109 ) — the number of sections, the number of creatures, and the creatures' minimum requirement for tastiness, respectively.
The next line contains n space separated integers a1,a2,…,an (1≤ai≤109 ) — the tastinesses of the sections.
The sum of n over all test cases does not exceed 2⋅105 .
Output For each test case, output the maximum tastiness Alice can achieve for her piece, or −1 if there is no way to make sure every creature is happy.
Example InputCopy 7 6 2 1 1 1 10 1 1 10 6 2 2 1 1 10 1 1 10 6 2 3 1 1 10 1 1 10 6 2 10 1 1 10 1 1 10 6 2 11 1 1 10 1 1 10 6 2 12 1 1 10 1 1 10 6 2 12 1 1 1 1 10 10 OutputCopy 22 12 2 2 2 0 -1 Note For the first test case, Alice can give the first and second section as their own pieces, and then take the remaining 10+1+1+10=22 tastiness for herself. We can show that she cannot do any better.
For the second test case, Alice could give the first and second section as one piece, and the sixth section as one piece. She can then take the remaining 10+1+1=12 tastiness for herself. We can show that she cannot do any better.
For the seventh test case, Alice cannot give each creature a piece of at least 12 tastiness. type code in c++.Please quite short
- Assistant
To solve this problem, we need to maximize the sum of Alice's piece while ensuring that the remaining cake can be divided into
msubarrays where each subarray has a sum of at leastv. The approach involves leveraging a binary search strategy combined with precomputed prefix and suffix counts for efficient verification.Step-by-step Reasoning:
-
Prefix and Suffix Arrays:
- Prefix Count: This array stores the number of non-overlapping subarrays with sum ≥
vup to each index. This helps in quickly determining how many such subarrays exist before a certain point. - Suffix Count: Similarly, this array stores the number of non-overlapping subarrays with sum ≥
vstarting from each index to the end of the array. This helps in determining how many such subarrays exist after a certain point.
- Prefix Count: This array stores the number of non-overlapping subarrays with sum ≥
-
Binary Search:
- We use binary search to determine the maximum possible sum Alice can take. The search space ranges from
0to the total sum of the cake. - For each midpoint
xin the binary search, we check if there is a subarray whose sum is at leastxand after removing this subarray, the remaining parts can providemsubarrays each with a sum ≥v.
- We use binary search to determine the maximum possible sum Alice can take. The search space ranges from
-
Check Function:
- This function iterates through the cake to find if there exists a subarray with sum ≥
xsuch that the remaining parts can satisfy the condition formcreatures. - By using the prefix and suffix arrays, it efficiently checks the validity of each potential subarray.
- This function iterates through the cake to find if there exists a subarray with sum ≥
-
Edge Cases:
- If the total sum of the cake is less than
m*v, it's impossible to make all creatures happy, and the answer is-1. - Otherwise, the binary search helps in finding the optimal solution.
- If the total sum of the cake is less than
Complexity:
- The solution runs in
O(t * n * log(S))time, wheretis the number of test cases,nis the number of sections in each test case, andSis the sum of section values. This is efficient enough given the problem constraints.
Implementation:
Here's the C++ implementation of the solution based on the above reasoning:
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ int n, m; ll v; cin>>n>>m>>v; vector<ll> a(n); for(auto &x:a) cin>>x; ll S=0; for(auto x:a) S +=x; if(S < (ll)m * v){ cout<<-1<<"\n"; continue; } // Compute prefix_count vector<int> prefix_count(n, 0); int count=0; ll sum=0; int start=0; for(int i=0;i<n;i++){ sum +=a[i]; if(sum >=v){ count++; prefix_count[i]=count; sum=0; start=i+1; } else{ prefix_count[i]=count; } } // Compute suffix_count vector<int> suffix_count(n, 0); count=0; sum=0; int end=n-1; for(int i=n-1;i>=0;i--){ sum +=a[i]; if(sum >=v){ count++; suffix_count[i]=count; sum=0; end=i-1; } else{ suffix_count[i]=count; } } // Binary search ll left=0, right=S; ll ans=-1; while(left <= right){ ll mid = left + (right - left)/2; // Check if there exists a subarray with sum >=mid and prefix_count[l-1]+suffix_count[r+1]>=m bool found=false; ll current_sum=0; int start_idx=0; for(int i=0;i<n;i++){ current_sum +=a[i]; while(current_sum >= mid){ int l = start_idx; int r = i; int total_m =0; if(l >0) total_m += prefix_count[l-1]; if(r <n-1) total_m += suffix_count[r+1]; if(total_m >= m){ found=true; break; } current_sum -=a[start_idx]; start_idx++; } if(found) break; } if(found){ ans=mid; left=mid+1; } else{ right=mid-1; } } // Now, check if ans is S - sum_given, but we need to find the maximum Alice's sum // The binary search already gives the maximum Alice's sum where S - Alice_sum can have m subarrays >=v // Thus, ans is the maximum Alice's sum // Output ans // If ans >=0, otherwise -1 if(ans != -1){ cout<<ans<<"\n"; } else{ cout<<-1<<"\n"; } } } -