Submission #799785

#	Time	Username	Problem	Language	Result	Execution time	Memory
799785		NeroZein	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	2260 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<int>& r, const vector<int>& c, 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) {
    mn = min({mn, r[j], c[j]});
    mx = max({mx, r[j], c[j]});
    ret = min(ret, bt(j + 1, rem - 1, r, c, 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) {
  memset(dp, -1, sizeof dp);
  return bt(0, k, r, c, n, m);
}

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