ARRAYSUB - subarrays
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input
the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line
n < 10^6
k < 10^5
1 <= k <= n
and each element of the array is between 0 and 10^6
(Edited: In fact, n <= 10^5)
Output
print the output array
Example
Input: 9 1 2 3 1 4 5 2 3 6 3 Output: 3 3 4 5 5 5 6
hide comments
Ashish:
2013-12-16 23:37:14
Got TLE with O(nk)... finally AC .. phew!!! |
|
SanchitK:
2013-12-14 10:43:40
getting WA in 5th test case |
|
anonymous:
2013-12-08 15:27:33
o(n) soln runs slower than o(n*k)
|
|
~!(*(@*!@^&:
2013-12-08 04:27:25
There are problems if you read input by a fast in/out procedure. It costs many WAs. Last edit: 2013-12-08 04:59:06 |
|
Shashank Gupta:
2013-11-10 05:48:13
Okay I found an O(n) DP solution but it runs even slower than optimized O(n*k). xD My first O(n*k) solution gave me 0.18 and DP O(n) solution gave me 0.20. (C language) Last edit: 2013-11-10 05:57:14 |
|
Shashank Gupta:
2013-11-10 00:53:18
I solved it but I wonder if there is a faster way than O(n*k)? |
|
Priyanshu Srivastava:
2013-09-02 16:28:29
0.18 s using brute force!! |
|
CoNtRaDiCtIoN:
2013-09-01 13:12:32
thank you garima !!! |
|
Abhimanyu:
2013-08-02 07:13:21
any special test cases please ??? |
|
innovolt:
2013-07-31 13:15:19
simple ques. did it in 0.19 sec no special algo required think simple..... |
Added by: | priyamehtanit |
Date: | 2012-02-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own |