Cod sursa(job #2220093)

Utilizator patcasrarespatcas rares danut patcasrares Data 10 iulie 2018 15:24:05
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<queue>
#include<iostream>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<stack>
#define DN 50005
#define x first
#define y second
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n,a[DN],s[DN],dp1[DN],dp2[DN],k,l,st,dr,ma=-15e8,t;
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    l=k;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i];
        if(a[i]>dp1[i-1]+a[i]||i==1)
        {
            dp1[i]=a[i];
            dp2[i]=i;
        }
        else
        {
            dp1[i]=a[i]+dp1[i-1];
            dp2[i]=dp2[i-1];
        }
        if(i<l)
            continue;
        t=i-l+1;
        if(s[i]-s[t]+dp1[t]>ma)
        {
            ma=s[i]-s[t]+dp1[t];
            dr=i;
            st=dp2[t];
        }
    }
    fout<<st<<' '<<dr<<' '<<ma;
}