Cod sursa(job #2866294)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 9 martie 2022 16:11:49
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

int n,k;
int s[50005];

int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for(int i=1;i<=n;++i)cin >> s[i],s[i]+=s[i-1];
    deque <int> dq;
    int ans=INT_MIN,ansi,ansj;
    for(int i=k;i<=n;++i){
        while(!dq.empty() && s[dq.back()]>s[i-k])dq.pop_back();
        dq.push_back(i-k);
        while(!dq.empty() && s[dq.back()]>0)dq.pop_back();
        if(dq.empty()){
            if(ans<s[i]){
                ans = s[i];
                ansi=1;
                ansj=i;
            }
        }else {
                if(ans<s[i]-s[dq.front()]){
                    ans = s[i]-s[dq.front()];
                    ansi=dq.front()+1;
                    ansj=i;
                }
            }
    }
    cout << ansi << " " << ansj << " " << ans;
}