Submission #258977

#	Time	Username	Problem	Language	Result	Execution time	Memory
258977		ipaljak	Aliens (IOI16_aliens)	C++14	25 / 100	174 ms	2304 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 = 505;
const int MAXM = 1005;
const llint INF = 1e17;

llint dp[MAXN][MAXN];

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;
}

llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  auto I = get_intervals(n, r, c);
  n = (int)I.size();
  for (int i = 1; i <= n; ++i) dp[i][0] = INF;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      int a = I[i - 1].first, b = I[i - 1].second;
      dp[i][j] = (llint)(b - I[0].first + 1) * (b - I[0].first + 1);
      for (int ii = 1; ii < i; ++ii) {
        int c = I[ii].first, d = I[ii].second, e = I[ii - 1].second;
        dp[i][j] =
            min(dp[i][j], dp[ii][j - 1] + (llint)(b - c + 1) * (b - c + 1) -
                              (llint)max(0, e - c + 1) * max(0, e - c + 1));
      }
    }
  }

  return dp[n][k];
}

Compilation message (stderr)

aliens.cpp: In function 'llint take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:64:30: warning: unused variable 'd' [-Wunused-variable]
         int c = I[ii].first, d = I[ii].second, e = I[ii - 1].second;
                              ^
aliens.cpp:61:11: warning: unused variable 'a' [-Wunused-variable]
       int a = I[i - 1].first, b = I[i - 1].second;
           ^

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