제출 #469118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469118		flashmt	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	204 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<>> {
  // (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;
  };

  long long ans = oo;
  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, oo);
    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));
      if (f[j - 1] != oo)
        lc.add(- a[j].first * 2, value);
      if (!lc.empty())
        newF[j] = lc.query(a[j].second) + sqr(a[j].second);
    }
    swap(f, newF);
    ans = min(ans, f[n]);
  }

  return ans;
}

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