Submission #837566

#	Time	Username	Problem	Language	Result	Execution time	Memory
837566		erdemkiraz	Aliens (IOI16_aliens)	C++17	4 / 100	4 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> ii;
 
const int M = 1e6 + 5;
 
int n, m, k;
int at[M];

vector<int> ats;
vector<ll> a, b;

class line{ public:
    double m, n;
    int idx;
    line(double m, double n, int idx) {
        this -> m = m;
        this -> n = n;
        this -> idx = idx;
    }
    double intersect(line oth) {
        return (double) (n - oth.n) / (oth.m - m);
    }
};

class convex{ public:
    int ptr;
    vector < line > v;
    void init() {
        ptr = 0;
        v.clear();
    }
    void add(double m, double n, int idx) {
        while(ptr + 1 < v.size()) {
            line l1 = v[v.size() - 2];
            line l2 = v[v.size() - 1];
            line l3 = {m, n, idx};
            if(l1.intersect(l2) < l1.intersect(l3))
                break;
            v.pop_back();
        }
        v.push_back({m, n, idx});
    }
    pair<double, int> query(double x) {
        while(ptr + 1 < v.size()) {
            line l1 = v[ptr];
            line l2 = v[ptr + 1];
            if(l1.intersect(l2) > x)
                break;
            ptr++;
        }
        return {v[ptr].m * x + v[ptr].n, v[ptr].idx};
    }
};

vector<int> go;

tuple<double, int, ll> get(double discourage) {
  vector<double> dp(m + 1, 1e18);

  dp[0] = 0;

  vector<double> cost(m + 1);

  convex trick;
  trick.init();

  for(int i = 1; i <= m; i++) {
    ll len = max(0LL, b[i - 1] - a[i]);
    cost[i] = dp[i - 1] + a[i] * a[i] - len * len;

    trick.add(- 2 * a[i], cost[i], i);

    auto [res, idx] = trick.query(b[i]);

    dp[i] = res + b[i] * b[i] + discourage;
    go[i] = idx;
  }

  int j = m, cnt = 0;
  ll ans = 0;

  while(j > 0) {
    cnt++;

    int i = go[j];

    ll len = b[j] - a[i];
    ll prev = max(0LL, b[i - 1] - a[i]);
    // printf("i = %d j = %d\n", i, j);
    ans += len * len - prev * prev;

    j = i - 1;
  }

  // printf("discourage = %.3lf cnt = %d dp = %.3lf real = %lld\n", discourage, cnt, dp[m], ans);

  return {dp[m], cnt, ans};
}
 
ll take_photos(int nn, int mm, int kk, vector<int> rr, vector<int> cc) {
  n = nn;
  m = mm;
  k = kk;
 
  for(int i = 0; i < n; i++) {
    if(rr[i] > cc[i]) {
      swap(rr[i], cc[i]);
    }
    at[rr[i] + 1] = max(at[rr[i] + 1], cc[i] + 2);
  }

  a.push_back(0);
  b.push_back(0);

  for(int i = 1; i <= m + 1; i++) {
    if(at[i]) {
      if(!ats.empty() and ats.back() >= at[i]) {
        continue;
      }
      ats.push_back(at[i]);

      a.push_back(i);
      b.push_back(at[i]);
    }
  }

  m = (int) a.size() - 1;

  k = min(k, m);

  if(k == 1 or m == 1) {
    return (b.back() - a[1]) * (b.back() - a[1]);
  }

  go.resize(m + 1);

  double l = 0, r = 1e18;

  ll ans = 1e18;

  for(int it = 0; it < 300; it++) {
    double m = (l + r) / 2;

    auto [_, used, res] = get(m);

    if(used > k) {
      l = m;
    }
    else {
      ans = min(ans, res);
      r = m;
    }
  }

  return ans;
}

Compilation message (stderr)

aliens.cpp: In member function 'void convex::add(double, double, int)':
aliens.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(ptr + 1 < v.size()) {
      |               ~~~~~~~~^~~~~~~~~~
aliens.cpp: In member function 'std::pair<double, int> convex::query(double)':
aliens.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(ptr + 1 < v.size()) {
      |               ~~~~~~~~^~~~~~~~~~

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