Submission #1023140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023140		huutuan	Aliens (IOI16_aliens)	C++14	100 / 100	171 ms	15284 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf=1e18;

struct Line{
   mutable int k, m, p;
   mutable int cnt;
   Line (int _k=0, int _m=0, int _p=0, int _cnt=0){ k=_k, m=_m, p=_p, cnt=_cnt; }
   bool operator<(const Line &a) const { return k<a.k; }
};

struct LineContainer: vector<Line>{
   int div(int x, int y){
      return x/y-((x^y)<0 && x%y);
   }
   bool isect(iterator x, iterator y){
      if (y==end()) return x->p=inf, 0;
      if (x->k==y->k) x->p=x->m>=y->m?inf:-inf;
      else x->p=div(y->m-x->m, x->k-y->k);
      return x->p>=y->p;
   }
   void add(int k, int m, int cnt){
      k=-k, m=-m;
      emplace_back(k, m, 0, cnt);
      auto z=prev(end()), y=z++, x=y;
      while (isect(y, z)) z=erase(z);
      if (x!=begin() && isect(--x, y)) isect(x, erase(y));
      while ((y=x)!=begin() && (--x)->p>=y->p) isect(x, erase(y));
   }
   int id=0;
   pair<int, int> query(int x){
      while (id+1<(int)size() && (*this)[id].k*x+(*this)[id].m<=(*this)[id+1].k*x+(*this)[id+1].m) ++id;
      return {(-(*this)[id].k)*x+(-(*this)[id].m), (*this)[id].cnt};
   }
};

pair<int, int> dp(int n, vector<pair<int, int>> &v2, int pen){
   vector<pair<int, int>> f(n+1, {inf, inf});
   LineContainer cht;
   f[0]={0, 0};
   for (int i=1; i<=n; ++i){
      int x=-2*v2[i-1].first, y=v2[i-1].first*v2[i-1].first;
      if (i!=1 && v2[i-2].second>v2[i-1].first) y-=(v2[i-2].second-v2[i-1].first)*(v2[i-2].second-v2[i-1].first);
      if (f[i-1].first<inf) cht.add(x, y+f[i-1].first, f[i-1].second);
      if (cht.size()){
         auto tmp=cht.query(v2[i-1].second);
         f[i]=min(f[i], {v2[i-1].second*v2[i-1].second+tmp.first+pen, tmp.second+1});
      }
   }
   return f[n];
}

long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
   vector<pair<int, int>> v;
   for (int i=0; i<n; ++i){
      v.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
   }
   sort(v.begin(), v.end());
   vector<pair<int, int>> v2;
   for (int i=0; i<(int)v.size(); ++i){
      int j=i;
      while (j+1<(int)v.size() && v[j+1].first==v[i].first) ++j;
      if (v2.empty() || v2.back().second<v[j].second) v2.push_back(v[j]);
      i=j;
   }
   n=v2.size();
   for (auto &i:v2) ++i.second;
   if (n<=k) return dp(n, v2, 0).first;
   int L=1, R=1e12;
   while (L<=R){
      int mid=(L+R)>>1;
      if (dp(n, v2, mid).second<=k) R=mid-1;
      else L=mid+1;
   }
   auto tmp1=dp(n, v2, L);
   if (tmp1.second==k) return tmp1.first-k*L;
   auto tmp2=dp(n, v2, R);
   int x1=tmp1.second, y1=tmp1.first;
   int x2=tmp2.second, y2=tmp2.first+tmp2.second;
   // slope = (y2 - y1) / (x2 - x1)
   int x=k;
   int y=y1+(y2-y1)/(x2-x1)*(x-x1);
   return y-k*L;
   // vector<vector<int>> f(n+1, vector<int>(k+1, inf));
   // vector<LineContainer> cht(k);
   // f[0][0]=0;
   // for (int i=1; i<=n; ++i){
   //    int x=-2*v2[i-1].first, y=v2[i-1].first*v2[i-1].first;
   //    if (i!=1 && v2[i-2].second>v2[i-1].first) y-=(v2[i-2].second-v2[i-1].first)*(v2[i-2].second-v2[i-1].first);
   //    for (int j=1; j<=k; ++j){
   //       if (f[i-1][j-1]!=inf) cht[j-1].add(x, y+f[i-1][j-1]);
   //       if (cht[j-1].size()) f[i][j]=min(f[i][j], v2[i-1].second*v2[i-1].second+cht[j-1].query(v2[i-1].second));
   //    }
   // }
   // return *min_element(f[n].begin(), f[n].end());
}

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