Submission #172245

#	Time	Username	Problem	Language	Result	Execution time	Memory
172245		golikovnik	Aliens (IOI16_aliens)	C++14	60 / 100	2081 ms	361280 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using real_t = long double;

struct line {
  i64 k, b;

  [[nodiscard]] i64 apply(i64 x) const {
    return k * x + b;
  }
};

real_t inter(line const& a, line const& b) {
  return static_cast<real_t>(a.b - b.b) / (b.k - a.k);
}

struct hull {
  struct item {
    line l;
    real_t from;
    real_t to;

    item(line l_, real_t from_, real_t to_) : l(l_), from(from_), to(to_) {}
  };
  vector<item> lines;
  real_t const inf = 1e20;
  int ptr = 0;

  void add_line(line const& l) {
    while ((int) lines.size() >= 2 &&
           inter(l, lines.back().l) <=
           inter(lines.back().l, lines[lines.size() - 2].l)) {
      lines.pop_back();
    }
    if (lines.empty()) {
      lines.emplace_back(l, -inf, inf);
    } else {
      auto x = inter(l, lines.back().l);
      lines.back().to = x;
      lines.emplace_back(l, x, inf);
    }
  }

  i64 get(i64 x) {
    ptr = min(ptr, (int) lines.size() - 1);
    while (x > lines[ptr].to) {
      ++ptr;
    }
    return lines[ptr].l.apply(x);
  }
};

i64 take_photos(int n, int, int mx, vector<int> r, vector<int> c) {
  struct cell {
    int r, c;

    cell(int r_, int c_) : r(r_), c(c_) {}
  };
  vector<cell> a;
  {
    for (int i = 0; i < n; ++i) {
      if (r[i] < c[i]) {
        swap(r[i], c[i]);
      }
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
      if (r[i] != r[j]) {
        return r[i] < r[j];
      }
      return c[i] > c[j];
    });
    for (int i = 0; i < n; ++i) {
      while (!a.empty() && a.back().c >= c[p[i]]) {
        a.pop_back();
      }
      a.emplace_back(r[p[i]], c[p[i]]);
    }
  }
  n = (int) a.size();
  mx = min(mx, n);
  i64 const INF = (i64) 1e18;
  vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
  fill(dp[0].begin(), dp[0].end(), 0);
  auto relax = [&](i64& x, i64 y) {
    if (y < x) {
      x = y;
    }
  };
  auto sqr = [](i64 x) {
    return x * x;
  };
  for (int k = 1; k <= mx; ++k) {
    hull cht;
    for (int i = 0; i < n; ++i) {
      //  dp[i + 1][k]
      auto ci = !i ? 0 : sqr(
              max<i64>(0, a[i - 1].r - a[i].c + 1));
      cht.add_line({-2 * a[i].c, sqr(a[i].c) + dp[i][k - 1] - ci});
      dp[i + 1][k] = sqr(a[i].r + 1) + cht.get(a[i].r + 1);
    }
  }
  return dp.back().back();
}

//int main() {
//  vector<int> r{0, 4, 4, 4, 4};
//  vector<int> c{3, 4, 6, 5, 6};
//  int n = (int) r.size();
//  int m = -1;
//  int k = n;
//  cout << take_photos(n, m, k, r, c) << '\n';
//}

Compilation message (stderr)

aliens.cpp: In function 'i64 take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:89:8: warning: variable 'relax' set but not used [-Wunused-but-set-variable]
   auto relax = [&](i64& x, i64 y) {
        ^~~~~

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