oj.uz

Submission #881826

# Submission time Handle Problem Language Result Execution time Memory
881826 2023-12-02T03:25:17 Z Zero_OP Building Bridges (CEOI17_building) C++14
0 / 100
 41 ms 18004 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;
typedef long double ld;

struct LiChao{
    struct line{
        ll a, b;
        ll eval(ll x){ return a*x+b; }
    };

    line st[N<<2];

    void update(int id, int l, int r, line d){
        if(l==r){
            if(st[id].eval(l)>d.eval(l)) st[id]=d;
        }
        else{
            int m=l+r>>1;
            if(st[id].a<d.a) swap(st[id], d);
            if(st[id].eval(m)>d.eval(m)){
                swap(st[id], d);
                update(id<<1, l, m, d);
            }
            else{
                update(id<<1|1, m+1, r, d);
            }
        }
    }

    void insertLine(int lim, line d){
        update(1, 1, lim, d);
    }

    ll query(int id, int l, int r, int x){
        if(l==r) return st[id].eval(x);
        int m=l+r>>1;
        if(x<=m) return min(st[id].eval(x), query(id<<1, l, m, x));
        else return min(st[id].eval(x), query(id<<1|1, m+1, r, x));
    }

    ll getMin(int lim, int x){
        return query(1, 1, lim, x);
    }
} lichaoTree;

int n, h[N];
ll dp[N], w[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    #define task "XAYCAU"
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];

    lichaoTree.insertLine(1000000, {- 2 * h[1], h[1] * h[1] + dp[1] - w[1]});
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + lichaoTree.getMin(1000000, h[i]);
        lichaoTree.insertLine(1000000, {-2 * h[i], h[i] * h[i] + dp[i] - w[i]});
    }

    cout << dp[n];
    return 0;
}

Compilation message

building.cpp: In member function 'void LiChao::update(int, int, int, LiChao::line)':
building.cpp:23:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |             int m=l+r>>1;
      |                   ~^~
building.cpp: In member function 'll LiChao::query(int, int, int, int)':
building.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m=l+r>>1;
      |               ~^~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -