Cod sursa(job #1529688)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 21 noiembrie 2015 10:33:49
Problema Secventa 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
#define DM 50007
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");

int N,K,st,dr,Sol=-40000,Sk;
int X[DM],DP[DM];

void Solve()
{
    int i;

    st=1;   dr=K;

    for(i=1;i<=K;++i)   Sk+=X[i];

    DP[K]=Sk;

    if(Sk>Sol)  Sol=Sk;

    for(i=K+1;i<=N;++i)
    {
        Sk=Sk+X[i]-X[i-K];

        if(Sk>=(DP[i-1]+X[i]))   {  st++;   DP[i]=Sk;   }
        else    DP[i]=DP[i-1]+X[i];

        if(DP[i]>Sol)
        {
            Sol=DP[i];
            dr=i;
        }
    }
}

int main()
{
    fin>>N>>K;

    for(int i=1;i<=N;++i)
    {
        fin>>X[i];
        if(X[i]>Sol)    Sol=X[i];
    }

    Solve();

    fout<<st<<" "<<dr<<" "<<Sol<<"\n";

    fin.close();
    fout.close();
    return 0;
}