Submission #72123

#	Time	Username	Problem	Language	Result	Execution time	Memory
72123		(#118)	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	1045 ms	22960 KiB

hill

#include <cstdio>
#include <set>
using namespace std;

int x[300002], y[300002];
int pv[300002];

struct S {
  int i, j, dx, dy;

  bool operator< (const S &r) const { // 가장 가파른 게 가장 앞에 오도록
    long long v = 1LL * r.dx * dy;
    long long w = 1LL * r.dy * dx;

    if(v != w) return v > w;

    return i < r.i;
  }
};

set<S> p;

long long area(int a, int b, int c){
  int x1 = x[a], y1 = y[a];
  int x2 = x[b], y2 = y[b];
  int x3 = x[c], y3 = y[c];

  long long v = 1LL * x1 * y2 + 1LL * x2 * y3 + 1LL * x3 * y1;
  long long w = 1LL * y1 * x2 + 1LL * y2 * x3 + 1LL * y3 * x1;

  return v > w ? v - w : w - v;
}

int gcd(int x, int y){
  if(x == 0 || y == 0) return x + y;

  for(;;){
    int t = x % y; if(t == 0) break;
    x = y; y = t;
  }

  return y;
}

int main(){
  int N; long long C; scanf("%d%lld", &N, &C);
  C *= 2;

  for(int i = 1; i <= N; i++) scanf("%d", &x[i]);
  for(int i = 1; i <= N; i++) scanf("%d", &y[i]);

  for(int i = 1; i < N; i++){
    p.insert({ i, i + 1, x[i + 1] - x[i], y[i + 1] - y[i] });
    pv[i + 1] = i;
  }

  for(;;){
    S now = *p.begin();
    if(now.i == 1) break; // convex

    int pre = pv[now.i]; // (pre, i)

    // pre, now.i, now.j triangle
    long long s = area(pre, now.i, now.j);

    if(s > C) break;

    C -= s;

    p.erase(p.begin());
    p.erase({ pre, now.i, x[now.i] - x[pre], y[now.i] - y[pre] });

    // printf("%d - %d, %d - %d\n", pre, now.i, now.i, now.j);

    p.insert({ pre, now.j, x[now.j] - x[pre], y[now.j] - y[pre] });

    // printf("%d - %d, %d / %d\n", pre, now.j, y[now.j] - y[pre], x[now.j] - x[pre]);

    pv[now.j] = pre;
  }

  S ans = *p.begin();
  int g = gcd(ans.dx, ans.dy);

  printf("%d/%d\n", ans.dy / g, ans.dx / g);
  return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:46:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N; long long C; scanf("%d%lld", &N, &C);
                       ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:49:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= N; i++) scanf("%d", &x[i]);
                               ~~~~~^~~~~~~~~~~~~
hill.cpp:50:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= N; i++) scanf("%d", &y[i]);
                               ~~~~~^~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 68 / 68