Submission #1273183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273183		khanhgng	Building Bridges (CEOI17_building)	C++20	100 / 100	84 ms	10408 KiB

building

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
#define pb push_back
#define bit(i,x) ((x>>i)&1)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define task "test"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r){assert(l<=r);return uniform_int_distribution<ll>(l,r)(rd);}

const int MAXn = 1e6 + 10;
const ll INF = (long long)(1e18);
const ll MOD1 = 1e9;
const int MOD = 1e9 + 7;
const int BL = 340;
const int BASE = 3137;

struct line{
    ll a,b;
    ld rx;
    line(ll _a = 0, ll _b = 0, ld _rx = MOD):a(_a),b(_b),rx(_rx){};
    ll eval(int x){
        return a*x+b;
    }
    ld isect(const line &other)const{
        return 1.0*(other.b-b)/(a-other.a);
    }
    bool operator < (const line &other)const{
        if(other.a!=MOD){
            return a>other.a;
        }
        return rx<other.rx;
    }
};

struct CHT{
    set<line>hull;
    void init(){
        hull.clear();
    }
    bool hasPrev(set<line>::iterator it){return it!=hull.begin();}
    bool hasNext(set<line>::iterator it){return (it!=hull.end()&&next(it)!=hull.end());}
    bool Bad(line d1,line d2,line d3){
        return d1.isect(d3)<=d1.isect(d2);
    }
    bool Bad(set<line>::iterator it){
        return (hasPrev(it)&&hasNext(it)&&Bad(*prev(it),*it,*next(it)));
    }
    void calcrx(set<line>::iterator it){
        line _d=*it;
        if(hasNext(it))_d.rx=_d.isect(*next(it));
        else _d.rx=MOD;
        hull.erase(it);
        hull.insert(_d);
    }
    void AddLine(line newline){
        auto it=hull.lower_bound(newline);
        if(it!=hull.end()&&it->a==newline.a){
            if(it->b<=newline.b)return;
            hull.erase(it);
        }
        it=hull.insert(newline).fi;
        if(Bad(it)){
            hull.erase(it);
            return;
        }
        while(hasPrev(it)&&Bad(prev(it)))hull.erase(prev(it));
        while(hasNext(it)&&Bad(next(it)))hull.erase(next(it));
        if(hasPrev(it))calcrx(prev(it));
        calcrx(it);
    }
    line query(int x){
        return *hull.lower_bound(line(MOD,0,x));
    }
}cht;

int n,w[MAXn],h[MAXn],dp[MAXn];

void solution(){
    cin>>n;
    int sum=0;
    FOR(i,1,n)cin>>h[i];
    FOR(i,1,n)cin>>w[i],sum+=w[i];
    cht.init();
    dp[1]=-w[1];
    cht.AddLine(line(-2*h[1],dp[1]+h[1]*h[1]));
    FOR(i,2,n){
        ///dp[i]=min -w[i]+dp[j]+(h[i]-h[j])^2
        ///dp[i]=min -w[i]+h[i]^2  +dp[j] +h[j]^2 -2h[i]h[j]
        dp[i]=cht.query(h[i]).eval(h[i])-w[i]+h[i]*h[i];
        cht.AddLine(line(-2*h[i],dp[i]+h[i]*h[i]));
    }
    cout << dp[n]+sum;
}

int32_t main(){
    if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
    ios_base::sync_with_stdio(0);cin.tie(0);
    int Ntest=1;///cin>>Ntest;
    while(Ntest--)solution();
    cerr<< "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

Compilation message (stderr)

building.cpp: In function 'int32_t main()':
building.cpp:106:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
      |                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:106:68: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
      |                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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