Cod sursa(job #2464550)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 28 septembrie 2019 16:04:46
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define NM 100005
#define val first
#define poz second
#define pii pair<int,int>
#define pb push_back
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");

int n,k,st,dr,ind,sMax,s[NM];
pii v[NM];

deque <pii> dq;

void Read();
void Solve();

int main()
{   Read();
    Solve();
    f.close();
    g.close();
    return 0;
}

void Read()
{   f>>n>>k;
    for(int nr,i=1; i<=n; i++)
    {   f>>nr;
        s[i]=s[i-1]+nr;
    }
}

void Solve()
{   for(int i=0; i<=n-k; i++)
    {   if(!dq.empty())
        {   while(s[i]<=dq.back().val)
            {   dq.pop_back();
                if(dq.empty())
                    break;
            }
        }
        dq.pb({s[i],i});
        v[i+k]=dq.front();
    }
    sMax=s[k]-v[k].val;
    st=v[k].poz;
    dr=k;
    for(int i=k+1; i<=n; i++)
        if(s[i]-v[i].val>=sMax)
        {   sMax=s[i]-v[i].val;
            st=v[i].poz+1;
            dr=i;
        }
    g<<st<<' '<<dr<<' '<<sMax;
}