Cod sursa(job #1586000)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 31 ianuarie 2016 17:50:37
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int dmax = 50000;

int a[dmax + 1];

int best[dmax + 1]; //best[i] == SUMA MAXIMA A UNEI SUBSECVENTE CE SE TERMINA PE POZITIA i

int NR[dmax + 1]; //NR[i] == LUNGIMEA UNEI SSM CE SE TERMINA PE POZITIA i

int N, K;

int main()
{
    int i, best_Sum = 0, p, u;
    bool GASIT = false;

    in >> N >> K;

    for(i = 1; i <= N; i++) in >> a[i];

    for(i = 1; i <= N; i++)
    {
        best[i] = a[i];

        NR[i] = 1;

        if(best[i] < best[i - 1] + a[i])
        {
            best[i] = best[i - 1] + a[i];

            NR[i] = NR[i - 1] + 1;
        }
    }

    for(i = 1; i <= K; i++) best_Sum += a[i];
    u = K;

    for(i = 1; i <= N; i++)
        if(NR[i] >= K)
        {
            if(!GASIT)
            {
                GASIT = true;
                best_Sum = best[i];
                u = i;
            }
            else if(best_Sum < best[i])
            {
                best_Sum = best[i];
                u = i;
            }
        }

    int S = 0;

    for(i = u; i >= 1; i--)
    {
        S += a[i];

        if(S == best_Sum) p = i;
    }

    out << p << " " << u << " " << best_Sum;

    return 0;
}