Pagini recente » Cod sursa (job #620832) | Cod sursa (job #2810174) | Cod sursa (job #2631430) | Cod sursa (job #332634) | Cod sursa (job #894939)
Cod sursa(job #894939)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const char infile [] ="secv2.in";
const char outfile [] = "secv2.out";
#define MAXN 50002
int A[MAXN];
int N;
int K;
int ResultStart = 0;
int ResultEnd = 0;
int Result = 0;
void citire()
{
fstream fin(infile, ios::in);
fin >> N;
fin >> K;
for(int i = 0; i < N; i++)
{
fin >> A[i];
}
fin.close();
}
void afisare()
{
fstream fout(outfile, ios::out);
fout << ResultStart << " ";
fout << ResultEnd << " ";
fout << Result << "\n";
fout.close();
}
void solve()
{
deque<int> removables;
int removableSum = 0;
deque<int> deck;
int best = 0;
int bStart = 0;
int bEnd = K-1;
int start = 0;
int end = K-1;
int current = 0;
for(int i = 0; i < K; i++)
{
deck.push_back(A[i]);
current += A[i];
}
best = current;
for(int i = K; i < N; i++)
{
int max1 = current + A[i];
int max2 = current + A[i] - A[start];
current = max(max1, max2);
if(current == max2)
{
deck.push_back(A[i]);
deck.pop_front();
end++;
start++;
}
else
{
removables.push_back(deck.front());
removableSum += deck.front();
deck.pop_front();
deck.push_back(A[i]);
end++;
}
while(removables.size() > 0 && removableSum < 0)
{
start++;
removableSum -= removables.front();
current -= removables.front();
removables.pop_front();
}
if(current > best)
{
best = current;
bStart = start;
bEnd = end;
}
}
Result = best;
ResultStart = bStart + 1;
ResultEnd = bEnd + 1;
}
int main()
{
citire();
solve();
afisare();
}