Cod sursa(job #1828183)

Utilizator antracodRadu Teodor antracod Data 12 decembrie 2016 21:40:33
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("secv2.in");
ofstream out("secv2.out");

const int NMAX = 50000;
const int INF =(1<<30);
int n,k;
long long int v[NMAX+2];
long long int sp[NMAX+2];
long long int mp[NMAX+2];
long long int st,dr,xmin;

void solve()
{
    long long int sol=-INF;
    for(int i=n;i>k-1;i--)
    {
        long long int p=sp[i]-mp[i-k+1];
        if(p>=sol)
        {
            dr=i;
            xmin=mp[i-k];
            sol=p;
        }
    }
    for(int i=dr-k;i>0;i--)
    {
        if(sp[i]==xmin)
        {
            st=i+1;
            break;
        }
    }
    out<<st<<" "<<dr<<" "<<sol;
}

int main()
{
    in>>n>>k;
    mp[0]=INF;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
        sp[i]=sp[i-1]+v[i];
        mp[i]=min(mp[i-1],sp[i]);
    }
    solve();
    return 0;
}