Submission #799787

#	Time	Username	Problem	Language	Result	Execution time	Memory
799787		NeroZein	Aliens (IOI16_aliens)	C++17	12 / 100	128 ms	2316 KiB

aliens

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

using namespace std;

const int N = 503;
const long long INF = 1e15;

long long dp[N][N];

long long bt (int id, int rem, const vector<pair<int, int>>& pts, const int& n, const int& m) {
  if (rem < 0) {
    return INF;
  }
  if (id == n) {
    return 0;
  }
  long long& ret = dp[id][rem];
  if (ret != -1) {
    return ret;
  }
  ret = INF; 
  int mn = m, mx = -m;
  for (int j = id; j < n; ++j) {
    auto [r, c] = pts[j];
    mn = min({mn, r, c});
    mx = max({mx, r, c});
    ret = min(ret, bt(j + 1, rem - 1, pts, n, m) + (mx - mn + 1) * (mx - mn + 1));
  }
  return ret;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
  vector<pair<int, int>> pts(n);
  for (int i = 0; i < n; ++i) {
    pts[i] = {r[i], c[i]};
  }
  sort(pts.begin(), pts.end(), [&](pair<int,int> i, pair<int,int> j) {
    return max(i.first, i.second) < max(j.first, j.second);
  });
  memset(dp, -1, sizeof dp);
  return bt(0, k, pts, n, m);
}

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