Submission #258989

#	Time	Username	Problem	Language	Result	Execution time	Memory
258989		ipaljak	Aliens (IOI16_aliens)	C++14	60 / 100	2065 ms	7524 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<

using llint = long long;

const int MAXN = 5e4 + 5;
const llint INF = 1e17;

vector<pair<int, int>> I, P;

struct Event {
  int x, type, id;
  Event() {}
  Event(int x, int type, int id) : x(x), type(type), id(id) {}
  friend bool operator<(const Event &A, const Event &B) {
    if (A.x == B.x) return A.type < B.type;
    return A.x < B.x;
  }
};

vector<pair<int, int>> get_intervals(int n, const vector<int> &r,
                                     const vector<int> &c) {
  vector<Event> e;
  for (int i = 0; i < n; ++i) {
    int lo = min(r[i], c[i]);
    int hi = max(r[i], c[i]);
    e.emplace_back(lo, 0, i);
    e.emplace_back(hi, 1, i);
  }

  sort(e.begin(), e.end());
  multiset<int> ms;
  vector<pair<int, int>> ret;

  for (const auto &p : e) {
    if (p.type == 0) {
      ms.insert(p.x);
      continue;
    }
    int lo = min(r[p.id], c[p.id]);
    ms.erase(ms.find(lo));
    if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x);
  }

  return ret;
}

inline llint C(int i, int j) {
  if (i == j) return 0LL;
  int a = I[j].first, b = I[j].second;
  int c = I[i + 1].first, d = I[i + 1].second;
  int e = I[i].second;
  return (llint)(b - c + 1) * (b - c + 1) -
         (llint)max(0, e - c + 1) * max(0, e - c + 1);
}

void compute(int l, int r, int optl, int optr, vector<llint> &dp_prev,
             vector<llint> &dp_curr) {
  if (l > r) return;
  int mid = (l + r) / 2;
  pair<llint, int> best = {INF, -1};

  for (int k = optl; k <= min(mid, optr); ++k)
    best = min(best, {dp_prev[k] + C(k, mid), k});

  dp_curr[mid] = best.first;
  compute(l, mid - 1, optl, best.second, dp_prev, dp_curr);
  compute(mid + 1, r, best.second, optr, dp_prev, dp_curr);
}

llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
  I = get_intervals(n, r, c);
  n = (int)I.size();

  vector<llint> dp_prev(n, 0), dp_curr(n, 0);
  for (int i = 0; i < n; ++i)
    dp_prev[i] =
        (llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1);
  for (int i = 1; i < k; ++i) {
    compute(0, n - 1, 0, n - 1, dp_prev, dp_curr);
    swap(dp_prev, dp_curr);
  }

  return dp_prev[n - 1];
}

Compilation message (stderr)

aliens.cpp: In function 'llint C(int, int)':
aliens.cpp:56:7: warning: unused variable 'a' [-Wunused-variable]
   int a = I[j].first, b = I[j].second;
       ^
aliens.cpp:57:27: warning: unused variable 'd' [-Wunused-variable]
   int c = I[i + 1].first, d = I[i + 1].second;
                           ^

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