oj.uz

Submission #72686

# Submission time Handle Problem Language Result Execution time Memory
72686 2018-08-26T15:11:45 Z gs14004 Hill Reconstruction (FXCUP3_hill) C++17
100 / 100
 523 ms 61036 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 300050;
 
int n; lint c;
pi den, a[MAXN];
vector<pi> stk;
 
lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
 
bool big_giulgi(pi a, pi b, llf c){
	return (b.second - a.second) > (b.first - a.first) * c;
}
 
lint trial(llf x){
	stk.clear();
	stk.push_back(a[0]);
	lint ans = 0;
	for(int i=1; i<n; i++){
		while(stk.size() >= 2 && big_giulgi(stk.back(), a[i], x)){
			ans += ccw(stk[stk.size()-2], stk.back(), a[i]);
			stk.pop_back();
		}
		if(big_giulgi(stk.back(), a[i], x)){
			return 3e18;
		}
		stk.push_back(a[i]);
	}
	return ans;
}
 
bool cmp(pi a, pi b){
	return 1ll * a.first * b.second < 1ll * b.first * a.second;
}
 
int gcd(int x, int y){ return y ? gcd(y, x%y) : x; }
 
int main(){
	scanf("%d %lld",&n,&c);
	c <<= 1;
	for(int i=0; i<n; i++) scanf("%d",&a[i].first);
	for(int i=0; i<n; i++) scanf("%d",&a[i].second);
	long double s = 0, e = 2e9;
	for(int i=0; i<100; i++){
		long double m = (s+e)/2;
		if(trial(m) <= c) e = m;
		else s = m;
	}
	assert(trial(e) <= c);
	pi ans(0, 1);
	for(int i=1; i<stk.size(); i++){
		ans = max(ans, pi(stk[i].second - stk[i-1].second, stk[i].first - stk[i-1].first), cmp); 
	}
	int g = gcd(ans.first, ans.second);
	ans.first /= g;
	ans.second /= g;
	printf("%d/%d\n", ans.first, ans.second);
}

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<stk.size(); i++){
               ~^~~~~~~~~~~
hill.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&c);
  ~~~~~^~~~~~~~~~~~~~~~~
hill.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].first);
                         ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].second);
                         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 4 ms 532 KB Output is correct
5 Correct 4 ms 672 KB Output is correct
6 Correct 4 ms 752 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 4 ms 976 KB Output is correct

Subtask #2
68.0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 4 ms 532 KB Output is correct
5 Correct 4 ms 672 KB Output is correct
6 Correct 4 ms 752 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 4 ms 976 KB Output is correct
9 Correct 335 ms 13204 KB Output is correct
10 Correct 299 ms 18828 KB Output is correct
11 Correct 523 ms 24724 KB Output is correct
12 Correct 398 ms 30436 KB Output is correct
13 Correct 204 ms 31508 KB Output is correct
14 Correct 137 ms 31508 KB Output is correct
15 Correct 415 ms 41888 KB Output is correct
16 Correct 329 ms 47704 KB Output is correct
17 Correct 360 ms 48176 KB Output is correct
18 Correct 222 ms 52396 KB Output is correct
19 Correct 241 ms 61036 KB Output is correct