| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72303 |
2018-08-26T06:57:26 Z |
The quick brown fox jumps over the lazy dog(#2200, khsoo01) |
Hill Reconstruction (FXCUP3_hill) |
C++17 |
|
1069 ms |
32848 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);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
476 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
476 KB |
Output is correct |
| 6 |
Correct |
3 ms |
476 KB |
Output is correct |
| 7 |
Correct |
5 ms |
724 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
476 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
476 KB |
Output is correct |
| 6 |
Correct |
3 ms |
476 KB |
Output is correct |
| 7 |
Correct |
5 ms |
724 KB |
Output is correct |
| 8 |
Correct |
3 ms |
724 KB |
Output is correct |
| 9 |
Correct |
272 ms |
32780 KB |
Output is correct |
| 10 |
Correct |
252 ms |
32780 KB |
Output is correct |
| 11 |
Correct |
1069 ms |
32780 KB |
Output is correct |
| 12 |
Correct |
358 ms |
32780 KB |
Output is correct |
| 13 |
Correct |
178 ms |
32780 KB |
Output is correct |
| 14 |
Correct |
245 ms |
32780 KB |
Output is correct |
| 15 |
Correct |
368 ms |
32780 KB |
Output is correct |
| 16 |
Correct |
286 ms |
32848 KB |
Output is correct |
| 17 |
Correct |
267 ms |
32848 KB |
Output is correct |
| 18 |
Correct |
268 ms |
32848 KB |
Output is correct |
| 19 |
Correct |
361 ms |
32848 KB |
Output is correct |
