Submission #593313

#	Time	Username	Problem	Language	Result	Execution time	Memory
593313		Soumya1	Aliens (IOI16_aliens)	C++17	60 / 100	2067 ms	6036 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
using ll = long long;
struct Line {
  ll m = 0, c = 0;
  Line(ll _m, ll _c) : m(_m), c(_c) { }
  ll get(ll x) { return m * x + c; }
  double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
  bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
  deque<Line> hull;
  void insert(Line l) {
    while (hull.size() > 1) {
      auto last = hull.end()[-1];
      auto p_last = hull.end()[-2];
      if (p_last.good(last, l)) break;
      hull.pop_back();
    }
    hull.push_back(l);
  }
  ll query(ll x) {
    while (hull.size() > 1 && hull[0].get(x) > hull[1].get(x)) {
      hull.pop_front();
    }
    return hull[0].get(x);
  }
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  vector<pair<int, int>> a;
  for (int i = 0; i < n; i++) {
    r[i]++, c[i]++;
    a.push_back({min(r[i], c[i]) - 1, max(r[i], c[i])});
  }
  sort(a.begin(), a.end(), [&](auto i, auto j) {
    if (i.first != j.first) return i.first < j.first;
    return i.second > j.second;
  });
  {
    vector<pair<int, int>> final;
    auto last = make_pair(-1, -1);
    for (int i = 0; i < n; i++) {
      auto [x, y] = a[i];
      if (x >= last.first && y <= last.second) continue;
      final.push_back(a[i]);
      last = a[i];
    }
    a = final;
  }
  auto sq = [&](ll x) {
    return 1LL * x * x;
  };
  a.insert(a.begin(), {0, 0});
  n = a.size() - 1;
  ll dp[n + 1], new_dp[n + 1];
  new_dp[0] = 0;
  for (int i = 0; i <= n; i++) dp[i] = 1e18;
  dp[0] = 0;
  for (int iter = 0; iter < k; iter++) {
    CHT cht;
    for (int i = 1; i <= n; i++) {
      if (dp[i - 1] != 1e18) {
        cht.insert(Line(-a[i].first, dp[i - 1] - sq(max(0, a[i - 1].second - a[i].first)) + sq(a[i].first)));
      }
      new_dp[i] = cht.query(2 * a[i].second) + sq(a[i].second);
    }
    for (int i = 0; i <= n; i++) dp[i] = min(dp[i], new_dp[i]);
  }
  return dp[n];
}

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