Submission #1264741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264741		minhpk	Building Bridges (CEOI17_building)	C++20	0 / 100	21 ms	3776 KiB

building

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
int prefix[1000005];
// hj^2 -2hi*hj -prefix[j]  + (hi^2 +prefix[i-1]);
struct line{
      int a,b;
};
int dp[1000005];
vector <line> v;
int inf=1e16;
int query(int x){
    if (v.size()==1){
        return v[0].a*x+v[0].b;
    }
    int l=1;
    int r=v.size()-1;
    int pos=inf;
    while (l<=r){
         int mid=(l+r)/2;
         int val1=v[mid].a*x+v[mid].b;
         int val2=v[mid-1].a*x+v[mid-1].b;
         pos=min({pos,val1,val2});
         if (val1>val2){
             r=mid-1;
         }else{
             l=mid+1;
         }
    }

    return pos;
}
bool cal(line c,line b,line a){
      return (c.b-a.b)*(a.a-b.a)>(b.b-a.b)*(a.a-c.a);
}

void add(line pre){
    v.push_back(pre);
    while (v.size()>=3 &&cal(v[v.size()-1],v[v.size()-2],v[v.size()-3]) ){
           v.erase(v.end()-2);
    }

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    for (int i=1;i<=a;i++){
         int x;
         cin >> x;
         prefix[i]=prefix[i-1]+x;
    }
    v.push_back({-2*z[1],-prefix[1]+z[1]*z[1]});
    dp[1]=0;
    for (int i=2;i<=a;i++){
         int val=query(z[i])+z[i]*z[i]+prefix[i-1];
         dp[i]=val;
         line pre={-2*z[i],dp[i]+z[i]*z[i]-prefix[i]};
//         cout << dp[i] << " " << v.size() << "\n";
         add(pre);
    }
    cout << dp[a] << "\n";
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40