Cod sursa(job #3149048)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 5 septembrie 2023 20:59:57
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

int n, k;
vector <int> v;
deque <int> maxSum;

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    cin >> n >> k;
    v.resize(n + 1);

    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
        v[i] += v[i - 1];
    }

    for(int i = 1; i <= k; i ++)
    {
        while(!maxSum.empty()  &&  v[i] > maxSum.back())
            maxSum.pop_back();
        maxSum.push_back(v[i]);
    }

    int minSum = 0, index = 0, st = 1, dr = k, ans = maxSum.front();

    for(int i = k + 1; i <= n; i ++)
    {
        if(v[i - k] < minSum)
        {
            minSum = v[i - k];
            index = i - k;
        }

        if(!maxSum.empty()  &&  v[i - k] == maxSum.front())
            maxSum.pop_front();
        while(!maxSum.empty()  &&  v[i] > maxSum.back())
            maxSum.pop_back();
        maxSum.push_back(v[i]);

//        cout << i << " " << maxSum.front() << " " << minSum << "\n";

        if(maxSum.front() - minSum > ans)
        {
            ans = maxSum.front() - minSum;
            st = index + 1;
            dr = i;
        }
    }
    cout << st << " " << dr << " " << ans;
    return 0;
}