Cod sursa(job #1769888)

Utilizator lucametehauDart Monkey lucametehau Data 3 octombrie 2016 12:29:35
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;
ifstream cin("secv2.in");
ofstream cout("secv2.out");
long long s[50005],m[50005],v[50005],w[50005];
int main()
{
    long long n,i,k,st,dr,smx=-5000000;
    cin>>n>>k;
    for(i=1;i<=n;i++)
        cin>>v[i];
    s[1]=v[1];
    w[1]=w[0]=1;
    for(i=2;i<=n;i++)
    {
        if(s[i-1]>=0)
        {
            s[i]=s[i-1]+v[i];
            w[i]=w[i-1];
        }
        else
        {
            s[i]=v[i];
            w[i]=i;
        }
    }
    for(i=1;i<=k;i++)
        m[1]+=v[i];
    for(i=k+1;i<=n;i++)
        m[i-k+1]=m[i-k]+v[i]-v[i-k];
    for(i=1;i<=n-k+1;i++)
    {
        if(s[i-1]>=0)
        {
            m[i]+=s[i-1];
            w[i]=w[i-1];
        }
        if(m[i]>smx)
        {
            smx=m[i];
            st=w[i];
            dr=i+k-1;
        }
    }
    cout<<st<<' '<<dr<<' '<<smx;
    return 0;
}