All submissions for this problem are available.
You are participating in The Quick-Math Quiz 2015 and, fortunately enough, have managed to qualify for the final round. But the final round ain't a piece of cake. The quiz master has revealed the final problem which reads :
- You are given an array of integers of size N and an integer K.
- Then you are asked Q number of questions.
- Each question has two integers S and X.
- You need to tell if the sum of any S consecutive subarrays of size K sum up to X or not.
The contestant who answers first, wins.
The first line of the input contains two integers N and K denoting the size of array and size of each subarray respectively.
The next line contains N spaced integers representing the array.
The next line contains an integer Q representing the number of questions.
Q lines follow.
Each question has two spaced integers S and X representing the number of consecutive subarrays and the sum of consecutive subarrays.
For each question, print "YES" or "NO" (without the quotations) accordingly to the question.
- 1 ≤ S+K-1 ≤ N ≤ 105
- 1 ≤ Q ≤ 103
- 1 ≤ Value of an integer in array ≤ 100
- Subtask #1[20 points] : 1 ≤ Q ≤ 100 & 1 ≤ S+K-1 ≤ N ≤ 100
- Subtask #2[80 points] : Original constraints
Input: 5 2 1 2 3 4 5 4
3 21 Output: YES YES
Example case 1. (2 + 3) = 5 by considering 1 subarray starting from 2nd position.
Example case 2. (2 + 3) + (3 + 4) = 12 by considering 2 subarrays with the first subarray starting from 2nd position.
Example case 3. The sum any three consectuive subarrays of size 2 is not equal to 14 as the only two possibilities are 15 and 21
Example case 4. (2 + 3) + (3 + 4) + (4 + 5) = 12 by considering 3 subarrays with the first subarray starting from 2nd position.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.