Submission #261263

#	Time	Username	Problem	Language	Result	Execution time	Memory
261263		Berted	Discharging (NOI20_discharging)	C++14	100 / 100	200 ms	30936 KiB

Discharging

#include <iostream>
#include <deque>
#include <vector>
#define ll long long
#define vi vector<ll>
#define pii pair<ll, ll>
#define fst first
#define snd second
#define vpi vector<pii>

using namespace std;

const long double EPS = 1e-9;

int n;
ll ar[1000001];
vpi dt;
deque<pii> s;

long double xIntercept(pii a, pii b)
{
	return (long double)(b.snd - a.snd) / (a.fst - b.fst);
}

ll eval(ll x, pii l) {return l.fst * x + l.snd;}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	int curMax = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> ar[i];
		if (ar[i] > ar[curMax])
		{
			dt.push_back({ar[curMax], i - curMax});
			curMax = i;
		}
	}
	dt.push_back({ar[curMax], n - curMax});
	s.push_back({n, 0});
	int curSZ = 0;
	for (int i = 0; i < dt.size(); i++)
	{
		// cout << dt[i].fst << " " << dt[i].snd << "\n";
		while (s.size() > 1 && eval(dt[i].fst, s[0]) >= eval(dt[i].fst, s[1])) {s.pop_front();}
		curSZ += dt[i].snd;
		pii l = {n - curSZ, eval(dt[i].fst, s[0])};
		while (s.size() > 1 && xIntercept(s.back(), l) - xIntercept(s.back(), s[s.size() - 2]) <= -EPS) {s.pop_back();}
		s.push_back(l);
	}
	cout << s.back().snd << "\n";
	return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < dt.size(); i++)
                  ~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28