Pagini recente » Cod sursa (job #907503) | Cod sursa (job #2037070) | Cod sursa (job #1312562) | Cod sursa (job #1335386) | Cod sursa (job #2605544)
#include <cstdio>
#include <climits>
using namespace std;
const int NMAX = 50000;
const long long NINF = LONG_LONG_MIN;
int d[NMAX + 5][20] , log[NMAX + 5] , n;
long long sp[NMAX + 5];
void rmq()
{
int i , j;
for(i = 1 ; i <= n ; i ++)
d[i][0] = i;
for(j = 1 ; (1 << j) <= n ; j ++)
for(i = 1 ; i + (1 << j) - 1 <= n ; i ++)
if(sp[d[i][j - 1]] >= sp[d[i + (1 << (j - 1))][j - 1]])
d[i][j] = d[i][j - 1];
else
d[i][j] = d[i + (1 << (j - 1))][j - 1];
}
int query(int x , int y)
{
int j = log[y - x + 1] - 1;
if(sp[d[x][j]] >= sp[d[y - (1 << j) + 1][j]])
return d[x][j];
return d[y - (1 << j) + 1][j];
}
int main()
{
freopen("secv2.in" , "r" , stdin);
freopen("secv2.out" , "w" , stdout);
int i , k , x , st , dr , poz;
long long vmax;
scanf("%d%d" , &n , &k);
for(i = 1 ; i <= n ; i ++)
{
scanf("%d" , &x);
sp[i] = sp[i - 1] + 1LL * x;
log[i] = log[i - 1];
if((i & (i - 1)) == 0)
log[i] ++;
}
rmq();
vmax = NINF;
for(i = 1 ; i <= n - k + 1; i ++)
{
poz = query(i + k - 1 , n);
if(sp[poz] - sp[i - 1] > vmax)
{
vmax = sp[poz] - sp[i - 1];
st = i;
dr = poz;
}
}
printf("%d %d %lld\n" , st , dr , vmax);
return 0;
}