Submission #392626

#	Time	Username	Problem	Language	Result	Execution time	Memory
392626		ivan_tudor	Aliens (IOI16_aliens)	C++14	100 / 100	173 ms	9004 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
struct CHT{
  //TODO
  struct Line{
    long long a, b;
    long long id;
    long long operator ()(long long x) const{
      return 1LL * a * x + b;
    }
  };
  deque<Line> dq;
  CHT(){
    dq.clear();
  }
  bool IntersectX(Line l1, Line l2, Line l3){ // daca l2 e scoasa ca minim de l1 si l3
    return (l2.b - l3.b) *(l2.a - l1.a) <= (l1.b - l2.b) *(l3.a - l2.a);
  }
  void AddLine(Line l){
    while(dq.size() > 1 && IntersectX(dq.end()[-2], dq.end()[-1], l))
      dq.pop_back();
    dq.push_back(l);
  }
  pair<long long, int> getmin(long long x){
    while(dq.size() > 1 && dq[0](x) >= dq[1](x))
      dq.pop_front();
    return {dq[0](x), dq[0].id};
  }
};
const long long N = 100005;
struct points{
  long long l, c;
  bool operator <(points oth) const{
    if(l == oth.l)
      return c > oth.c;
    return l < oth.l;
  }
};
points p[N];
long long dp[N], cnt[N];
void makedp(long long n, long long lambda){
  CHT cht;
  for(long long i = 1; i<=n; i++){
    long long extracoef = max(0LL, p[i - 1].c - p[i].l + 1);
    cht.AddLine({-2LL * p[i].l, 1LL * dp[i - 1] + 1LL * p[i].l * p[i].l - extracoef * extracoef, i-1});
    pair<long long, int> dpr = cht.getmin(p[i].c + 1);
    cnt[i] = cnt[dpr.second] + 1;
    dp[i] = dpr.first + lambda + 1LL * (p[i].c + 1) * (p[i].c + 1);
  }
}
long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> columns) {
  for(long long i = 0; i < n; i++){
    long long l = rows[i], c = columns[i];
    l++;
    c++;
    if(l > c)
      swap(l, c);
    p[i+1] = {l, c};
  }
  sort(p + 1, p + n + 1);
  long long maxc = 0;
  vector<points> noup;
  for(long long i = 1; i<=n;){
    long long j = i;
    while(j <=n && p[j].l == p[i].l)
      j++;
    if(p[i].c > maxc){
      noup.push_back(p[i]);
      maxc = p[i].c;
    }
    i = j;
  }
  n = noup.size();
  for(long long i = 1; i<=n; i++)
    p[i] = noup[i - 1];
  long long good = 0;
  for(long long p2 = 1LL<<50; p2>0; p2/=2){
    makedp(n, good + p2);
    if(cnt[n] >= k)
      good += p2;
  }
  makedp(n, good);
  return dp[n] - k * good;
}

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