Submission #555756

#	Time	Username	Problem	Language	Result	Execution time	Memory
555756		MilosMilutinovic	Aliens (IOI16_aliens)	C++14	25 / 100	2085 ms	564 KiB

aliens

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

using namespace std;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  for (int i = 0; i < n; i++) {
    if (r[i] > c[i]) {
      swap(r[i], c[i]);
    }
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    if (r[i] != r[j]) {
      return r[i] < r[j];
    } else {
      return c[i] > c[j];
    }
  });
  vector<pair<int, int>> pts;
  int mx = -1;
  for (int id = 0; id < n; id++) {
    int i = order[id];
    if (c[i] <= mx) {
      continue;
    } else {
      mx = max(mx, c[i]);
      pts.emplace_back(r[i], c[i]);
    }
  }
  n = (int) pts.size();
  for (int i = 0; i < n; i++) {
    r[i] = pts[i].first;
    c[i] = pts[i].second;
  }
  vector<long long> w(n);
  for (int i = 1; i < n; i++) {
    long long d = c[i - 1] - r[i] + 1;
    if (d < 0) {
      continue;
    }
    w[i] = d * d;
  }
  const long long inf = (long long) 1e18;
  vector<long long> dp(n, inf);
  for (int t = 0; t < k; t++) {
    vector<long long> new_dp(n, inf);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= i; j++) {
        long long d = c[i] - r[j] + 1;
        long long ft = d * d;
        if (j > 0) {
          ft += dp[j - 1] - w[j];
        }
        new_dp[i] = min(new_dp[i], ft);
      }
    }
    swap(dp, new_dp);
  }
  return dp[n - 1];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6

*/

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