| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 72241 | 이시대의진정한망겜스타투 (#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 <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
int N;
pll p[300030];
ll C;
pll operator-(pll a, pll b) { return pll(a.Fi - b.Fi, a.Se - b.Se); }
pll operator+(pll a, pll b) { return pll(a.Fi + b.Fi, a.Se + b.Se); }
ll operator/(pll a, pll b) { return a.Fi * b.Se - a.Se * b.Fi; }
int nxt[600030], pre[600030];
pll data[600060];
int chk[600060];
ll gc(ll x, ll y) { return y == 0 ? x : gc(y, x%y); }
void upd(pll &a, pll b) {
if(a.Se * b.Fi < b.Se * a.Fi) a = b;
}
struct str {
str(){}
str(ll dx, ll dy) { p = pll(dx, dy); }
str(pll p) : p(p) {}
pll p;
bool operator<(const str &rhs) const {
return p.Se * rhs.p.Fi < p.Fi * rhs.p.Se;
}
};
void output(pll p) {
ll g = gc(p.Fi, p.Se);
p.Fi /= g;
p.Se /= g;
printf("%lld/%lld\n", p.Se, p.Fi);
}
int main() {
scanf("%d", &N);
scanf("%lld", &C);
C *= 2;
for(int i=1;i<=N;i++) {
scanf("%lld", &p[i].Fi);
}
for(int i=1;i<=N;i++) {
scanf("%lld", &p[i].Se);
}
for(int i=1;i<N;i++) data[i] = p[i+1] - p[i];
for(int i=0;i<=N;i++) {
nxt[i] = i + 1;
pre[i] = i - 1;
}
priority_queue <pair<str, int> > pq;
for(int i=2;i<=N;i++) {
pq.push(make_pair(str(p[i] - p[i-1]), i - 1));
}
int cs = N;
pll ans = pll(0, 1);
while(!pq.empty()) {
auto pr = pq.top(); pq.pop();
if(chk[pr.Se] == 1) continue;
if(pre[pr.Se] == 0 || szz(pq) == 0) { output(pr.Fi.p); return 0; }
pll me = pr.Fi.p;
if(ans.Se * me.Fi > ans.Fi * me.Se) ans = me;
pll prp = data[pre[pr.Se]];
ll val = prp / (prp + me);
if(C < val) { output(pr.Fi.p); return 0; }
C -= val;
int u = pr.Se, v = pre[u];
chk[u] = chk[v] = 1;
int nw = ++cs;
pre[nw] = pre[v];
nxt[nw] = nxt[u];
pre[nxt[u]] = nw;
nxt[pre[v]] = nw;
data[nw] = prp + me;
pq.push(make_pair(data[nw], nw));
}
output(ans);
return 0;
}