Pagini recente » Cod sursa (job #41732) | Cod sursa (job #412189) | Cod sursa (job #1751732) | Cod sursa (job #274539) | Cod sursa (job #274536)
Cod sursa(job #274536)
#include <fstream>
#include <iostream>
using namespace std;
int n, k;
int s[60000],best[60000],sum[60000];
#define sFIN "secv2.in"
#define sFOUT "secv2.out"
#define FOR(i,b,c) for (int i = (b); i<(c); i++)
#define abs(a) ((a<0)?(-1*a):(a))
int interval(int a, int b){
if ( a == 0)
return sum[b];
return (sum[b]-sum[a])+s[a];
}
void mainLoop(){
ifstream fin(sFIN);
ofstream fout(sFOUT);
fin >> n >> k;
FOR(i,0,n){
fin >> s[i];
sum[i] = (i==0?s[i]:sum[i-1]+s[i]);
}
long a=0, b=k-1;
long m = 0;
best[0]=0;
FOR(i,1,n){
if (sum[i-1]<-sum[best[i-1]])
best[i] = i-1;
else
best[i] = best[i-1];
}
FOR(i,k,n)
if (interval(best[i-(k-1)]+1,i) > interval(a,b))
a = best[i-(k-1)]+1, b = i;
cout << a+1 << " " << b+1 << " " << interval(a,b);
fout.close(), fin.close();
}
int main() {
mainLoop();
return 0;
}