Submission #858253

#	Time	Username	Problem	Language	Result	Execution time	Memory
858253		nhuang685	Aliens (IOI16_aliens)	C++17	4 / 100	2036 ms	432 KiB

aliens

/**
 * @file uoj240-1.cpp
 * @author n685
 * @brief
 * @date 2023-10-07
 *
 *
 */
#include <bits/stdc++.h>

#include "aliens.h"

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

using db = long double; // change it to double as needed
const db PI = std::acos(static_cast<db>(-1.0));
// constexpr db PI = std::numbers::pi_v<db>;
constexpr db EPS = 1e-9;
template <class T, class U> constexpr bool eq(const T &a, const U &b) {
  if constexpr (std::is_floating_point<
                    typename std::common_type<T, U>::type>::value) {
    return (std::abs(a - b) < EPS);
  } else {
    return (a == b);
  }
}

struct I {
  int64_t l = 0, r = 0;
  bool operator<(const I &i) const {
    return (l == i.l) ? (r > i.r) : (l < i.l);
  }
  bool contains(const I &i) const { return l <= i.l && i.r <= r; }
};
struct L {
  db m, b;
  int ind;
  auto eval(db x) const { return m * x + b; }
  db isect(const L &l) const { return (b - l.b) / (l.m - m); }
};

long long take_photos(int n, int m, int k, std::vector<int> r,
                      std::vector<int> c) {
  std::vector<I> vv(n);
  for (int i = 0; i < n; ++i) {
    vv[i] = {std::min(r[i], c[i]), std::max(r[i], c[i])};
  }
  std::sort(vv.begin(), vv.end());
  std::vector<I> v;
  v.push_back(vv[0]);
  for (int i = 1; i < n; ++i) {
    if (!v.back().contains(vv[i])) {
      v.push_back(vv[i]);
    }
  }
  n = (int)v.size();

  std::vector<db> dp;
  std::vector<int> cnt, ind;
  auto good = [&](db cc) -> bool {
    dp.assign(n + 1, 0);
    cnt.assign(n + 1, 0);
    ind.assign(n + 1, 0);
    std::deque<L> dq = {
        L{(db)-2 * (v[0].l - 1), dp[0] + (v[0].l - 1) * (v[0].l - 1) + cc, 0}};
    auto ins = [&](const L &l) {
      while ((int)dq.size() >= 2) {
        if (eq(l.m, dq.back().m)) {
          if (l.b < dq.back().b) {
            dq.pop_back();
          } else if (eq(l.b, dq.back().b) && cnt[l.ind] < cnt[dq.back().ind]) {
            dq.pop_back();
          } else {
            return;
          }
        } else {
          // std::pair<int64_t, int64_t> ins1 = dq.end()[-2].isect(dq.back()),
          //                             ins2 = dq.back().isect(l);
          // if (ins1.first * ins2.second >= ins2.first * ins1.second) {
          if (dq.end()[-2].isect(dq.back()) >= dq.back().isect(l)) {
            dq.pop_back();
          } else {
            break;
          }
        }
      }
      dq.push_back(l);
    };
    auto insFront = [&](const L &l) {
      while ((int)dq.size() >= 2) {
        if (eq(l.m, dq[0].m)) {
          if (l.b < dq[0].b) {
            dq.pop_front();
          } else if (eq(l.b, dq[0].b) && cnt[l.ind] < cnt[dq[0].ind]) {
            dq.pop_front();
          } else {
            return;
          }
        } else {
          // std::pair<int64_t, int64_t> ins1 = dq.end()[-2].isect(dq.back()),
          //                             ins2 = dq.back().isect(l);
          // if (ins1.first * ins2.second >= ins2.first * ins1.second) {
          if (dq[1].isect(dq[0]) <= dq[0].isect(l)) {
            dq.pop_front();
          } else {
            break;
          }
        }
      }
      dq.push_front(l);
    };
    auto query = [&](auto x) {
      while ((int)dq.size() > 1) {
        if (dq[0].eval(x) >= dq[1].eval(x)) {
          dq.pop_front();
        } else {
          break;
        }
      }
    };
    for (int i = 1; i <= n; ++i) {
      query(v[i - 1].r);
      dp[i] = dq[0].eval(v[i - 1].r) + v[i - 1].r * v[i - 1].r;
      cnt[i] = cnt[dq[0].ind] + 1;
      ind[i] = dq[0].ind;
      if (dp[i] < 0) {
        // continue;
      }
      if (i < n) {
        ins(L{(db)-2 * (v[i].l - 1),
              dp[i] + (v[i].l - 1) * (v[i].l - 1) -
                  std::max<db>(0, v[i - 1].r - v[i].l + 1) *
                      std::max<db>(0, v[i - 1].r - v[i].l + 1) +
                  cc,
              i});
      }
    }
    return (cnt[n] <= k);
  };
  db ll = 0, rr = (db)m * m;
  while (std::abs(rr - ll) >= 1e-15) {
    db mid = (ll + rr) / 2;
    if (good(mid)) {
      rr = mid;
    } else {
      ll = mid;
    }
  }
  // cerr << std::fixed << std::setprecision(20);
  // dbg(rr);
  // dbg(dp[n] - rr * cnt[n]);
  good(rr);
  assert(cnt[n] <= k);
  return (long long)std::round(dp[n] - rr * cnt[n]);
}

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:109:10: warning: variable 'insFront' set but not used [-Wunused-but-set-variable]
  109 |     auto insFront = [&](const L &l) {
      |          ^~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40