Submission #74341

#	Time	Username	Problem	Language	Result	Execution time	Memory
74341		khsoo01	Hill Reconstruction (FXCUP3_hill)	C++11	100 / 100	797 ms	86516 KiB

hill

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
 
typedef long long ll;
 
const ll N = 300005;
 
ll n, b, x[N], y[N];
 
struct line {
	ll a, b;
	bool operator < (const line &T) const {
		return a * T.b < T.a * b;
	}
};
 
priority_queue<pair<line, ll> > s;
set<ll> lft;
 
ll area (ll A, ll B, ll C) {
	return abs((x[A]*y[B]+x[B]*y[C]+x[C]*y[A]) - (y[A]*x[B]+y[B]*x[C]+y[C]*x[A]));
}
 
ll gcd (ll A, ll B) {
	if(B) return gcd(B, A%B);
	return A;
}
 
line getl (ll A, ll B) {
	if(A > B) swap(A, B);
	return {y[B]-y[A], x[B]-x[A]};
}
 
int main()
{
	scanf("%lld%lld",&n,&b);
	b *= 2;
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&x[i]);
	}
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&y[i]);
		lft.insert(i);
	}
	for(ll i=3;i<=n;i++) {
		s.push({getl(i-1, i), i});
	}
	while(!s.empty()) {
		auto it1 = s.top(); s.pop();
		auto it2 = lft.find(it1.Y);
		if(it2 == lft.end()) continue;
		ll A, B, C;
		A = *it2; it2--;
		B = *it2; it2--;
		C = *it2;
		if(getl(A, B) < getl(B, C)) continue;
		ll T = area(A, B, C);
		if(T > b) break;
		b -= T;
		lft.erase(B);
		if(*lft.begin() != C) {
			s.push({getl(C, A), A});
		}
	}
	vector<ll> V;
	for(auto &T : lft) {
		V.push_back(T);
	}
	line R = {0, 1};
	for(int i=1;i<(int)V.size();i++) {
		R = max(R, getl(V[i], V[i-1]));
	}
	ll G = gcd(R.a, R.b);
	printf("%lld/%lld\n",R.a/G,R.b/G);
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x[i]);
   ~~~~~^~~~~~~~~~~~~~
hill.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&y[i]);
   ~~~~~^~~~~~~~~~~~~~
hill.cpp:32:2: warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false [-Wstrict-overflow]
  if(A > B) swap(A, B);
  ^~

• Subtask 1: 32 / 32
• Subtask 2: 68 / 68