Pagini recente » Cod sursa (job #711063) | Cod sursa (job #1219686) | Cod sursa (job #2868105) | Cod sursa (job #1278933) | Cod sursa (job #825114)
Cod sursa(job #825114)
#include <fstream>
using namespace std;
#define INF 0x3f3f3f3f
ifstream is ("secv2.in");
ofstream os ("secv2.out");
long i,n,k;
long T[50005], S[50005], D[50005];
long maxim=-INF, front, back, st, dr;
int main()
{
is >> n >> k;
for ( i=1; i<=n; i++ )
{
is >> T[i];
S[i]=S[i-1]+T[i];
}
back=0;
front=1;
for ( i=k; i<=n; i++ )
{
while ( S[i]> S[ D[back] ] && back>0 )
back--;
back++;
D[back]=i;
}
for ( i=1; i<=n-k+1; i++ )
{
if ( D[front] < i+k-1 )
front++;
if ( maxim < S[D[front]]-S[i-1] )
{
maxim=S[D[front]]-S[i-1];
st=i;
dr=D[front];
}
}
os << st << " " << dr << " " << maxim;
return 0;
}