Submission #94585

#	Time	Username	Problem	Language	Result	Execution time	Memory
94585		wxh010910	Aliens (IOI16_aliens)	C++17	100 / 100	114 ms	6364 KiB

aliens

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

using namespace std;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  vector<pair<int, int>> p(n);
  for (int i = 0; i < n; ++i) {
    p[i].first = min(r[i], c[i]);
    p[i].second = max(r[i], c[i]);
  }
  sort(p.begin(), p.end());
  {
    vector<pair<int, int>> new_p;
    for (int i = 0, j = 0; i < n; i = j) {
      while (j < n && p[j].first == p[i].first) {
        ++j;
      }
      if (new_p.empty() || p[j - 1].second > new_p.back().second) {
        new_p.push_back(p[j - 1]);
      }
    }
    swap(p, new_p);
    n = p.size();
  }
  k = min(k, n);
  vector<int> x(n), y(n);
  for (int i = 0; i < n; ++i) {
    x[i] = p[i].first;
    y[i] = p[i].second;
  }
  vector<long long> f(n + 1);
  vector<int> g(n + 1);
  auto sqr = [&](int x) {
    return (long long) x * x;
  };
  auto solve = [&](long long c) {
    vector<int> q(n + 1);
    int l = 0, r = 0;
    auto check = [&](int a, int b, int c) {
      return (f[a] + sqr(x[a]) - f[c] - sqr(x[c])) * (x[b] - x[c]) < (f[b] + sqr(x[b]) - f[c] - sqr(x[c])) * (x[a] - x[c]);
    };
    for (int i = 0; i < n; ++i) {
      while (r - l > 1 && check(i, q[r - 1], q[r - 2])) {
        --r;
      }
      q[r++] = i;
      while (r - l > 1 && f[q[l]] + sqr(y[i] - x[q[l]] + 1) > f[q[l + 1]] + sqr(y[i] - x[q[l + 1]] + 1)) {
        ++l;
      }
      f[i + 1] = f[q[l]] + sqr(y[i] - x[q[l]] + 1) + c;
      if (i + 1 < n && y[i] >= x[i + 1]) {
        f[i + 1] -= sqr(y[i] - x[i + 1] + 1);
      }
      g[i + 1] = g[q[l]] + 1;
    }
  };
  long long low = 0, high = 1ll << 40;
  while (low < high) {
    long long mid = low + high >> 1;
    solve(mid);
    if (g[n] <= k) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  solve(high);
  return f[n] - k * high;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:60:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     long long mid = low + high >> 1;
                     ~~~~^~~~~~

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