Cod sursa(job #2457598)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 18 septembrie 2019 10:04:32
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");
typedef long long ll;
int x[50001],n,k;
struct sol
{
    int st;
    ll sum;
};
sol make(int st,ll sum)
{
    sol rez;
    rez.st=st;
    rez.sum=sum;
    return rez;
}
sol kalvin[50001];
void solve()
{
    kalvin[1]=make(1,x[1]);
    for(int i=2;i<=n;i++)
    {
        if(kalvin[i-1].sum>=0)
            kalvin[i]=make(kalvin[i-1].st,kalvin[i-1].sum+x[i]);
        else
            kalvin[i]=make(i,x[i]);
    }
    ll curentsum=0;
    ll bestsum=0;
    int st,bst,bdr;
    st=bst=1;
    bdr=k;
    for(int i=1;i<=k;i++)
        bestsum=curentsum=curentsum+x[i];
    for(int i=k+1;i<=n;i++)
    {
        curentsum=curentsum+x[i]-x[i-k];
        st=i-k+1;
        int compara=curentsum;
        if(kalvin[i-k].sum>0)
        {
            st=kalvin[i-k].st;
            compara+=kalvin[i-k].sum;
        }
        if(compara>bestsum)
        {
            bestsum=compara;
            bst=st;
            bdr=i;
        }
    }
    g<<bst<<' '<<bdr<<' '<<bestsum;

}


int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>x[i];
    solve();
    f.close();
    g.close();
    return 0;
}