Pagini recente » Cod sursa (job #2100581) | Cod sursa (job #2393094) | Cod sursa (job #268413) | Cod sursa (job #3168569) | Cod sursa (job #1236253)
#include <cstdio>
#define Nmax 50005
using namespace std;
int N,K;
int v[Nmax];
int spart[Nmax];
int DP[Nmax];
struct poz{
int a,b;
poz(){
a = b = 0;
}
poz(int a,int b){
this->a = a;
this->b = b;
}
}p[Nmax];
int main()
{
freopen("secv2.in","r",stdin);
freopen("secv2.out","w",stdout);
scanf("%d%d",&N,&K);
for(int i = 1; i <= N; ++i)
{
scanf("%d",&v[i]);
spart[i] = spart[i-1] + v[i];
}
p[K] = poz(1,K);
DP[K] = spart[K];
int best = DP[K], besta = 1,bestb = K;
for(int i = K + 1; i <= N; ++i)
{
if(spart[i] - spart[i-K] > DP[i-1] + v[i])
{
DP[i] = spart[i] - spart[i-K];
p[i] = poz(i-K+1,i);
}
else
{
DP[i] = DP[i-1] + v[i];
p[i] = p[i-1];
p[i].b++;
}
if(DP[i] > best)
{
best = DP[i];
besta = p[i].a;
bestb = p[i].b;
}
}
printf("%d %d %d\n",besta, bestb, best);
return 0;
}