Advertisement
mickypinata

AJPrakarn-T002: Aliens

Dec 3rd, 2021
638
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. struct linear {
  7.     lli m, c;
  8.     linear(): m(0), c(0) {};
  9.     linear(lli m, lli c): m(m), c(c) {};
  10. };
  11.  
  12. #define f first
  13. #define s second
  14. typedef pair<int, int> pii;
  15. typedef pair<linear, lli> pLl;
  16.  
  17. const int N = 4000 + 5;
  18. const int K = 500 + 5;
  19.  
  20. deque<pLl> cht;
  21. vector<pii> coor(1, pii(-1, -1));
  22. lli dp[N][K];
  23. pii tmp[N];
  24.  
  25. bool comp(const pii &lhs, const pii &rhs){
  26.     if(lhs.f != rhs.f){
  27.         return lhs.f < rhs.f;
  28.     }
  29.     return lhs.s > rhs.s;
  30. }
  31.  
  32. lli intersect(linear a, linear b){
  33.     lli x = b.c - a.c;
  34.     lli y = a.m - b.m;
  35.     return (lli)ceil((double)x / y);
  36. }
  37.  
  38. void chtInsert(linear l){
  39.     while(!cht.empty() && cht.back().f.m == l.m){
  40.         if(cht.back().f.c > l.c){
  41.             cht.pop_back();
  42.             chtInsert(l);
  43.         }
  44.         return;
  45.     }
  46.     while(!cht.empty() && cht.back().s >= intersect(cht.back().f, l)){
  47.         cht.pop_back();
  48.     }
  49.     if(cht.empty()){
  50.         cht.emplace_back(l, 0);
  51.     } else {
  52.         cht.emplace_back(l, intersect(cht.back().f, l));
  53.     }
  54. }
  55.  
  56. lli chtQuery(lli x){
  57.     while(cht.size() > 1 && next(cht.begin()) -> s <= x){
  58.         cht.pop_front();
  59.     }
  60.     linear a = cht.front().f;
  61.     return a.m * x + a.c;
  62. }
  63.  
  64. int main(){
  65.  
  66.     int n, sz, parts;
  67.     scanf("%d%d%d", &n, &sz, &parts);
  68.     for(int i = 1; i <= n; ++i){
  69.         scanf("%d%d", &tmp[i].f, &tmp[i].s);
  70.         if(tmp[i].f > tmp[i].s){
  71.             swap(tmp[i].f, tmp[i].s);
  72.         }
  73.     }
  74.     sort(tmp + 1, tmp + n + 1, comp);
  75.     for(int i = 1; i <= n; ++i){
  76.         if(tmp[i].f >= coor.back().f && tmp[i].s <= coor.back().s){
  77.             continue;
  78.         }
  79.         coor.push_back(tmp[i]);
  80.     }
  81.     n = (int)coor.size() - 1;
  82.     for(int i = 1; i <= n; ++i){
  83.         dp[i][0] = 1e18;
  84.     }
  85.     for(int p = 1; p <= parts; ++p){
  86.         cht.clear();
  87.         for(int i = 1; i <= n; ++i){
  88.             lli camInter = max(0, coor[i - 1].s - coor[i].f + 1);
  89.             chtInsert(linear(-2 * coor[i].f, (lli)coor[i].f * coor[i].f - 2 * coor[i].f - camInter * camInter + dp[i - 1][p - 1]));
  90.             dp[i][p] = (lli)coor[i].s * coor[i].s + 2 * coor[i].s + 1 + chtQuery(coor[i].s);
  91.         }
  92.     }
  93.     cout << dp[n][parts];
  94.  
  95.     return 0;
  96. }
  97.  
Advertisement
RAW Paste Data Copied
Advertisement