Submission #863041

#	Time	Username	Problem	Language	Result	Execution time	Memory
863041		HataNoKokoro	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	2396 KiB

segments

#include <bits/stdc++.h>

using namespace std;

const int maxN = 5e5 + 5;

int n, pos;
pair<int, long long> dp[maxN];
long long s[maxN];

bool better(const pair<int, long long> &a, const pair<int, long long> &b)
{
    if(a.first > b.first)
        return true;
    if(a.first != b.first)
        return false;
    return (a.first < b.first);
}

int main()
{
    cin >> n;

    s[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] += s[i - 1];

        dp[i].first = -1;
    }

    dp[1].first = 1;
    dp[1].second = s[1];
    for(int i = 1; i < n; i++)
    {
        if(!better(dp[i + 1], make_pair(dp[i].first, dp[i].second + s[i + 1] - s[i])))
            dp[i + 1] = dp[i];
        pos = lower_bound(s, s + n, s[i] + dp[i].second) - s;
        if(!better(dp[pos], make_pair(dp[i].first + 1, s[pos] - s[i])))
        {
            dp[pos].first = dp[i].first + 1;
            dp[pos].second = s[pos] - s[i];
        }
    }
    cout << dp[n].first;
    return 0;
}

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