Cod sursa(job #1655185)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 17 martie 2016 20:17:01
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define NM 50005

using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

int n, k, i, x, bmin[NM], st[NM], bt[NM], fi, prim, maxim;

int main()
{
    fin>>n>>k;
    for (i=1; i<k; i++)
    {
        fin>>x;
        bmin[i]=bmin[i-1]+x;
        if (bt[i-1]<bmin[i])
        {
            bt[i]=bt[i-1];
            st[i]=st[i-1];
        }
        else
        {
            bt[i]=bmin[i];
            st[i]=i;
        }
    }
    maxim=-1000000000;
    for (i=k; i<=n; i++)
    {
        fin>>x;
        bmin[i]=bmin[i-1]+x;
        if (bt[i-1]<bmin[i])
        {
            bt[i]=bt[i-1];
            st[i]=st[i-1];
        }
        else
        {
            bt[i]=bmin[i];
            st[i]=i;
        }
        if (bmin[i]-bt[i-k]>maxim)
        {
            maxim=bmin[i]-bt[i-k];
            fi=i;
            prim=st[i-k]+1;
        }
    }
    fout<<prim<<" "<<fi<<" "<<maxim;
    return 0;
}