Cod sursa(job #847703)

Utilizator dumitrascumihaiDumitrascu Mihai dumitrascumihai Data 4 ianuarie 2013 13:20:33
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
/*#include<fstream>

using namespace std;

int main()
{
    int n,a[1000001],i,j,s=0;
    ifstream f("fractii.in");//fractii
    ofstream g("fractii.out");

    f>>n;
    for(i=2;i<=n;i++)
    {
        a[i]=i-1;
    }

    for(i=2;i<=n;i++)
    {
        s+=a[i];
        for(j=i+i;j<=n;j+=i)
        {
            a[j]-=a[i];
        }
    }

    g<<2*s+1;
}
*/
/*
#include <fstream>

using namespace std;

const int a=2000000000;
int main()
{
    int v[1000002], G, W, vmin=a,eg[10002],cg[10002];
	int i, j;
	ifstream f("fractii.in"); // energii
	ofstream g("fractii.out");
	f>>G>>W;
	for(i=1;i<=G;i++)
		f>>eg[i]>>cg[i];
	for(int i=1;i<1000002;i++)
		v[i]=a;
	v[0]=0;
	for(i=1;i<=G;i++)
		for(j=W;j>=0;j--)
			if(v[j]!=a && v[j+eg[i]]>v[j]+cg[i])
				v[j+eg[i]]=v[j]+cg[i];
	for(i=W;i<1000001;i++)
		if(v[i]<vmin)
			vmin=v[i];
	if(vmin!=a)
		g<<vmin;
	else
		g<<"-1";
	return 0;
}
*/
/*
#include<fstream>

using namespace std;

int n,m,maxim,x[17][17],v[17],j,s1,s2;

ofstream g("fractii.out"); //flip

void verif()
{int i;
     s2=0;
     for(i=1;i<=n;i++)
        {
            s1=0;
            for(j=1;j<=m;j++)
            {
                s1+=x[i][j]*v[j];
            }

            if(s1<0) s2+=s1*-1;
            else
                s2+=s1;
        }

        if(s2>maxim)
        {
            maxim=s2;
        }
}
void back(int k)
{int i;
    if(k>m)
    {
        verif();
    }
    else
    {
        for(i=-1;i<=1;i+=2)
        {
            v[k] = i;
            back(k+1);
        }
    }
}

int main()
{int i;
    ifstream f("fractii.in"); //flip
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>x[i][j];
    back(1);
    g<<maxim;
    return 0;
}
*/
#include <fstream>

using namespace std;

int main()
{
    int n,x[500001],maxim,k,i,j,imax;
    long long smax=0;
    ifstream f("deque.in");
    ofstream g("deque.out");
    f>>n>>k;
    for(i=1;i<=n;i++)
    {
        f>>x[i];
    }
    maxim=10000000;
    for(i=1;i<=k;i++)
    {
        if(x[i]<=maxim)

        {
            maxim=x[i];
            imax=i;
        }
    }
    smax+=maxim;
    for(i=k+1;i<=n;i++)
    {
        if(x[i]<=maxim)
        {
            maxim=x[i];
            imax=i;
        }
        else if(imax<=i-k)
            {
                maxim=10000000;
                for(j=i-k+1;j<=i;j++)
                {
                    if(x[j]<maxim){ maxim=x[j]; imax=j;}
                }
            }
        smax+=maxim;
    }
    g<<smax;
    return 0;
}