oj.uz

Submission #868270

# Submission time Handle Problem Language Result Execution time Memory
868270 2023-10-31T02:22:04 Z phattruongPO344 Building Bridges (CEOI17_building) C++14
100 / 100
 40 ms 9924 KB 
#include<bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Phat Truong */
const int maxn = 1e5 + 10;
bool line_sort(false);
struct line{
    long long m,b;
    mutable double p;
    line();
    line(long long _m,long long _b,double _p){
        m = _m,b = _b,p = _p;
    }
    bool operator < (const line &x) const{
        if(!line_sort){
            if(m == x.m) return b < x.b;
            return m > x.m;
        }
        return p < x.p;
    }   
};
struct line_container:multiset<line,less<>>{
    const double inf = 1/.0;
    bool intersect(iterator x,iterator y){
        if(y == end()){
            x->p = inf;
            return false;
        }
        if(x -> m == y ->m)
            return true;
        else 
            x->p = (x ->b - y->b)*1.0/(y -> m - x ->m);
        return x ->p >= y->p;
    }
    void add(long long m,long long b){
        iterator z = insert(line(m,b,0));
        iterator y = z++;
        iterator x = y;
        while(intersect(y,z))
            intersect(y, z = erase(z));
        while((x = y) != begin() && intersect(--x,y))
            intersect(x,y = erase(y));
        while((y = x) != begin() && intersect(--x,y))
            intersect(x,y = erase(y)); 
    }
    long long findval(long long x){
        line_sort = true;
        line t = *(lower_bound(line(0,0,x)));
        line_sort = false;
        return (x*t.m + t.b);
    }
};
line_container hull;
long long dp[maxn];
int n;
long long h[maxn];
long long w[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
   // freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    cin >> n;
    FOR(i,1,n)
        cin >> h[i];
    FOR(i,1,n)
        cin >> w[i];
    FOR(i,1,n)
        w[i] += w[i-1];
    hull.add(-2*h[1],h[1]*h[1] - w[1]);
    dp[1] = 0;
    FOR(i,2,n){
        long long tmp = hull.findval(h[i]);
        dp[i] = tmp + h[i]*h[i] + w[i - 1];
        hull.add(-2*h[i],h[i]*h[i] - w[i] + dp[i]);
    }
    cout << dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2476 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2652 KB Output is correct
2 Correct 34 ms 3672 KB Output is correct
3 Correct 33 ms 3756 KB Output is correct
4 Correct 31 ms 3636 KB Output is correct
5 Correct 29 ms 4924 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2476 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 34 ms 2652 KB Output is correct
7 Correct 34 ms 3672 KB Output is correct
8 Correct 33 ms 3756 KB Output is correct
9 Correct 31 ms 3636 KB Output is correct
10 Correct 29 ms 4924 KB Output is correct
11 Correct 32 ms 3920 KB Output is correct
12 Correct 33 ms 3672 KB Output is correct
13 Correct 25 ms 3672 KB Output is correct
14 Correct 35 ms 3924 KB Output is correct
15 Correct 40 ms 9924 KB Output is correct
16 Correct 29 ms 4724 KB Output is correct
17 Correct 19 ms 3676 KB Output is correct
18 Correct 17 ms 3676 KB Output is correct