Sanduíche

sanduiche.cpp

// Sanduíche - F1P2 - OBI 2016
// Rogério Júnior
// Complexidade: O(n)

#include <cstdio>

#define MAXN 1000100

int n, d, v[2*MAXN], prefix[2*MAXN], resp, fim;

int main(){
	
	scanf("%d %d", &n, &d);
	
	// leio os tamanho dos pedaços
	for(int i=1;i<=n;i++){
	
		scanf("%d", &v[i]);
		
		// sempre lembrando de duplicar o sanduíche
		v[i+n]=v[i];
	}
	
	// precalculo as somas de todos os prefixos
	for(int i=1;i<=2*n;i++) prefix[i]=v[i]+prefix[i-1];
	
	// se o tamanho total do sanduíche for menor que d
	if(prefix[n]<d){
		
		// não há solução
		printf("0\n");
		return 0;
	}
	
	// caso contrário, vamos procurar os intervalos com soma D
	
	// o fim de cada intervalo começa como 1
	fim=1;
	
	// e para cada início
	for(int ini=1;ini<=n;ini++){
		
		// incremento o fim enquanto puder
		while(fim<2*n && prefix[fim+1]-prefix[ini-1]<=d) fim++;
		
		// e testo se a soma do intervalo é D
		if(prefix[fim]-prefix[ini-1]==d) resp++;
	}
	
	// por fim, imprimo o valor salvo em resp
	printf("%d\n", resp);
	
	return 0;
}