Submission #1081142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081142		erray	Aliens (IOI16_aliens)	C++17	25 / 100	2027 ms	22364 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi16d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

long long take_photos(int N, int M, int K, std::vector<int> R_, std::vector<int> C) {
  vector<array<int, 2>> ranges;
  for (int i = 0; i < N; ++i) {
    if (R_[i] - C[i] > 0) {
      ranges.push_back({C[i], R_[i] + 1});
    } else {
      ranges.push_back({R_[i], C[i] + 1});
    }
  }
  sort(ranges.begin(), ranges.end(), [&](auto x, auto y) {
    return array<int, 2>{x[0], -x[1]} < array<int, 2>{y[0], -y[1]};
  });
  vector<int> L, R;
  int mx_r = -1;
  for (auto[l, r] : ranges) {
    if (mx_r < r) {
      mx_r = r;
      L.push_back(l);
      R.push_back(r);
    }
  }
  N = int(L.size());
  K = min(K, N);
  auto S = [&](int x) {
    return int64_t(x) * x;
  };
  int64_t inf = int64_t(M) * M;
  vector<vector<int64_t>> best(N + 1, vector<int64_t>(K + 1, inf));
  best[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
      for (int n = i; n < N; ++n) {
        int64_t cost = best[i][j] + S(R[n] - L[i]) - (n + 1 < N && R[n] > L[n + 1] ? S(R[n] - L[n + 1]) : 0);
        best[n + 1][j + 1] = min(best[n + 1][j + 1], cost);
      }
    }
  }
  int64_t ans = inf;
  for (int i = 0; i <= K; ++i) ans = min(ans, best[N][i]);
  return ans;
}

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