제출 #172241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172241		golikovnik	Aliens (IOI16_aliens)	C++14	60 / 100	2065 ms	5604 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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]]);
    }
  }
  auto relax = [&](i64& x, i64 y) {
    if (y < x) {
      x = y;
      return true;
    }
    return false;
  };
  auto sqr = [](i64 x) {
    return x * x;
  };
  n = (int) a.size();
  i64 const INF = (i64) 1e18;
  mx = min(mx, n);
  vector<i64> dp(n + 1, INF);
  dp[0] = 0;
  for (int k = 0; k < mx; ++k) {
    vector<i64> new_dp(n + 1, INF);
    new_dp[0] = 0;
    function<void(int, int, int, int)> solve =
            [&](int l, int r, int ll, int rr) {
      if (l > r) {
        return;
      }
      int m = (l + r) / 2;
      int opt = -1;
      for (int j = ll; j <= min(m, rr); ++j) {
        auto his_c = a[j].c;
        auto my_area = sqr(a[m].r - his_c + 1);
        auto inter_area = !j ? 0 : sqr(
                max<i64>(0, a[j - 1].r - his_c + 1));
        if (relax(new_dp[m + 1], dp[j] + my_area - inter_area)) {
          opt = j;
        }
      }
      solve(l, m - 1, ll, opt);
      solve(m + 1, r, max(opt, 0), rr);
    };
    solve(0, n - 1, 0, n);
    dp.swap(new_dp);
  }
  return dp.back();
}

//int main() {
//  vector<int> r{0, 2, 3};
//  vector<int> c{2, 2, 1};
//  int n = (int) r.size();
//  int m = -1;
//  int k = n;
//  cout << take_photos(n, m, k, r, c) << '\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