제출 #1347601

#제출 시각아이디문제언어결과실행 시간메모리
1347601SSKMFBigger segments (IZhO19_segments)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

int64_t sir[500001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime;
    cin >> lungime;

    for (int indice = 1 ; indice <= lungime ; indice++)
    { 
        cin >> sir[indice];
        sir[indice] += sir[indice - 1];
    }

    int maxim = 0;
    for (int inceput = 1 ; inceput <= lungime ; inceput++)
    {
        int candidat = 1 , anterior = 0 , indice = inceput;
        while (true)
        {
            const int64_t urmatorul = 2 * sir[indice] - sir[anterior];
            if (sir[lungime] < urmatorul)
                { break; }

            int stanga = indice + 1 , dreapta = lungime;
            while (stanga <= dreapta)
            {
                const int mijloc = (stanga + dreapta) >> 1;
                if (sir[mijloc] < urmatorul) { stanga = mijloc + 1; }
                else { dreapta = mijloc - 1; }
            }

            anterior = indice;
            indice = stanga;
            candidat++;
        }

        maxim = max(maxim , candidat);
    }

    cout << maxim;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...