oj.uz

Submission #547664

# Submission time Handle Problem Language Result Execution time Memory
547664 2022-04-11T09:15:22 Z wdjpng Building Bridges (CEOI17_building) C++17
100 / 100
 71 ms 12896 KB 
    #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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3800 KB Output is correct
2 Correct 56 ms 3800 KB Output is correct
3 Correct 54 ms 3792 KB Output is correct
4 Correct 55 ms 3600 KB Output is correct
5 Correct 54 ms 5404 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 56 ms 3800 KB Output is correct
7 Correct 56 ms 3800 KB Output is correct
8 Correct 54 ms 3792 KB Output is correct
9 Correct 55 ms 3600 KB Output is correct
10 Correct 54 ms 5404 KB Output is correct
11 Correct 51 ms 3904 KB Output is correct
12 Correct 55 ms 3788 KB Output is correct
13 Correct 38 ms 3780 KB Output is correct
14 Correct 55 ms 3924 KB Output is correct
15 Correct 71 ms 12896 KB Output is correct
16 Correct 53 ms 5480 KB Output is correct
17 Correct 19 ms 3672 KB Output is correct
18 Correct 21 ms 3660 KB Output is correct