Cod sursa(job #1405923)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 29 martie 2015 16:08:23
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n,k,s[50002],mini[50002],x,nr_mini;
struct solutie
{
        int p1,pf,sum;
}sol_final;
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        s[i]=s[i-1]+x;
    }
    sol_final.p1=1;sol_final.pf=n;sol_final.sum=s[n];
    for(int i=1;i<=n;i++)
    {
        if(s[i]<mini[nr_mini])
        {
            mini[++nr_mini]=i;
            for(int j=nr_mini-1;j>=0;j--)
            {
                if(mini[nr_mini]-mini[j]-1>=k && s[mini[nr_mini]-1]-s[mini[j]]>sol_final.sum)
                {
                    sol_final.sum=s[mini[nr_mini]-1]-s[mini[j]];
                    sol_final.p1=mini[j]+1;
                    sol_final.pf=mini[nr_mini]-1;
                }
            }
        }
    }
    fout<<sol_final.p1<<' '<<sol_final.pf<<' '<<sol_final.sum;

    return 0;
}