Cod sursa(job #2564428)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 1 martie 2020 21:21:55
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("numar2.in");
ofstream fout("numar2.out");
long long s[200003], x, k, n, val;
int LungimeMax(int k)
{
    int i;
    for(i=k; i<=n; i++)
        if(s[i]-s[i-k]<=val)
         return 1;
    return 0;
}
int Cb(int x)
{
    int mij,dr=n, st=1, p=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(LungimeMax(mij)==1)
        {
            p=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return p;
}
int main()
{
    int i;
    fin>> n >> val;
    for(i=1; i<=n; i++)
        {
            fin >> x;
            s[i]=s[i-1]+x;
        }
    fout << Cb(n);

    return 0;
}