Submission #547664

#	Time	Username	Problem	Language	Result	Execution time	Memory
547664		wdjpng	Building Bridges (CEOI17_building)	C++17	100 / 100	71 ms	12896 KiB

building

    #include <bits/stdc++.h>
     
    #define int long long
    #define lint __int128_t
    #define rep(i,n) for(int i =0; i<n;i++)
    #define all(a) a.begin(), a.end()
     
    using namespace std;
     
    const int MOD = 32768;
     
    struct line
    {
        mutable long double xleft = -1e15; 
        bool search=false;
        int a,b;
     
        line(int x) : b(x), search(true) {}
        line(int ia, int ib) : a(ia), b(ib) {}
     
        bool operator<(const line& l2) const {
            if(search) return b < l2.xleft;
            if(l2.search) return xleft < l2.b;
            return (a!=l2.a)?a<l2.a:b<l2.b;
        }
     
        int eval(int x) const {return a*x + b;}
        
        // it zeigt auf Element eins links
        void recalcleft(set<line>::iterator it) const
        {
            if(a == it -> a) return;
            xleft = ((long double) b - it->b) / ((long double) it->a - a);
        }
    };
     
     
    struct hullopt
    {
        set<line>hull;
     
        bool bad(set<line>::iterator it)
        {
            // normal case
            if(it==hull.begin()) {
                if(next(it)==hull.end()) return false;
                return it->a==next(it)->a&&next(it)->b>=it->b;
            }
     
            auto pr = prev(it);
            if(next(it)==hull.end()) return it->a==pr->a&&pr->b>=it->b; // unneccassary ?
     
            auto nx = next(it);
            if(pr->a==it->a) return it->b<=pr->b;  //not like joel 
            if(nx->a==it->a) return it->b<=nx->b;
            return ((lint)  pr->a - it->a)*((lint) nx->b - it->b)<=((lint) it->a-nx->a)*((lint)it->b-pr->b);
        }
     
        void insert(int a, int b)
        {
            auto it = hull.insert(line({-a,-b})).first;
            if(bad(it)) {hull.erase(it); return;}
     
            while (it!=hull.begin()&&bad(prev(it))) hull.erase(prev(it));
            while (next(it)!=hull.end()&&bad(next(it))) hull.erase(next(it));
     
            // why don't I have to do this previously
            if(it==hull.begin()) it->xleft=-1e15;
            else it->recalcleft(prev(it));
            if(next(it)!=hull.end()) next(it)->recalcleft(it);
        }
     
        int query(int x)
        {
            return -prev(hull.upper_bound(line(x)))->eval(x);
        }
    };
     
     
    signed main()
    {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
        
        int n;
        cin>>n;
        vector<int>h(n),w(n);
     
        rep(i,n) cin>>h[i];
        rep(i,n) cin>>w[i];
     
        int sum = 0;
        rep(i,n-1) sum+=w[i+1];
     
        vector<int>dp(n,1e18);
        dp[0]=0;
        hullopt opt = hullopt();
        opt.insert(-2*h[0], dp[0]+h[0]*h[0]);
        for(int i = 1; i < n; i++)
        {
            dp[i] = h[i]*h[i] - w[i] + opt.query(h[i]);
            opt.insert(-2*h[i], dp[i]+h[i]*h[i]);
        }
        cout<<dp[n-1]+sum<<'\n';
    }

Compilation message (stderr)

building.cpp: In constructor 'line::line(long long int)':
building.cpp:16:15: warning: 'line::b' will be initialized after [-Wreorder]
   16 |         int a,b;
      |               ^
building.cpp:15:14: warning:   'bool line::search' [-Wreorder]
   15 |         bool search=false;
      |              ^~~~~~
building.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         line(int x) : b(x), search(true) {}
      |         ^~~~

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