Sreekar_0125

Untitled

Feb 18th, 2024
1,209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. template <class T>
  7. using pbds =
  8.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. // #define cerr if(false)cerr
  10. #define int long long
  11. #define pb push_back
  12. #define F first
  13. #define S second
  14. #define yes cout << "Yes\n"
  15. #define no cout << "No\n"
  16. #define yn(x) x ? yes : no
  17. #define f(i, s, e) for (int i = s; i < e; i++)
  18. #define vi vector<int>
  19. #define vb vector<bool>
  20. #define pii pair<int, int>
  21. #define vpi vector<pii>
  22. #define umi unordered_map<int, int>
  23. #define mi map<int, int>
  24. #define si set<int>
  25. #define sc set<char>
  26. #define maxheap priority_queue<int>
  27. #define minheap priority_queue<int, vector<int>, greater<int>>
  28. #define all(x) x.begin(), x.end()
  29. #define minele(x) *min_element(all(x))
  30. #define maxele(x) *max_element(all(x))
  31. #define endl '\n'
  32.  
  33. const int N = 2e5;
  34. const int MOD = 1e9 + 7;
  35.  
  36. #ifndef ONLINE_JUDGE
  37. #define debug(x)            \
  38.     cerr << (#x) << " is "; \
  39.     _print(x)
  40. #define dbg(x) \
  41.     cerr << (#x) << " is " << x << endl;
  42. #else
  43. #define debug(x)
  44. #define dbg(x)
  45. #endif
  46.  
  47. template <typename T>
  48. void _print(T a)
  49. {
  50.     cerr << a;
  51. }
  52. template <typename T>
  53. void print(T a)
  54. {
  55.     cout << a << ' ';
  56. }
  57. template <typename T>
  58. void println(T a)
  59. {
  60.     cout << a << endl;
  61. }
  62. template <class T>
  63. istream &operator>>(istream &is, vector<T> &a)
  64. {
  65.     for (auto &x : a)
  66.         is >> x;
  67.     return is;
  68. }
  69. template <class T>
  70. ostream &operator<<(ostream &os, const vector<T> &a)
  71. {
  72.     for (const auto &x : a)
  73.         os << x << ' ';
  74.     return os;
  75. }
  76.  
  77. template <class T, class V>
  78. void _print(pair<T, V> p);
  79. template <class T>
  80. void _print(vector<T> v);
  81. template <class T>
  82. void _print(set<T> v);
  83. template <class T, class V>
  84. void _print(map<T, V> v);
  85. template <class T>
  86. void _print(multiset<T> v);
  87. template <class T, class V>
  88. void _print(pair<T, V> p)
  89. {
  90.     cerr << "{";
  91.     _print(p.F);
  92.     cerr << ",";
  93.     _print(p.S);
  94.     cerr << "} ";
  95. }
  96. template <class T>
  97. void _print(vector<T> v)
  98. {
  99.     cerr << "[ ";
  100.     for (T i : v)
  101.     {
  102.         _print(i);
  103.         cerr << " ";
  104.     }
  105.     cerr << "]";
  106.     cerr << endl;
  107. }
  108. template <class T>
  109. void _print(set<T> v)
  110. {
  111.     cerr << "[ ";
  112.     for (T i : v)
  113.     {
  114.         _print(i);
  115.         cerr << " ";
  116.     }
  117.     cerr << "]";
  118.     cerr << endl;
  119. }
  120. template <class T>
  121. void _print(multiset<T> v)
  122. {
  123.     cerr << "[ ";
  124.     for (T i : v)
  125.     {
  126.         _print(i);
  127.         cerr << " ";
  128.     }
  129.     cerr << "]";
  130.     cerr << endl;
  131. }
  132. template <class T, class V>
  133. void _print(map<T, V> v)
  134. {
  135.     cerr << "[ ";
  136.     for (auto i : v)
  137.     {
  138.         _print(i);
  139.         cerr << " ";
  140.     }
  141.     cerr << "]";
  142.     cerr << endl;
  143. }
  144. template <class T, class V>
  145. void _print(unordered_map<T, V> v)
  146. {
  147.     cerr << "[ ";
  148.     for (auto i : v)
  149.     {
  150.         _print(i);
  151.         cerr << " ";
  152.     }
  153.     cerr << "]";
  154.     cerr << endl;
  155. }
  156.  
  157. /////////////Sieve///////////////
  158. // vb sieve(N + 5, true);
  159. // vi primes;
  160. // void gensieve()
  161. // {
  162. //     sieve[0] = sieve[1] = false;
  163. //     for (int i = 2; i <= sqrt(N); i++)
  164. //     {
  165. //         if (sieve[i])
  166. //         {
  167. //             for (int j = i * i; j <= N; j += i)
  168. //                 sieve[j] = false;
  169. //         }
  170. //     }
  171. //     for (int i = 2; i <= N; i++)
  172. //     {
  173. //         if (sieve[i])
  174. //             primes.pb(i);
  175. //     }
  176. // }
  177. ////////////////////////////////
  178.  
  179. int binpow(int a, int b)
  180. {
  181.     int ans = 1;
  182.     a %= MOD;
  183.     while (b)
  184.     {
  185.         if (b & 1)
  186.             ans = ((ans % MOD) * (a % MOD)) % MOD;
  187.  
  188.         a = ((a % MOD) * (a % MOD)) % MOD;
  189.         b >>= 1;
  190.     }
  191.     return ans;
  192. }
  193.  
  194. void fast()
  195. {
  196.     ios_base::sync_with_stdio(false);
  197.     cin.tie(NULL);
  198.     cout.tie(NULL);
  199. }
  200.  
  201. void init_code()
  202. {
  203. #ifndef ONLINE_JUDGE
  204.     freopen("input.txt", "r", stdin);
  205.     freopen("output.txt", "w", stdout);
  206.     freopen("error.txt", "w", stderr);
  207. #endif // ONLINE_JUDGE
  208. }
  209.  
  210. int n, c;
  211. vi v;
  212.  
  213. vector<vi> dp;
  214.  
  215. int fun(int i, int p)
  216. {
  217.     if (dp[i][p] != -1)
  218.         return dp[i][p];
  219.     if (i == n - 1)
  220.     {
  221.         return dp[i][p] = (((v[i] - v[p]) * (v[i] - v[p])) + c);
  222.     }
  223.     // take
  224.     int take = (((v[i] - v[p]) * (v[i] - v[p])) + c) + fun(i + 1, i);
  225.  
  226.     // not take
  227.     int nottake = fun(i + 1, p);
  228.  
  229.     return dp[i][p] = min(take, nottake);
  230. }
  231.  
  232. void solve()
  233. {
  234.     cin >> n >> c;
  235.  
  236.     v.resize(n);
  237.     cin >> v;
  238.  
  239.     dp.resize(n + 1, vi(n + 1, -1));
  240.     println(fun(0, 0));
  241. }
  242.  
  243. signed main()
  244. {
  245.     init_code();
  246.     fast();
  247.     int t = 1;
  248.     // cin >> t;
  249.     while (t--)
  250.     {
  251.         solve();
  252.     }
  253.     return 0;
  254. }
  255.  
Advertisement
Add Comment
Please, Sign In to add comment