oj.uz

Submission #547398

# Submission time Handle Problem Language Result Execution time Memory
547398 2022-04-10T15:32:44 Z wdjpng Building Bridges (CEOI17_building) C++17
0 / 100
 3000 ms 3668 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) sum+=w[i];

    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]-w[i]-2*h[i]*h[j]+dp[j]+h[j]*h[j]);
        }
    }
    cout<<dp[n-1]+sum<<'\n';
}

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -