Cod sursa(job #841665)

Utilizator assa98Andrei Stanciu assa98 Data 24 decembrie 2012 16:28:32
Problema Divk Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>

int n;
int x;
int v[100100];
int s[500100];

long long sol;
int k,a,b;

int main()
{
    freopen("divk.in","r",stdin);
    freopen("divk.out","w",stdout);
    scanf("%d%d%d%d",&n,&k,&a,&b);

    for(int i=1; i<=a; i++)
    {
        scanf("%d",&x);
        s[i]=(s[i-1]+x)%k;
        //v[s[i]]++;
    }

    if(s[a]==0)
    {
        sol++;
        //printf("%d\n",a);
    }
    for(int i=a+1; i<=b+1; i++)
    {
        scanf("%d",&x);
        s[i]=(s[i-1]+x)%k;
        //v[s[i]]++;
        v[s[i-a]]++;
        if(s[i]==0)
        {
            sol++;
            //printf("%d\n",i);
        }
        if(v[s[i]])
        {
            sol+=v[s[i]];
            //printf("%d\n",i);
        }
    }

    for(int i=b+2; i<=n; i++)
    {
        scanf("%d",&x);
        s[i]=(s[i-1]+x)%k;
        v[s[i-a]]++;
        v[s[i-b]]--;
        if(v[s[i]])
        {
            sol+=v[s[i]];
            //printf("%d\n",i);
        }
    }

    printf("%lld",sol);
    return 0;
}