Pagini recente » Cod sursa (job #1362434) | Cod sursa (job #1929222) | Cod sursa (job #2539821) | Cod sursa (job #653627) | Cod sursa (job #1622088)
#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];
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] = S[k];
STR[k] = 1;
for(i=k+1; i<=n; i++){
sumak = S[i] - S[i - k];
if(DPT[i - k] > 0){
DP[i] = DPT[i-k] + sumak;
STR[i] = ST[i-k];
}
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;
}