Submission #601374

#	Time	Username	Problem	Language	Result	Execution time	Memory
601374		Soumya1	Aliens (IOI16_aliens)	C++17	100 / 100	188 ms	5568 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
using ll = long long;
struct Line {
  ll m = 0, c = 0;
  int cnt = 0;
  Line(ll _m, ll _c, int _cnt) : m(_m), c(_c), cnt(_cnt) { }
  ll get(ll x) { return m * x + c; }
  double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
  bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
  deque<Line> hull;
  void insert(Line l) {
    while (hull.size() > 1) {
      auto last = hull.end()[-1];
      auto p_last = hull.end()[-2];
      if (p_last.good(last, l)) break;
      hull.pop_back();
    }
    hull.push_back(l);
  }
  pair<ll, int> query(ll x) {
    while (hull.size() > 1 && hull[0].get(x) > hull[1].get(x)) {
      hull.pop_front();
    }
    return {hull[0].get(x), hull[0].cnt};
  }
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  vector<pair<int, int>> a;
  for (int i = 0; i < n; i++) {
    r[i]++, c[i]++;
    a.push_back({min(r[i], c[i]) - 1, max(r[i], c[i])});
  }
  sort(a.begin(), a.end(), [&](auto i, auto j) {
    if (i.first != j.first) return i.first < j.first;
    return i.second > j.second;
  });
  {
    vector<pair<int, int>> final;
    auto last = make_pair(-1, -1);
    for (int i = 0; i < n; i++) {
      auto [x, y] = a[i];
      if (x >= last.first && y <= last.second) continue;
      final.push_back(a[i]);
      last = a[i];
    }
    a = final;
  }
  auto sq = [&](ll x) {
    return 1LL * x * x;
  };
  a.insert(a.begin(), {0, 0});
  n = a.size() - 1;
  auto check = [&](ll m) {
    CHT cht;
    cht.insert(Line(-a[1].first, sq(a[1].first), 0));
    for (int i = 1; i <= n; i++) {
      auto x = cht.query(2 * a[i].second);
      ll dp = x.first + sq(a[i].second) + m;
      if (i == n) return pair<ll, int> {dp, x.second + 1};
      cht.insert(Line(-a[i + 1].first, dp - sq(max(0, a[i].second - a[i + 1].first)) + sq(a[i + 1].first), x.second + 1));
    }
    return pair<ll, int> {0, 0};
  };
  ll lo = 0, hi = 1e13;
  while (lo < hi) {
    ll mid = (lo + hi) >> 1;
    if (check(mid).second <= k) hi = mid;
    else lo = mid + 1;
  }
  auto x = check(lo);
  return x.first - 1LL * k * lo;
}

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