Cod sursa(job #208718)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 17 septembrie 2008 21:51:05
Problema Divk Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <math.h>

#define max 500001

int main() {
	freopen("divk.in", "r", stdin);
	freopen("divk.out", "w", stdout);
	long sol = 0;	
	long n, a, b, k, x, s, i;
	long v[max];
	long ww[max], j;
	//long sel[max / 4];

	scanf("%ld %ld %ld %ld", &n, &k, &a, &b);
	
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &x);
		v[i] = x % k;
	}
	
	for (i = 1; i <= a - 1; ++i) { 
		s += v[i];
	}
	
	long rrr, rrq;
	
	for (i = 1; i <= n; ++i) {
		ww[i] = (ww[i - 1] + v[i]) % k;
	}
	
	sol = 0;
	for (i = a; i <= n - b; ++i) {
		for (j = i; j <= n + 1; ++j) { // && j <= n + 1
			if( (ww[j - 1] - ww[i - 1] + k) % k == 0) { 
				++sol;
			}
		}
	}

/*	for (i = 1; i <= n; ++i) {
		for (j = i + a; j <= i + b && j <= n + 1; ++j) { // && j <= n + 1
			if( (ww[j - 1] - ww[i - 1] + k) % k == 0) { 
				++sol;
			}
		}
	}*/
	
	rrr = sol / 1000000;
	rrq = sol % 1000000;
	if (rrr > 0) {
		printf("%ld%ld\n", rrr, rrq);
	} else {
		printf("%ld\n", rrq);
	}
	return 0;
}