Submission #392596

#	Time	Username	Problem	Language	Result	Execution time	Memory
392596		ivan_tudor	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	204 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;
  bool IntersectX(Line l1, Line l2, Line l3){ // daca l2 e scoasa ca minim de l1 si l3
    return 1LL * (l2.b - l1.b) * (l2.a - l3.a) <= (l1.a - l2.a) * (l3.b - l2.b);
  }
  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 - 2LL*p[i].l, i-1});
    pair<long long, int> dpr = cht.getmin(p[i].c);
    cnt[i] = cnt[dpr.second] + 1;
    dp[i] = dpr.first + lambda + 1LL * p[i].c * p[i].c + 2LL*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 st = 0, dr = 1LL<<60;
  while(st < dr){
    long long mid = (st + dr)/2;
    makedp(n, mid);
    if(cnt[n] <= k){
      dr = mid - 1;
    }
    else
      st = mid + 1;
  }
  makedp(n, st);
  return dp[n] - k* st;
}

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