| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 72515 | BOJ 8481 (#118) | Hill Reconstruction (FXCUP3_hill) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <queue>
#include <functional>
using namespace std;
typedef long long lint;
lint n,si;
lint siment;
lint x[100010];
lint y[100010];
lint gcd(lint xx, lint yy){
return xx%yy==0 ? yy : gcd(yy, xx%yy);
}
class Point{
public:
lint x;
lint y;
Point(){
x = y = 0;
}
Point(lint x1, lint y1){
x = x1;
y = y1;
}
};
Point arr[100010];
class Hill{
public:
lint dx;
lint dy;
lint s;
lint e;
Hill(){
dx = dy = s = e = 0;
}
Hill(lint i, lint j){
dx = arr[j].x - arr[i].x;
dy = arr[j].y - arr[i].y;
s = i;
e = j;
}
Hill(lint dx1, lint dy1, lint s1, lint e1){
dx = dx1, dy = dy1, s = s1, e = e1;
}
};
bool Comp(Hill a, Hill b){
return a.dx * b.dy > a.dy * b.dx;
}
bool equal(Hill a, Hill b){
return a.dx * b.dy == a.dy * b.dx;
}
lint area(Point a, Point b, Point c){
return (c.x - a.x) * (c.y + a.y) - (c.x - b.x) * (c.y + b.y) - (b.x - a.x) * (b.y + a.y);
}
priority_queue<Hill, vector<Hill>, function<bool(Hill, Hill)> > q(Comp);
Hill store[100010];
lint prev_pointer[100010];
lint main(){
scanf("%lld%lld", &n, &si);
siment = 2 * si;
for(lint i=1; i<=n; i++) scanf("%lld", &arr[i].x);
for(lint i=1; i<=n; i++) scanf("%lld", &arr[i].y);
for(lint i=1; i<n; i++){
Hill temp = Hill(i, i+1);
q.push(temp);
store[i] = temp;
prev_pointer[i+1] = i;
}
while(siment > 0 && q.size() > 1){
auto temp = q.top();
q.pop();
if(temp.s == 1) continue;
if(!equal(temp, store[temp.s])) continue;
lint a = prev_pointer[temp.s];
lint b = temp.s;
lint c = temp.e;
lint temp_area = area(arr[a], arr[b], arr[c]);
if(siment >= temp_area){
siment -= temp_area;
prev_pointer[c] = prev_pointer[b];
Hill newhill = Hill(a, c);
q.push(newhill);
store[a] = newhill;
}
}
auto result = q.top();
lint g = gcd(result.dx, result.dy);
printf("%lld/%lld\n", result.dy / g, result.dx / g);
}