Cod sursa(job #1566884)

Utilizator horatiuchevalHoratiu Cheval horatiucheval Data 12 ianuarie 2016 18:52:25
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;

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

    int sum[50001];
    sum[0] = 0;
    int n, k, x, sc, smax = -2000000000, st, stmax = 1, drmax = 1;
    fin>>n>>k;
    for(int i = 1; i <= k; i++)
    {
        fin>>x;
        sum[i] = sum[i - 1] + x;
    }

    sc = smax = sum[k];
    st = stmax = 1;
    drmax = k;

    for (int i = k + 1; i <= n; i++)
    {
        fin>>x;
        sum[i] = sum[i - 1] + x;
        if(sum[i] - sum[i - k] > sc + x)
        {
            sc = sum[i] - sum[i - k];
            st = i - k + 1;
        }
        else sc += x;

        if(sc > smax)
        {
            smax = sc;
            drmax = i;
            stmax = st;
        }
    }

    fout<<stmax<<" "<<drmax<<" "<<smax;
    fin.close();
    fout.close();
    return 0;
}