Cod sursa(job #2033818)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 7 octombrie 2017 11:00:24
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#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("secventa2.in", "r", stdin);
    freopen("secventa2.out", "w", stdout);

    solve();

    return 0;
}