Pagini recente » Cod sursa (job #462566) | Cod sursa (job #1781721) | Cod sursa (job #2324333) | Cod sursa (job #53330) | Cod sursa (job #2033820)
#include <cstdio>
#include <deque>
using namespace std;
int n, k;
int sir[5000005];
int valMin, pos;
void solve(){
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++){
scanf("%d", &sir[i]);
if(i != 0){
sir[i] += sir[i - 1];
}
}
deque<int> dqmin;
deque<int> dqmax;
int st, dr, val;
st = 0;
dr = k - 1;
val = 0;
for(int i = 0; i < k; i++){
while(dqmin.size() > 0 && sir[dqmin.back()] > sir[i]){
dqmin.pop_back();
}
dqmin.push_back(i);
while(dqmax.size() > 0 && sir[dqmax.back()] < sir[i]){
dqmax.pop_back();
}
dqmax.push_back(i);
}
val = sir[dqmax.front()] - sir[dqmin.front()];
for(int i = k; i < n; i++){
while(dqmin.size() > 0 && sir[dqmin.back()] > sir[i]){
dqmin.pop_back();
}
dqmin.push_back(i);
while(dqmax.size() > 0 && sir[dqmax.back()] < sir[i]){
dqmax.pop_back();
}
dqmax.push_back(i);
int valx = sir[dqmax.front()] - sir[dqmin.front()];
if(valx > val){
val = valx;
st = dqmin.front();
dr = dqmax.front();
}
}
printf("%d %d %d", st + 1 + 1, dr + 1, val);
}
int main() {
freopen("secv2.in", "r", stdin);
freopen("secv2.out", "w", stdout);
solve();
return 0;
}