Submission #545558

#	Time	Username	Problem	Language	Result	Execution time	Memory
545558		iulia13	Bigger segments (IZhO19_segments)	C++14	100 / 100	238 ms	16864 KiB

segments

#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 5;
#define ll long long
ll n, v[N];
struct ura{
    ll seg, prv;
} dp[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        v[i] += v[i - 1];
    }
    dp[1] = {1, 0};
    for (int i = 1; i <= n; i++)
    {
        if (dp[i].seg < dp[i - 1].seg || (dp[i].seg == dp[i - 1].seg && dp[i].prv < dp[i - 1].prv))
            dp[i] = dp[i - 1];
        ///i e capatul intervalului vechi!
        ll st = 1, dr = n, j = n + 1;
        while (st <= dr)
        {
            int mid = (st + dr) / 2;
            if (2 * v[i] - v[dp[i].prv] <= v[mid])
            {
                j = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
        ura x = {dp[i].seg + 1, i};
        if (dp[j].seg < x.seg || (dp[j].seg == x.seg && dp[j].prv < x.prv))
            dp[j] = x;
    }
    cout << dp[n].seg;
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27