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