Submission #469108

#	Time	Username	Problem	Language	Result	Execution time	Memory
469108		flashmt	Aliens (IOI16_aliens)	C++17	25 / 100	2074 ms	22220 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
  vector<pair<int, int>> a = {{-1, -1}};
  for (int i = 0; i < n; i++)
    a.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1});
  sort(begin(a), end(a));

  int cur = 0;
  for (int i = 1; i <= n; i++)
    if (a[i].first == a[cur].first) a[cur].second = a[i].second;
    else if (a[i].second > a[cur].second) a[++cur] = a[i];
  n = cur;

  auto sqr = [&](int x)
  {
    return 1LL * x * x;
  };

  vector<vector<long long>> f(k + 1, vector<long long>(n + 1, oo));
  f[0][0] = 0;
  for (int i = 1; i <= k; i++)
    for (int j = 1; j <= n; j++)
    {
      f[i][j] = oo;
      for (int jj = 0; jj < j; jj++)
      {
        long long cost = sqr(a[j].second - a[jj + 1].first);
        if (a[jj].second > a[jj + 1].first)
          cost -= sqr(a[jj].second - a[jj + 1].first);
        f[i][j] = min(f[i][j], f[i - 1][jj] + cost);
      }
    }

  long long ans = oo;
  for (int i = 1; i <= k; i++)
    ans = min(ans, f[i][n]);
  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