This was a great problem. I took the the deque approach after referring to this link. With some minor changes, and a check for k>n, it worked. For some reason though, my sub-task testcases were failing with the deque, so I had to use brute force for n<1000. Here’s my solution.
@devilhector use iterative segment trees recursive calls on such high constraints is not gonna work.
I’ve used the same approach you can view my solution CodeChef: Practical coding for everyone
https://www.codechef.com/viewsolution/13559652
solve this using priority queue and simple obserations
Thanks
Please check this solution, it doesn’t give the required answer on running!
Used the recursive Segment trees!
I solved this problem by precalculating all the possible answer as there cannot be more than N different answers.
here is my solution.
Any solution using deque??Please post!!!
I did this Question using sliding windows by precompute values and deque to get the maximum value
O(n) solution can be done without deques, using frequency table to get the max. Since values are 0 and 1 only, the max value changes by at most 1.
Here is my solution: CodeChef: Practical coding for everyone as same as author solution but I don’t know why my solution got wrong. Please tell me why I got wrong. Thank you.
One question guys!
Is the complexity O(n) for the entire subtask or O(n) for each querie?
Can someone tell me whats wrong with my code. I would be very greatful.
Submission : CodeChef: Practical coding for everyone
This Solution is giving TLE. I have used Segment Tree/ Range Maximum Query. Please share your insight.
A deque approach with window sliding and taking care of k>n condition and array sizes declaration gives an AC.
here is my easy to understand solution easy solution
i am using segment trees as said above . i am getting WA. please help me
can anyone explain this part
else the answer is the maximum sum we can obtain by starting the window from 1 to (n−k+1).
using namespace std;
include
define _ iosbase::syncwith_stdio(false);cin.tie(NULL);
define D(x) cout<< #x " = "<<(x)<<endl
int main() { _
int n;cin>>n;
int acum = 0;
int ans = 0;
int t;
for (int i = 0; i < n; ++i) {
cin>>t;
if (t == 0) {
ans = max(ans, acum);
acum = 0;
} else {
acum++;
}
}
ans = max(ans, acum);
cout<<ans<<endl;
return 0;
}