Cod sursa(job #1004482)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 2 octombrie 2013 20:28:17
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>

#define maxn 50001

using namespace std;

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

int v[maxn],bst[maxn],sum[maxn],s,st,lst,n,k,stcurrent,maxv;

int main()
{
    fin>>n>>k;

    for (int i=1; i<=n; ++i)
        fin>>v[i];

    int i;
    for (i=1; i<=n; ++i)
    {
        sum[i]=sum[i-1]+v[i];
    }

    stcurrent = 1;

    maxv = sum[k];
    st = 1;
    lst = k;

    for (i=k+1; i<=n; ++i)
    {
        if (s + v[i] > sum[i] - sum[i-k])
           s += v[i];
        else
        {
            s = sum[i] - sum[i-k];
            stcurrent = i-k+1;
        }

        if (s > maxv)
        {
            maxv = s;
            st = stcurrent;
            lst = i;
        }
    }

    fout<<st<<" "<<lst<<" "<<maxv;
}