fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N=2e5;
  5. int a[N+1];
  6. int n,c;
  7. __int128_t dp[N+1];
  8. struct line{
  9.     int a,b;
  10.     line() {a=0,b=0;}
  11.     int val(int x){
  12.         return a*x+b;
  13.     }
  14. };
  15. vector<line>vec;
  16. bool check(line x1,line x2,line x3){
  17.     return 1.0*(x3.b-x2.b)/(x2.a-x3.a)>1.0*(x2.b-x1.b)/(x1.a-x2.a);
  18. }
  19. void add(line x){
  20.     while(vec.size()>=2&&!check(vec[vec.size()-1],vec[vec.size()-2],x)){
  21.         vec.pop_back();
  22.     }
  23.     vec.push_back(x);
  24. }
  25. int get(int x){
  26.     int l=0,r=vec.size()-1;
  27.     int ans=0;
  28.     while(l<=r){
  29.         int m1=l+(r-l)/3;
  30.         int m2=r-(r-l)/3;
  31.         if(vec[m1].val(x)<vec[m2].val(x)){
  32.             ans=vec[m1].val(x);
  33.             r=m2-1;
  34.         }
  35.         else{
  36.             ans=vec[m2].val(x);
  37.             l=m1+1;
  38.         }
  39.     }
  40.     return ans;
  41. }
  42. signed main(){
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(0);cout.tie(0);
  45.     cin>>n>>c;
  46.     for(int i=1;i<=n;i++){
  47.         cin>>a[i];
  48.     }
  49.     line x;
  50.     x.a=-2*a[1];
  51.     x.b=a[1]*a[1];
  52.     add(x);
  53.     for(int i=2;i<=n;i++){
  54.         dp[i]=get(a[i])+a[i]*a[i]+c;
  55.         x.a=-2*a[i];
  56.         x.b=a[i]*a[i]+dp[i];
  57.         add(x);
  58.     }
  59.     vector<int>ans;
  60.     while(dp[n]){
  61.         int k=dp[n]%10;
  62.         dp[n]/=10;
  63.         ans.push_back(k);
  64.     }
  65.     reverse(ans.begin(),ans.end());
  66.     for(int k:ans){
  67.         cout<<k;
  68.     }
  69. }
Success #stdin #stdout 0s 5640KB
comments (?)
stdin
copy 
5 6
1 2 3 4 5
stdout
copy 
20
https://ideone.com/WbiQyL
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!