Pagini recente » Cod sursa (job #2512514) | Cod sursa (job #2386929) | Cod sursa (job #1450058) | Cod sursa (job #2920335) | Cod sursa (job #2447588)
#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{INT_MIN}; //our maximum sum of a sequence with at least K elements
int copy_answer{INT_MIN}; //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] = INT_MIN;
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
}