Submission #172212

#	Time	Username	Problem	Language	Result	Execution time	Memory
172212		golikovnik	Aliens (IOI16_aliens)	C++14	0 / 100	2 ms	376 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]);
    }
    while (!a.empty() && a.back().c >= c[i]) {
      a.pop_back();
    }
    a.emplace_back(r[i], c[i]);
  }
  n = (int) a.size();
  i64 const INF = (i64) 1e18;
  mx = min(mx, n);
  vector<vector<i64>> dp(n + 1, vector<i64>(mx + 1, INF));
  dp[0][0] = 0;
  auto relax = [&](i64& x, i64 y) {
    if (y < x) {
      x = y;
    }
  };
  auto sqr = [](i64 x) {
    return x * x;
  };
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      for (int k = 1; k <= i + 1; ++k) {
        auto his_c = a[j].c;
        auto my_area = sqr(a[i].r - his_c + 1);
        auto inter_area = !j ? 0 : sqr(
                max<i64>(0, a[j - 1].r - his_c + 1));
        relax(dp[i + 1][k], dp[j][k - 1] + my_area - inter_area);
      }
    }
  }
  return *min_element(dp.back().begin(), dp.back().end());
}

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

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