oj.uz

Submission #74341

# Submission time Handle Problem Language Result Execution time Memory
74341 2018-08-31T10:51:35 Z khsoo01 Hill Reconstruction (FXCUP3_hill) C++11
100 / 100
 797 ms 86516 KB 
#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

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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 3 ms 872 KB Output is correct
8 Correct 3 ms 872 KB Output is correct

Subtask #2
68.0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 3 ms 872 KB Output is correct
8 Correct 3 ms 872 KB Output is correct
9 Correct 246 ms 38776 KB Output is correct
10 Correct 266 ms 43608 KB Output is correct
11 Correct 797 ms 49164 KB Output is correct
12 Correct 339 ms 54964 KB Output is correct
13 Correct 164 ms 54964 KB Output is correct
14 Correct 203 ms 54964 KB Output is correct
15 Correct 335 ms 66308 KB Output is correct
16 Correct 269 ms 73152 KB Output is correct
17 Correct 257 ms 73152 KB Output is correct
18 Correct 242 ms 73152 KB Output is correct
19 Correct 366 ms 86516 KB Output is correct