oj.uz

Submission #547404

# Submission time Handle Problem Language Result Execution time Memory
547404 2022-04-10T15:48:12 Z wdjpng Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 2644 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 hull
    {
        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) it->a - nx->a)*((lint) it->b - pr->b) <= ((lint)pr->a - it->a)*((lint)nx->b - it->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 (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(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;
     
        for(int i = 1; i < n; i++)
        {
            rep(j,i)
            {
                dp[i]=min(dp[i],h[i]*h[i]-2*h[i]*h[j]+h[j]*h[j]-w[i]+dp[j]);
            }
        }
        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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Execution timed out 3060 ms 2644 KB Time limit exceeded
7 Halted 0 ms 0 KB -