Submission #470206

#	Time	Username	Problem	Language	Result	Execution time	Memory
470206		flashmt	Aliens (IOI16_aliens)	C++17	100 / 100	229 ms	6516 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;

struct Line
{
  long long a, b;
  int id;

  long long calc(long long x)
  {
    return a * x + b;
  }
};

struct Hull
{
  deque<Line> q;

  int isBad(Line x, Line y, Line z)
  {
    return (x.b - z.b) * (z.a - y.a) >= (y.b - z.b) * (z.a - x.a);
  }

  void add(long long a, long long b, int id)
  {
    Line l = {a, b, id};
    while (size(q) >= 2 && isBad(q[size(q) - 2], q.back(), l))
      q.pop_back();
    q.push_back(l);
  }

  pair<long long, int> query(long long x)
  {
    while (size(q) >= 2 && q[0].calc(x) > q[1].calc(x))
      q.pop_front();
    return {q[0].calc(x), q[0].id};
  }
};

long long sqr(long long x)
{
  return x * x;
}

pair<long long, int> solve(vector<pair<int, int>> &a, long long penalty)
{
  int n = size(a) - 1;
  Hull hull;
  vector<pair<long long, int>> f(n + 1, pair<int, int>(oo, 0)); // (cost, number of photos)
  f[0] = {0, 0};
  for (int i = 1; i <= n; i++)
  {
    long long curB = f[i - 1].first + sqr(a[i].first) - sqr(max(0, a[i - 1].second - a[i].first));
    hull.add(-2 * a[i].first, curB, i - 1);
    auto [cost, id] = hull.query(a[i].second);
    f[i] = {cost + sqr(a[i].second) + penalty, f[id].second + 1};
  }
  return f[n];
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
  vector<pair<int, int>> a = {{-1, -1}};
  for (int i = 0; i < n; i++)
    a.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1});
  sort(begin(a), end(a));

  int cur = 0;
  for (int i = 1; i <= n; i++)
    if (a[i].first == a[cur].first) a[cur].second = a[i].second;
    else if (a[i].second > a[cur].second) a[++cur] = a[i];
  n = cur;
  a.resize(n + 1);

  long long low = 0, high = 1e12, res = high;
  while (low <= high)
  {
    long long mid = (low + high) / 2;
    if (solve(a, mid).second > k) low = mid + 1;
    else
    {
      res = mid;
      high = mid - 1;
    }
  }

  auto [f, photo] = solve(a, res);
  return f - k * res;
}

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