Cod sursa(job #786667)

Utilizator RadulescuSerbanRadulescu Serban RadulescuSerban Data 11 septembrie 2012 18:36:50
Problema Secventa 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>

using namespace std;

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

int v[50000],sum[50000];

const int INF = 2000000000;

int main()
{
    int n,k,i,j,s,smax=-INF,st,dr;
    in >> n >> k;
    for(i=0 ; i<n ; i++)
        in >> v[i];
    s=0;
    for(i = 1 ; i < n ; i++)
        sum[i] = v[i] + sum[i-1];
    j = 0;
    s = smax = sum[k-1];
    j = st = 0;
    dr = k - 1;
    for(i = k ; i < n ; i++)
    {
        if(sum[i] - sum[i-k] > s + v[i])
        {
            s = sum[i] - sum[i-k];
            j = i - k + 1;
        }
        else
            s += v[i];
        if(s > smax)
        {
            smax = s;
            st = j;
            dr = i;
        }
    }
    out << st+1 <<" "<< dr+1 << " " << smax << "\n";
    return 0;
}