Submission #837643

#	Time	Username	Problem	Language	Result	Execution time	Memory
837643		erdemkiraz	Aliens (IOI16_aliens)	C++17	4 / 100	1 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:
    ll m, n;
    int cnt;
    line(ll m, ll n, int cnt) {
        this -> m = m;
        this -> n = n;
        this -> cnt = cnt;
    }
    long double intersect(line oth) {
        return (long double) (n - oth.n) / (oth.m - m);
    }
};

class convex{ public:
    int ptr;
    vector < line > v;
    void init() {
        ptr = 0;
        v.clear();
    }
    void add(ll m, ll n, int cnt) {
        while(ptr + 1 < v.size()) {
            line l1 = v[v.size() - 2];
            line l2 = v[v.size() - 1];
            line l3 = {m, n, cnt};
            if(l1.intersect(l2) < l1.intersect(l3))
                break;
            v.pop_back();
        }
        v.push_back({m, n, cnt});
    }
    pair<ll, int> query(ll 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].cnt};
    }
};

vector<int> go;

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

  dp[0] = 0;

  vector<ll> 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], go[i - 1] + 1);

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

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

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

  ll ans = dp[m] - go[m] * discourage;

  return {dp[m], go[m], 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);

  ll l = 0, r = 1.001e12;

  ll ans = 1e18;

  while(l < r) {
    ll m = (l + r) / 2;

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

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

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

  ans = min(ans, res);

  return ans;
}

Compilation message (stderr)

aliens.cpp: In member function 'void convex::add(ll, ll, 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<long long int, int> convex::query(ll)':
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