Submission #1260464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260464		kunzaZa183	Aliens (IOI16_aliens)	C++20	100 / 100	129 ms	6204 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  vector<pair<int, int>> all;
  for (int i = 0; i < n; i++)
    all.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
  sort(all.begin(), all.end(), [&](pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first)
      return a.first < b.first;
    return a.second > b.second;
  });

  vector<pair<int, int>> segs;
  for (auto [l, r] : all) {
    if (segs.empty()) {
      segs.emplace_back(l, r);
    } else {
      auto [l2, r2] = segs.back();
      if (r2 < r)
        segs.emplace_back(l, r);
    }
  }

  auto sq = [&](ll x) { return x * x; };

  auto kill = [&](array<ll, 3> a, array<ll, 3> b, array<ll, 3> c) {
    return (a[1] - c[1]) * (b[0] - a[0]) <= (a[1] - b[1]) * (c[0] - a[0]);
  };

  ll binl = 0, binr = 1LL * m * m;
  n = (int)segs.size();

  while (binl < binr) {
    ll mid = (binl + binr) / 2;

    vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
    ct[0] = 0;

    deque<array<ll, 3>> lin;
    lin.push_back({-2 * (ll)segs[0].first,
                   dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first, 0LL});

    auto qry = [&](const array<ll, 3> &L, ll x) { return L[0] * x + L[1]; };

    for (int i = 1; i <= n; i++) {
      while (lin.size() > 1) {
        ll a = qry(lin[0], segs[i - 1].second);
        ll b = qry(lin[1], segs[i - 1].second);
        if (a > b) {
          lin.pop_front();
        } else if (a == b) {
          if (ct[lin[0][2]] >= ct[lin[1][2]])
            lin.pop_front();
          else
            break;
        } else {
          break;
        }
      }

      auto [mm, bb, in] = lin.front();

      dp[i] = (ll)segs[i - 1].second * mm + bb + sq(segs[i - 1].second) +
              2LL * (ll)segs[i - 1].second + 1 + mid;
      ct[i] = ct[in] + 1;

      if (i < n) {
        array<ll, 3> tmp = {
            -2 * (ll)segs[i].first,
            dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) -
                sq(max(0, segs[i - 1].second - segs[i].first + 1)),
            (ll)i};
        while (lin.size() >= 2 && kill(lin[lin.size() - 2], lin.back(), tmp)) {
          lin.pop_back();
        }
        lin.push_back(tmp);
      }
    }

    if (ct[n] > k)
      binl = mid + 1;
    else
      binr = mid;
  }

  vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
  ct[0] = 0;

  deque<array<ll, 3>> lin;
  lin.push_back({-2 * (ll)segs[0].first,
                 dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first, 0LL});

  auto qry = [&](const array<ll, 3> &L, ll x) { return L[0] * x + L[1]; };

  for (int i = 1; i <= n; i++) {
    while (lin.size() > 1) {
      ll a = qry(lin[0], segs[i - 1].second);
      ll b = qry(lin[1], segs[i - 1].second);
      if (a > b) {
        lin.pop_front();
      } else if (a == b) {
        if (ct[lin[0][2]] >= ct[lin[1][2]])
          lin.pop_front();
        else
          break;
      } else {
        break;
      }
    }

    auto [mm, bb, in] = lin.front();

    dp[i] = (ll)segs[i - 1].second * mm + bb + sq(segs[i - 1].second) +
            2LL * (ll)segs[i - 1].second + 1 + binl;
    ct[i] = ct[in] + 1;

    if (i < n) {
      array<ll, 3> tmp = {
          -2 * (ll)segs[i].first,
          dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) -
              sq(max(0, segs[i - 1].second - segs[i].first + 1)),
          (ll)i};
      while (lin.size() >= 2 && kill(lin[lin.size() - 2], lin.back(), tmp)) {
        lin.pop_back();
      }
      lin.push_back(tmp);
    }
  }

  return dp.back() - 1LL * k * binl;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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