Cod sursa(job #1121898)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 25 februarie 2014 14:42:54
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
/// Craciun Catalin
///  Secv2
///   Programare dinamica
#include <fstream>
#include <iostream>

#define NMax 50005

using namespace std;

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

unsigned int n,k;
int A[NMax];
long long Best[NMax];
int st, dr, auxSt;
long long bestSum;

void programareDinamica()
{
    Best[1]=A[1];
    bestSum=A[1];
    st=1; dr=1;
    for (unsigned int i=2;i<=n;i++)
    {
        Best[i]=A[i];
        if (Best[i-1]+A[i]>Best[i])
            Best[i]=Best[i-1]+A[i];
        else
            auxSt=i;

        if (bestSum<Best[i] && i>=k)
        {
            bestSum=Best[i];
            st=auxSt;
            dr=i;
        }
    }

    if (k==n)
    {
        bestSum=0;
        for (unsigned int i=1;i<=n;i++)
            bestSum+=A[i];

        g<<1<<' '<<n<<' '<<bestSum<<'\n';
    }
    else
        g<<st<<' '<<dr<<' '<<bestSum<<'\n';
    g.close();
}

void citire()
{
    f>>n>>k;
    for (unsigned int i=1;i<=n;i++)
        f>>A[i];

    f.close();
}

int main()
{
    citire();
    programareDinamica();

    return 0;
}