Pagini recente » Istoria paginii runda/saptamana_altfel_6d/clasament | Cod sursa (job #1256302) | Istoria paginii runda/okfrt | Istoria paginii runda/00001/clasament | Cod sursa (job #687519)
Cod sursa(job #687519)
#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;
const int knmax = 50005;
int n, k, list[knmax], dfront[knmax], partialsum[knmax], indfront[knmax];
int sol=-900001, xsol, ysol;
void read(){
assert(freopen("secv2.in","r",stdin) != NULL);
scanf("%d%d",&n ,&k);
int i;
for(i = 1; i <=n; ++i)
scanf("%d",&list[i]);
}
/*void get_dback(){
int i;
for(i = n; i > 0; --i)
if(list[i] + dback[i + 1] > list[i]){
indback[i] = indback[i + 1];
dback[i] = dback[i + 1] + list[i];
}
else {
indback[i] = i;
dback[i] = list[i];
}
}*/
void get_dfront(){
int i;
for(i = 1; i <= n; ++i)
if(list[i] + dfront[i - 1] > list[i]){
indfront[i] = indfront[i - 1];
dfront[i] = dfront[i - 1] + list[i];
}
else {
indfront[i] = i;
dfront[i] = list[i];
}
}
void get_partialsum(){
int i;
for(i = 1; i <= n; ++i)
partialsum[i] = partialsum[i - 1] + list[i];
}
void query(int left, int right){
int localsol = partialsum[right] - partialsum[left - 1];
if(dfront[left - 1] > 0){
localsol = localsol + dfront[left - 1];
left = indfront[left - 1];
}
if(localsol > sol){
sol = localsol;
xsol = left;
ysol = right;
}
}
void solve(){
//get_dback();
get_dfront();
get_partialsum();
int i;
for(i = k;i <= n; ++i)
query(i - k + 1 , i);
}
void write(){
assert(freopen("secv2.out","w",stdout) != NULL);
printf("%d %d %d",xsol ,ysol ,sol);
}
int main(){
read();
solve();
write();
return 0;
}