oj.uz

Submission #72288

# Submission time Handle Problem Language Result Execution time Memory
72288 2018-08-26T06:50:05 Z The quick brown fox jumps over the lazy dog(#2200, khsoo01) Hill Reconstruction (FXCUP3_hill) C++17
32 / 100
 1500 ms 42368 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;
	}
};

multiset<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.insert({getl(i-1, i), i});
	}
	while(!s.empty()) {
		auto it1 = s.end(); it1--;
		auto it2 = lft.find(it1->Y);
		s.erase(it1);
		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);
		auto it3 = s.find({getl(B, C), B});
		if(it3 != s.end()) s.erase(it3);
		if(*lft.begin() != C) {
			s.insert({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 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 672 KB Output is correct
8 Correct 3 ms 672 KB Output is correct

Subtask #2
0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 672 KB Output is correct
8 Correct 3 ms 672 KB Output is correct
9 Correct 589 ms 42368 KB Output is correct
10 Correct 579 ms 42368 KB Output is correct
11 Execution timed out 1550 ms 42368 KB Time limit exceeded
12 Halted 0 ms 0 KB -