Cod sursa(job #3147430)

Utilizator ChopinF69Lazar Alexandru ChopinF69 Data 26 august 2023 11:16:14
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define LONG_MAX 1LL << 63
#define LONG_MIN -1LL << 63
#define INT_MAX 1<<31 -1
#define INT_MIN -1<<31 +1
using namespace std;
string fis="secv2";
ifstream fin(fis+".in");
ofstream fout(fis+".out");
const int dim=5*1e5;
int n,k;

ll sp[dim+1],maxs[dim+1],dr[dim+1];
int main()
{

    FAST
    fin>>n>>k;
    for(int i=0;i<n;++i)
    {
        fin>>sp[i+1];
        sp[i+1]+=sp[i];
    }

    maxs[n-k]=sp[n];
    dr[n-k]=n-1;
    for(int i=n-k-1;i>=0;i--)
    {
        if(sp[i+k]>maxs[i+1])
        {
            maxs[i]=sp[i+k];
            dr[i]=i+k-1;
        }
        else
        {
            maxs[i]=maxs[i+1];
            dr[i]=dr[i+1];
        }
    }

    ll maxx=LONG_MIN,ind1,ind2;
    for(int i=0;i<=n-k;++i)
    {
        if(maxs[i]-sp[i]>maxx)
        {
            maxx=maxs[i]-sp[i];
            ind1=i;
            ind2=dr[i];
        }
    }
    fout<<ind1+1<<" "<<ind2+1<<" " <<maxx;
}