Submission #336728

#	Time	Username	Problem	Language	Result	Execution time	Memory
336728		lovro_nidogon1	Cover (COCI18_cover)	C++14	12 / 120	5 ms	492 KiB

cover

#include<bits/stdc++.h>
#define breturn return
#define ll long long
using namespace std;
vector<pair<ll, ll> > kor, hull, bruh;
pair<ll, ll> poc;
ll n, a, b, c, dp[5002]; 
bool ccw(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
//	cout << a.first << " " << a.second << " - " << b.first << " " << b.second << " - " << c.first << " " << c.second << '\n';
	if(a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0) breturn true;
	else breturn false; 
}
int main() {
	cin >> n;
	c = -1;
	for(ll i = 0; i < n; i++) {
		cin >> a >>b;
		a = abs(a), b = abs(b);
		kor.push_back({a, b});
		if(b > c) c = b, poc = {a, b}; 
	}
	if(n == 1) breturn cout << a * b * 4<< '\n', 0;
	sort(kor.begin(), kor.end());
	ll x = 0;
	while(kor[x] != poc) x++;
	hull.push_back(kor[x]);
	for(ll i = x; i < n; i++) {
		if(kor[i].first > hull[hull.size() - 1].first and kor[i].second < hull[hull.size() - 1].second) hull.push_back(kor[i]);
	}
	dp[0] = 0;
	for(ll i = 0; i < hull.size(); i++) {
		bruh.push_back({hull[i].second, dp[i]});
		ll l = 0;
		ll r = bruh.size() - 1;
		while(l != r) {
			ll mid = (l + r)/2;
			if(bruh[mid].first * hull[i].first + bruh[mid].second > bruh[mid + 1].first * hull[i].first + bruh[mid + 1].second) l = mid + 1;
			else r = mid;
		}
		dp[i + 1] = bruh[l].first * hull[i].first + bruh[l].second;
	}
	cout << dp[hull.size()] * 4;
}

Compilation message (stderr)

cover.cpp: In function 'int main()':
cover.cpp:31:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(ll i = 0; i < hull.size(); i++) {
      |                ~~^~~~~~~~~~~~~

• Subtask 1: 12 / 120