Solução de Roger Benet, comentário de João Guilherme
Para ver o problema original, clique aqui.
O problema é bem simples, precisamos apenas manter a soma de todos os custos até nossa casa i. Se a soma for maior do que a quantia que Prateek quer gastar podemos remover os primeiro custos, (assim guardamos a soma de j até i, em vez de 0 até i) até que a soma fique menor que o valor que Prateek quer gastar. Se nesse processo de remover os primeiro valores a soma ficar igual a x, guardamos essa informação num boleano.
Quando terminarmos de processar, checamos se nosso boleano está verdadeiro (existe uma soma igual a x) ou falso e imprimos a resposta de acordo.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| ll vet[1000010], x, sm; | |
| int t,n,j; | |
| bool ok; | |
| int main(){ | |
| scanf("%d", &t); | |
| while(t--){ | |
| scanf("%d %lld", &n, &x); | |
| ok = false; | |
| j = 0; | |
| sm = 0LL; | |
| for(int i = 0; i < n; i++){ | |
| scanf("%lld", &vet[i]); | |
| sm += vet[i]; | |
| while(sm >= x and j <= i){ | |
| if(sm == x)ok = true; | |
| sm -= vet[j++]; | |
| } | |
| } | |
| if(ok)printf("YES\n"); | |
| else printf("NO\n"); | |
| } | |
| return 0; | |
| } |