Cod sursa(job #1828178)

Utilizator antracodRadu Teodor antracod Data 12 decembrie 2016 21:31:42
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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;
int v[NMAX+2];
int sp[NMAX+2];
int mp[NMAX+2];
int st,dr,xmin;
void sumepart()
{
    mp[0]=INF;
    for(int i=1; i<=n; i++)
    {
        sp[i]=sp[i-1]+v[i];
        mp[i]=min(mp[i-1],sp[i]);
    }
}

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

int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
    }
    sumepart();
    solve();
    return 0;
}