Submission #469119

#	Time	Username	Problem	Language	Result	Execution time	Memory
469119		flashmt	Aliens (IOI16_aliens)	C++17	41 / 100	2069 ms	5912 KiB

aliens

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

using ll = long long;

struct Line {
  mutable ll k, m, p; // y = kx + m
  bool operator<(const Line& o) const { return k < o.k; }
  bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  // query maximum value
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  const ll inf = LLONG_MAX;

  ll div(ll a, ll b) { // floored division
    return a / b - ((a ^ b) < 0 && a % b);
  }

  bool isect(iterator x, iterator y) {
    if (y == end()) { x->p = inf; return false; }
    if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    else x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }

  void add(ll k, ll m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }

  ll query(ll x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return l.k * x + l.m;
  }
};

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;

  auto sqr = [&](int x)
  {
    return 1LL * x * x;
  };

  vector<long long> f(n + 1, oo);
  f[0] = 0;
  for (int i = 1; i <= k; i++)
  {
    LineContainer lc;
    vector<long long> newF(n + 1);
    for (int j = 1; j <= n; j++)
    {
      long long value = f[j - 1] + sqr(a[j].first) - sqr(max(0, a[j - 1].second - a[j].first));
      lc.add(a[j].first * 2, -value);
      newF[j] = sqr(a[j].second) - lc.query(a[j].second);
    }
    swap(f, newF);
  }

  return f[n];
}

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