Cod sursa(job #2359740)

Utilizator FrostfireMagirescu Tudor Frostfire Data 1 martie 2019 09:12:16
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int n, S[50100], Deque1[50100], Deque2[50100], dr1, dr2, k, p1, p2;
long long sol;

int main()
{
    f >> n >> k;
    for(int i=1; i<=n; i++)
    {
        int x;
        f >> x;
        S[i] = S[i-1] + x;
    }

    dr1 = dr2 = 0;
    for(int i=1; i<=n; i++)
    {
        while(dr1 >= 1 && S[i] <= S[Deque1[dr1]]) dr1--;
        while(dr2 >= 1 && S[i] >= S[Deque2[dr2]]) dr2--;
        Deque1[++dr1] = i;
        Deque2[++dr2] = i;
        if(abs(Deque1[1] - Deque2[1]) >= k)
        {
            long long val = S[Deque2[1]] - S[Deque1[1]];
            if(val > sol)
            {
                p1 = Deque1[1] + 1;
                p2 = Deque2[1];
                sol = val;
            }
        }
    }
    g << p1 << ' ' << p2 << ' ' << sol << '\n';
    return 0;
}