Submission #249132

#	Time	Username	Problem	Language	Result	Execution time	Memory
249132		fedoseevtimofey	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	384 KiB

aliens

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;

#include "aliens.h"
 
const ll Inf = 1e18;

struct Line {
  ll k, b;
  Line(ll k, ll b) : k(k), b(b) {}
  ll f(ll x) {
    return x * k + b;
  }
};

ld div_floor(ll a, ll b) {
  return (ld)a / b;
}

ld inter(Line a, Line b) {
  return div_floor(b.b - a.b, a.k - b.k);
}

struct CHT {
  vector <Line> lines;
  void add(Line a) {  
    while (lines.size() >= 2) {
      Line b = lines.rbegin()[0];
      Line c = lines.rbegin()[1];
      if (inter(a, c) < inter(b, c)) lines.pop_back();
      else break;
    }
    lines.push_back(a);
  }
  ll get(ll x) {
    int l = -1, r = (int)lines.size() - 1;
    while (r - l > 1) {
      int m = (l + r) >> 1;
      if (lines[m].f(x) >= lines[m + 1].f(x)) l = m;
      else r = m;
    }
    return lines[r].f(x);
  }
};  
  
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
  vector <pair <int, int>> seg;
  for (int i = 0; i < n; ++i) {
    int cr = r[i], cc = c[i];
    if (cc - cr < 0) {
      swap(cr, cc);
    }
   seg.push_back({cr, cc});
  }
  sort(seg.begin(), seg.end(), [&] (pair <int, int> f, pair <int, int> s) {
    if (f.second != s.second) return f.second < s.second;
    else return f.first > s.first;
  });
  {
    vector <pair <int, int>> nseg;
    int mn_l = m;
    for (int i = (int)seg.size() - 1; i >= 0; --i) {
      if (seg[i].first < mn_l) {
        nseg.push_back(seg[i]);
        mn_l = seg[i].first;
      }
    }
    seg = nseg;
    reverse(seg.begin(), seg.end());
  }
  n = seg.size();

  vector <ll> delta(n);
  for (auto &p : seg) ++p.second;
  for (int i = 1; i < n; ++i) {
    int inter = max(0, seg[i - 1].second - seg[i].first); 
    delta[i] = -(ll)inter * inter;
  } 
  for (int i = 0; i < n; ++i) {
    delta[i] += (ll)seg[i].first * seg[i].first;
  } 
  auto get = [&] (ll pen) {
    vector <ll> dp(n + 1);
    dp[0] = 0;
    CHT c;
    c.add({-2 * seg[0].first, dp[0] + delta[0]});
    for (int i = 1; i <= n; ++i) {
      dp[i] = pen + (ll)seg[i - 1].second * seg[i - 1].second + c.get(seg[i - 1].second);
      if (i < n) c.add({-2 * seg[i].first, dp[i] + delta[i]}); 
    }
    int cnt = 0;
    int who = n;
    for (int i = n - 1; i >= 0; --i) {
      if (dp[who] == pen + (ll)seg[who - 1].second * seg[who - 1].second - 2LL * seg[who - 1].second * seg[i].first + dp[i] + delta[i]) {
        ++cnt;
        who = i;
      }
    }
    return make_pair(dp[n], cnt);
  };

  ll L = 0, R = 1e18;
  while (R - L > 1) {
    ll M = (L + R) / 2;
    auto cur = get(M);
    if (cur.second > k) L = M;
    else R = M;
  } 
  auto ans = get(R);
  return ans.first - ans.second * R;
}   
 
#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> r(n), c(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i] >> c[i];
  }
  long long ans = take_photos(n, m, k, r, c);
  cout << ans << '\n';  
}
#endif

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