Submission #536683

#	Time	Username	Problem	Language	Result	Execution time	Memory
536683		blue	Bigger segments (IZhO19_segments)	C++17	100 / 100	201 ms	45340 KiB

segments

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

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

	int N;
	cin >> N;

	ll Asum[1+N];
	Asum[0] = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> Asum[i];
		Asum[i] += Asum[i-1];
	}

	pll DP[1+N];
	DP[0] = {0, 0};

	set<pll> tbv;

	pll currbest{0, 0};

	for(int i = 1; i <= N; i++)
	{
		// cerr << "\n\n\ni = " << i << '\n';
		tbv.insert({DP[i-1].second + Asum[i-1], i-1});
		// cerr << "tbv insert " << DP[i-1].second + Asum[i-1] << ' ' << i-1 << '\n';

		// cerr << tbv.begin()->first << '\n';

		while(!tbv.empty() && tbv.begin()->first <= Asum[i])
		{
			currbest = max(currbest, {DP[tbv.begin()->second].first, tbv.begin()->second});
			// cerr << "tbv erase " << tbv.begin()->first << ' ' << tbv.begin()->second << '\n';
			tbv.erase(tbv.begin());
		}

		DP[i] = {currbest.first + 1, Asum[i] - Asum[currbest.second]};

		// cerr << i << " : " << DP[i].first << ' ' << DP[i].second << '\n';
	}

	cout << DP[N].first << '\n';
}

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