oj.uz

Submission #868285

# Submission time Handle Problem Language Result Execution time Memory
868285 2023-10-31T02:54:26 Z phattruongPO344 Building Bridges (CEOI17_building) C++14
100 / 100
 39 ms 9052 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 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2760 KB Output is correct
2 Correct 33 ms 2736 KB Output is correct
3 Correct 34 ms 2652 KB Output is correct
4 Correct 38 ms 2700 KB Output is correct
5 Correct 34 ms 3948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2760 KB Output is correct
7 Correct 33 ms 2736 KB Output is correct
8 Correct 34 ms 2652 KB Output is correct
9 Correct 38 ms 2700 KB Output is correct
10 Correct 34 ms 3948 KB Output is correct
11 Correct 31 ms 2696 KB Output is correct
12 Correct 33 ms 2652 KB Output is correct
13 Correct 25 ms 2652 KB Output is correct
14 Correct 32 ms 2648 KB Output is correct
15 Correct 39 ms 9052 KB Output is correct
16 Correct 29 ms 3916 KB Output is correct
17 Correct 16 ms 2652 KB Output is correct
18 Correct 16 ms 2652 KB Output is correct