mickypinata

SMMR-T159: Election Campaign

Jul 28th, 2021 (edited)
662
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. const int N = 1000;
  7.  
  8. int arr[N + 1];
  9. lli dp[N + 1];
  10.  
  11. lli distance(int x, int y){
  12.     int diff = x - y;
  13.     return (lli)diff * diff;
  14. }
  15.  
  16. int main(){
  17.  
  18.     int nVertex, carCost;
  19.     scanf("%d%d", &nVertex, &carCost);
  20.     for(int i = 1; i <= nVertex; ++i){
  21.         scanf("%d", &arr[i]);
  22.     }
  23.  
  24.     sort(arr + 1, arr + nVertex + 1);
  25.  
  26.     dp[0] = 0;
  27.     for(int i = 1; i <= nVertex; ++i){
  28.         lli mn = 1e18;
  29.         for(int j = 1; j <= i; ++j){
  30.             mn = min(mn, dp[j - 1] + distance(arr[i], arr[j]) + carCost);
  31.         }
  32.         dp[i] = mn;
  33.     }
  34.     cout << dp[nVertex];
  35.  
  36.     return 0;
  37. }
  38.  
  39. // Convex Hull Trick Solution
  40. #include <bits/stdc++.h>
  41. using namespace std;
  42.  
  43. typedef long long lli;
  44.  
  45. struct linear {
  46.     lli m, c;
  47.     linear(): m(0), c(0) {};
  48.     linear(lli m, lli c): m(m), c(c) {};
  49. };
  50.  
  51. const int N = 1000;
  52.  
  53. int arr[N + 1];
  54. lli dp[N + 1];
  55. deque<pair<linear, lli>> cht;
  56.  
  57. lli intersect(linear &a, linear &b){
  58.     lli x = b.c - a.c;
  59.     lli y = a.m - b.m;
  60.     // ceiling of the answer
  61.     return x / y + !(((x < 0) != (y < 0)) || (x % y == 0));
  62. }
  63.  
  64. // Min CHT Insertion: Greater -> Less
  65. void chtInsert(linear l){ // O(1) Insertion
  66.     // new line has same m
  67.     if(!cht.empty() && cht.back().first.m == l.m){
  68.         if(cht.back().first.m > l.m){ // new line has lower c: less => better
  69.             cht.pop_back();
  70.             chtInsert(l);
  71.         } // new line has higher c: greater => worse
  72.         return;
  73.     }
  74.     // new line has left or same intersection but with lower m: less => better
  75.     while(!cht.empty() && cht.back().second >= intersect(cht.back().first, l)){
  76.         cht.pop_back();
  77.     }
  78.     // insert new line at the back
  79.     if(cht.empty()){ // empty hull
  80.         cht.emplace_back(l, 0);
  81.     } else {
  82.         cht.emplace_back(l, intersect(cht.back().first, l));
  83.     }
  84. }
  85.  
  86. // Min CHT Query: Less -> Greater
  87. lli chtQuery(lli x){ // O(1) Query (Two Pointer)
  88.     // upper_bound(cht.begin(), cht.end(), x) - 1
  89.     while(cht.size() > 1 && next(cht.begin()) -> second <= x){
  90.         cht.pop_front();
  91.     }
  92.     linear mn = cht.front().first;
  93.     return mn.m * x + mn.c;
  94. }
  95.  
  96. int main(){
  97.  
  98.     int nVertex, carCost;
  99.     scanf("%d%d", &nVertex, &carCost);
  100.     for(int i = 1; i <= nVertex; ++i){
  101.         scanf("%d", &arr[i]);
  102.     }
  103.  
  104.     dp[0] = 0;
  105.     for(int i = 1; i <= nVertex; ++i){
  106.         chtInsert(linear(-2 * arr[i], (lli)arr[i] * arr[i] + dp[i - 1]));
  107.         dp[i] = carCost + (lli)arr[i] * arr[i] + chtQuery(arr[i]);
  108.     }
  109.     cout << dp[nVertex];
  110.  
  111.     return 0;
  112. }
  113.  
RAW Paste Data