Cod sursa(job #687519)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 22 februarie 2012 15:37:44
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#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;
}