Submission #837379

#	Time	Username	Problem	Language	Result	Execution time	Memory
837379		erdemkiraz	Aliens (IOI16_aliens)	C++17	60 / 100	2093 ms	358928 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;
 
vector<vector<ll>> dp;

class line{ public:
    ll m, n;
    line(ll m, ll n) {
        this -> m = m;
        this -> n = n;
    }
    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(ll m, ll n) {
        while(ptr + 1 < v.size()) {
            line l1 = v[v.size() - 2];
            line l2 = v[v.size() - 1];
            line l3 = {m, n};
            if(l1.intersect(l2) < l1.intersect(l3))
                break;
            v.pop_back();
        }
        v.push_back({m, n});
    }
    ll query(int 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;
    }
};
 
ll take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
  n = nn;
  m = mm;
  k = kk;
 
  for(int i = 0; i < n; i++) {
    if(r[i] > c[i]) {
      swap(r[i], c[i]);
    }
    at[r[i] + 1] = max(at[r[i] + 1], c[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;
 
  dp.resize(m + 1, vector<ll>(k + 1, 1e18));

  for(int i = 0; i <= k; i++) {
    dp[0][i] = 0;
  }

  for(int rem = 1; rem <= k; rem++) {

    vector<ll> cost(m + 1);

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

    convex trick;
    trick.init();

    for(int j = 1; j <= m; j++) {
      trick.add(- 2 * a[j], cost[j]);

      dp[j][rem] = trick.query(b[j]) + b[j] * b[j];
      // for(int i = j; i >= 1; i--) {
        // dp[j][rem] = min(dp[j][rem], cost[i] + b[j] * b[j] - 2 * a[i] * b[j]);
      // }
    }
  }
 
  ll ans = dp[m][k];
 
  return ans;
}

Compilation message (stderr)

aliens.cpp: In member function 'void convex::add(ll, ll)':
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 'll convex::query(int)':
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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40