Cod sursa(job #1374530)

Utilizator span7aRazvan span7a Data 5 martie 2015 09:50:12
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#define maxN 50001
#define M -1<<30
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");

short a[maxN];
int s[maxN],b[maxN],n,k,poz[maxN];
void citire()
{
    int i ;
    f>>n>>k;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
        s[i]+=s[i-1]+a[i];
    }
}
void solve()
{
    int maxx = M , i , sum_k, poz_i, poz_f ;
    for(i=1;i<=n;i++)
        b[i]=M;
    for(i=k;i<=n;i++)
    {
        sum_k=s[i]-s[i-k];
        if(sum_k  >= b[i-1]+a[i] )
        {
            b[i]=sum_k;
            poz[i]=poz[i-1]+1;
            if(sum_k > maxx)
            {
                maxx=sum_k;
                poz_i=i-k+1;
                poz_f=i;
            }
        }
        else
        {
            b[i]=   b[i-1] + a[i];
            poz[i]=poz[i-1];
            if(b[i] > maxx )
            {
                maxx=b[i];
                poz_i=poz[i-1];
                poz_f=i;
            }
        }
    }
    g<<poz_i<<" " << poz_f << " " <<maxx;
}
int main()
{
    citire();
    solve();
    return 0;
}