Cod sursa(job #1640785)

Utilizator cristina_borzaCristina Borza cristina_borza Data 8 martie 2016 19:22:02
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <cstdio>

#define NMAX 50005
#define INF 50005

using namespace std;

int n , k , sol , sum , ps , pf , s , f;
int a[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 = 1;
    for(int i = 1 ; i <= n ; ++i) {
        if(sum + a[i] >= a[i]) {
            sum += a[i];
            ++pf;
        }

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

        if(sol < sum && pf - ps + 1 >= k) {
            sol = sum;
            s = ps;
            f = pf;
        }
    }

    if(sol < sum && pf - ps + 1 >= k) {
        sol = sum;
        s = ps;
        f = pf;
    }

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