Cod sursa(job #2632122)

Utilizator sireanu_vladSireanu Vlad sireanu_vlad Data 2 iulie 2020 11:55:38
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

ifstream in("sum2.in");
ofstream out("sum2.out");

int main()
{
    int n, l, u;
    in >> n >> l >> u;
    int s, s1 = 0, v;
    int maxSum = -2147483648;


    deque<int> minS;
    minS.push_back(0);
    deque<int> indS;
    indS.push_back(-1);

    for(int i = 0; i < n; i++)
    {
        in >> v;
        s = s1 + v;
        if(!indS.empty()) if(i - indS.front() > u)
        {
            minS.pop_front();
            indS.pop_front();
        }
        while(minS.size() > 1)
        {
            if(i - indS.at(1) > l)
            {
                minS.pop_front();
                indS.pop_front();
            }
            else
                break;
        }
        if(!minS.empty()) if(s - minS.front() > maxSum && i - indS.front() >= l)
        {
            maxSum = s - minS.front();
            //cout << "\n--maxsum--\n" << i << "\n" << indS.front() << "\n" << maxSum << "\n" << minS.front() << "\n" << s;
        }
        if(minS.empty())
        {
            minS.push_back(s);
            indS.push_back(i);
        }
        else if(minS.back() > s)
        {
            /*while(!minS.empty())
            {
                if(minS.back() > s)
                {
                    minS.pop_back();
                    indS.pop_back();
                }
                else
                    break;
            }*/
            minS.push_back(s);
            indS.push_back(i);
        }
        //cout << "\ni = " << i << "   minS = " << minS.front() << endl;
        s1 = s;
    }

    out << maxSum << endl;

    return 0;
}