Submission #1080642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080642		juicy	Aliens (IOI16_aliens)	C++17	100 / 100	122 ms	9036 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

struct line {
  long long a, b;
  int c;

  long long div(long long a, long long b) const {
    return a / b - ((a ^ b) < 0 && a % b);
  }

  long long slope(const line &o) const {
    return div(o.b - b, a - o.a);
  }

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

deque<line> hull;

void add(line l) {
  while (hull.size() > 1 && hull.end()[-2].slope(hull.back()) >= hull.back().slope(l)) {
    hull.pop_back();
  }
  hull.push_back(l);
}

pair<long long, int> qry(long long x) {
  while (hull.size() > 1 && hull[0].eval(x) > hull[1].eval(x)) {
    hull.pop_front();
  }
  return {hull[0].eval(x), hull[0].c};
}

vector<array<int, 2>> cands;

pair<long long, int> count(long long pen) {
  deque<line>().swap(hull);
  long long dp = 0;
  int lst = 0, cnt = 0;
  for (auto [x, y] : cands) {
    int l = max(0, lst - x);
    add({-2 * x, dp + (long long) x * x - (long long) l * l, cnt});
    tie(dp, cnt) = qry(y);
    dp += (long long) y * y + pen;
    ++cnt;
    lst = y;
  }
  return {dp, cnt};
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  vector<int> mi(m, m + 1);
  for (int i = 0; i < n; ++i) {
    if (r[i] > c[i]) {
      swap(r[i], c[i]);
    }
    mi[c[i]] = min(mi[c[i]], r[i]);
  }
  for (int i = 0; i < m; ++i) {
    if (mi[i] != m + 1) {
      while (cands.size() && cands.back()[0] >= mi[i]) {
        cands.pop_back();
      }
      cands.push_back({mi[i], i + 1});
    }
  }
  long long L = 0, R = (long long) m * m, res = -1;
  while (L <= R) {
    auto md = (L + R) / 2;
    if (count(md).second <= k) {
      res = md;
      R = md - 1;
    } else {
      L = md + 1;
    }
  }
  return count(res).first - 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