Cod sursa(job #2447589)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 13 august 2019 20:15:54
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <iostream>
using namespace std;

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

//size_t is a shorthand for "unsigned int"
//variable{value} is a shorthand for variable = value, but works just at initialization

size_t N, K;

int v[50000 + 1]; //the array where we the given numbers

int sum_current{0}; //the sum of a K length sequence

size_t last;   //the position where our winning sequence ends
size_t first;  //the position where our winning sequence stars

int answer{-2000000000};        //our maximum sum of a sequence with at least K elements
int copy_answer{-2000000000};   //a copy of our answer
                            //we will need it to find the values of "last" and "first"

int sum_max[50000 + 1];  //sum_max[i] = the maximum sum of a contiguous sequence ending at position i
                         //we build this array using Kadane's algorithm



int main()
{
    fin >> N >> K;

    sum_max[0] = -2000000000;

    for(size_t i = 1; i <= N; i++) {
        fin >> v[i];

        sum_max[i] = max(v[i], sum_max[i - 1] + v[i]);
        //Kadane's algorithm
    }

    for(size_t i = 1; i <= K; i++) sum_current += v[i];
    //Sum  of first K numbers

    for(size_t i = K + 1; i <= N; i++){
        sum_current = sum_current + v[i] - v[i - K];
        //we maintain the sum of a contiguous sequence of size K
        //when we add a new element (v[i]) we remove the last one (v[i - K])

        copy_answer = answer;
        answer = max(answer, max(sum_current, sum_current + sum_max[i - K]));
        //we can compare the sum of our K length sequence (sum_current) with our answer
        //but at the same time, we can extend our sequence to a greater one (size greater than K)
        //so if the maximum sum ending at the position we just popped (i - k) improves our sum_current
        //then we choose sum_current + sum_max[i - K] to compare to our answer

        if(copy_answer != answer){
            //in this case we found a new best sequence
            //we update the ending position of our winning sequence
            last = i;
        }

    }

    //we find the starting position of our winning sequence
    copy_answer = answer;

    //we eliminate a element from our winning sum until it becomes null
    for(first = last; copy_answer != 0; first--){
        copy_answer -= v[first];
    }

    first++;    //we need to increase it by 1 because "for" above
                //it ends when our winning sum becomes null but still decreases "first" one more time

    fout << first << " " << last << " " <<answer;
    //Kisses :** from Ursu
}