Submission #645597

#	Time	Username	Problem	Language	Result	Execution time	Memory
645597		ymm	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	312 KiB

segments

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

__int128 cross(pll a, pll b)
{
	return (__int128)a.first * b.second - (__int128)a.second * b.first;
}

pll dif(pll a, pll b)
{
	return {a.first - b.first, a.second - b.second};
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	vector<pll> con = {{0, 0}};
	int n;
	cin >> n;
	ll sum = 0;
	Loop (i,1,n+1) {
		int x;
		cin >> x;
		sum += x;
		pll p = {i, sum};
		for (;;) {
			int n = con.size();
			if (n < 2)
				break;
			if (cross(dif(con[n-1], con[n-2]), dif(p, con[n-1])) >= 0)
				break;
			con.pop_back();
		}
		con.push_back(p);
	}
	cout << con.size()-1 << '\n';
}

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