Cod sursa(job #1640889)

Utilizator cristina_borzaCristina Borza cristina_borza Data 8 martie 2016 19:47:37
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <cstdio>

#define NMAX 50005
#define INF 5000005

using namespace std;

int n , k , sol , sum , ps[NMAX] , pf[NMAX] , s , f;
int a[NMAX] , ssm[NMAX] , sm[NMAX];

void read(int &x) {
    int sign = 1;
    char ch;
    x = 0;

    while(!isdigit(ch = getchar())) {
        if(ch == '-') {
            sign = -1;
        }

        else {
            sign = 1;
        }
    }

    do {
        x = x * 10 + ch - '0';
    }while(isdigit(ch = getchar()));
    x *= sign;
}

int main() {
    freopen("secv2.in" , "r" , stdin);
    freopen("secv2.out" , "w" , stdout);

    read(n) , read(k);
    for(int i = 1 ; i <= n ; ++i) {
        read(a[i]);
    }

    sum = -INF;
    ps[0] = 1;
    for(int i = 1 ; i <= n ; ++i) {
        pf[i] = pf[i - 1];
        ps[i] = ps[i - 1];

        if(sum + a[i] >= a[i]) {
            sum += a[i];
            ++pf[i];
        }

        else {
            sum = a[i];
            ps[i] = pf[i] = i;
        }

        ssm[i] = sum;
    }

    for(int i = 1 ; i <= n ; ++i) {
        sm[i] = sm[i - 1] + a[i];
    }

    sol = sm[k];
    s = 1;
    f = k;

    for(int i = k + 1 ; i <= n ; ++i) {
        int qq = sm[i] - sm[i - k + 1] + ssm[i - k + 1];
        if(qq > sol) {
            sol = qq;
            s = ps[i - k + 1];
            f = i;
        }
    }

    printf("%d %d %d" , s , f , sol);
    return 0;
}