Submission #435853

#	Time	Username	Problem	Language	Result	Execution time	Memory
435853		Hegdahl	Aliens (IOI16_aliens)	C++17	4 / 100	10 ms	204 KiB

aliens

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

using namespace std;
using ll = long long;

int n, m, k;
vector<ar<ll, 2>> a;

const ll INF = 1LL<<60;

ll sq(ll a) { return a*a; }

pair<ll, int> solve(ll penalty) {

  vector<ll> cost(n+1, INF);
  vector<int> used(n+1, 0);
  cost[0] = 0;

  for (int i = 0; i < n; ++i) {
    int pr = i==0 ? -1 : a[i-1][1];

    int l = a[i][0], r = a[i][1];
    for (int j = i+1; j <= n; ++j) {
      r = a[j-1][1];
      ll c = cost[i] + sq(r-l+1) - sq(max(0, pr-l+1)) + penalty;
      if (c < cost[j]) {
        cost[j] = c;
        used[j] = used[i]+1;
      }
    }
  }

  return {cost[n], used[n]};
}

ll take_photos(int n_, int m_, int k_, vector<int> r_, vector<int> c_) {
  n = n_, m = m_, k = k_;
  a.resize(n);
  for (int i = 0; i < n; ++i)
    a[i] = {min(r_[i], c_[i]), max(r_[i], c_[i])};
  sort(a.begin(), a.end(), [&](auto p0, auto p1) {
      if (p0[0] != p1[0]) return p0[0] < p1[0];
      return p0[1] > p1[1];
      });

  {
    decltype(a) na;
    int mxr = -1e9;
    for (int i = 0; i < n; ++i) {
      if (a[i][1] > mxr) {
        mxr = a[i][1];
        na.push_back(a[i]);
      }
    }
    a = move(na);
    n = (int)a.size();
  }

  ll ans = INF;

  ll lo = -INF, hi = INF;
  while (lo != hi) {
    ll ce = lo + (hi-lo)/2;
    auto [cost, used] = solve(ce);

    if (used > k) lo = ce+1;
    else {
      hi = ce;
      ans = min(ans, cost - used*ce);
    }
  }

  return ans;
}

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