Pagini recente » Cod sursa (job #1893857) | Cod sursa (job #2918891) | Cod sursa (job #1621826) | Cod sursa (job #1632) | Cod sursa (job #1622014)
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int V[50005], DP[50005], ST[50005], DPT[50005], STR[50005], S[50005];
priority_queue <pair <int, int> > PQ;
int n, k;
int const oo = 2000000000;
void citire()
{
int i;
f>>n>>k;
for(i=1; i<=n; i++)
f>>V[i];
}
void rez()
{
int i, maxi = -oo, ind, sumak;
for(i=1; i<=n; i++){
S[i] = S[i-1] + V[i];
if(DPT[i-1] > 0){
DPT[i] = DPT[i-1] + V[i];
ST[i] = ST[i-1];
}
else{
DPT[i] = V[i];
ST[i] = i;
}
}
DP[k] = DPT[k];
for(i=k+1; i<=n; i++){
sumak = S[i] - S[i - k];
PQ.push(make_pair(DPT[i - k], ST[i - k]));
if(PQ.top().first > 0){
DP[i] = PQ.top().first + sumak;
STR[i] = PQ.top().second;
}
else{
DP[i] = sumak;
STR[i] = i - k + 1;
}
}
for(i = k; i<=n; i++)
if(DP[i] > maxi){
maxi = DP[i];
ind = i;
}
g<<STR[ind]<<" "<<ind<<" "<<maxi<<"\n";
}
int main()
{
citire();
rez();
return 0;
}