Submission #69476

#	Time	Username	Problem	Language	Result	Execution time	Memory
69476		funcsr	Aliens (IOI16_aliens)	C++17	60 / 100	2064 ms	617532 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<long long, long long> P;
double intersect(P s, P t) { return (double)(t._2-s._2)/(double)(s._1-t._1); }

struct CHT {
  vector<P> ps;
  int h = 0;
  void add(long long x, long long y) {
    auto c = P(x, y);
    while (ps.size() >= 2) {
      auto a = ps[ps.size()-2], b = ps[ps.size()-1];
      if (intersect(b,c) < intersect(a,c) && intersect(a,c) < intersect(a,b)) break;
      else ps.pop_back();
      h = ::min(h, max(0, (int)ps.size()-1));
    }
    ps.pb(P(x, y));
  }
  long long min(long long x) {
    if (ps.empty()) return INF;
    while (h+1<ps.size() && intersect(ps[h+1], ps[h]) >= x) h++;
    return ps[h]._1*x+ps[h]._2;
  }
};

CHT dp[4001];
int L[100000], R[100000];

long long take_photos(int N, int M, int K, vector<int> RR, vector<int> CC) {
  vector<P> ins;
  rep(i, N) {
    int l = min(RR[i], CC[i]), r = max(RR[i], CC[i]);
    ins.pb(P(l, -r));
  }
  sort(all(ins));
  vector<P> ins2;
  int lp = -1;
  for (P p : ins) {
    int l = p._1, r = -p._2;
    if (lp < r) {
      ins2.pb(P(l, r));
      lp = r;
    }
  }
  swap(ins, ins2);
  N = ins.size();
  rep(i, N) L[i] = ins[i]._1, R[i] = ins[i]._2;
  //rep(i, N) cout << "["<<ins[i]._1<<","<<ins[i]._2<<"]\n";
  K = min(K, N);

  dp[0].add(L[0], 1LL*L[0]*L[0]);
  long long ans = INF;
  rep(x, N) {
    for (int k=K-1; k>=0; k--) {
      long long m = dp[k].min(-2LL*(R[x]+1));
      if (m == INF) continue;
      m += 1LL*(R[x]+1)*(R[x]+1);
      // cout<<"dp["<<x<<"]["<<k+1<<"]="<<m<<"\n";
      if (x==N-1) {
        ans = min(ans, m);
      }
      else {
        long long overlap = 0;
        if (L[x+1]<=R[x]) overlap = 1LL*(R[x]-L[x+1]+1)*(R[x]-L[x+1]+1);
        dp[k+1].add(L[x+1], m+1LL*L[x+1]*L[x+1]-overlap);
      }
    }
  }
  return ans;
}

Compilation message (stderr)

aliens.cpp: In member function 'long long int CHT::min(long long int)':
aliens.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (h+1<ps.size() && intersect(ps[h+1], ps[h]) >= x) h++;
            ~~~^~~~~~~~~~

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