Submission #171628

#	Time	Username	Problem	Language	Result	Execution time	Memory
171628		davitmarg	Bigger segments (IZhO19_segments)	C++17	100 / 100	139 ms	20968 KiB

segments

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 500005;


int n;
LL a[N],pr[N];
pair<int, LL> dp[N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%lld", a + i);
	for (int i = 1; i <= n; i++)
	{
		dp[i] = MP(0, -mod * mod);
		pr[i] = pr[i - 1] + a[i];
	}
	for (int i = 0; i < n; i++)
	{
		dp[i + 1] = max(dp[i + 1], MP(dp[i].first, dp[i].second - a[i+1]));
		int l = i + 1, r = n, m, pos = 0;
		while (l <= r)
		{
			m = (l + r) / 2;
			if (pr[m] - pr[i] >= -dp[i].second)
			{
				r = m - 1;
				pos = m;
			}
			else
				l = m + 1;
		}
		dp[pos] = max(dp[pos], MP(dp[i].first + 1, pr[i] - pr[pos]));
		//cout << i << " = " << dp[i].first << " : " << -dp[i].second << endl;
		//cout << pos << endl << endl;
	}
	cout << dp[n].first << endl;
	return 0;
}

/*





*/

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
   ~~~~~^~~~~~~~~~~~~~~

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