oj.uz

Submission #116318

# Submission time Handle Problem Language Result Execution time Memory
116318 2019-06-12T08:06:43 Z JohnTitor Building Bridges (CEOI17_building) C++11
100 / 100
 115 ms 14972 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Bridges"
int n, m;
int h[100001];
int x[100001];
int w[100001];
class line{
public:
    ll a, b;
    line(){
        a=0;
        b=1e18;
    }
    line(ll a, ll b){
        this->a=a;
        this->b=b;
    }
    ll at(int x){
        return a*x+b;
    }
};
class linear_segment_tree{
public:
    using pointer=linear_segment_tree*;
    pointer left, right;
    int l, r, m;
    line L;
    linear_segment_tree(int idl, int idr): L(){
        l=x[idl];
        r=x[idr];
        m=x[(idl+idr)/2];
        if(idl!=idr){
            left=new linear_segment_tree(idl, (idl+idr)/2);
            right=new linear_segment_tree((idl+idr)/2+1, idr);
        }
    }
    void update(line A){
        bool gl=A.at(l)<=L.at(l);
        bool gr=A.at(r)<=L.at(r);
        if(gl&&gr) L=A;
        else if(gl||gr){
            left->update(A);
            right->update(A);
        }
    }
    ll get(int u){
        if(l==r) return L.at(u);
        else{
            if(m>=u) return min(left->get(u), L.at(u));
            return min(right->get(u), L.at(u));
        }
    }
};
linear_segment_tree::pointer tree;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    FOR(i, 1, n) read(h[i]);
    FOR(i, 1, n) read(w[i]);
    FOR(i, 1, n) x[i]=h[i];
    sort(x+1, x+n+1);
    m=unique(x+1, x+n+1)-x-1;
    tree=new linear_segment_tree(1, m);
    tree->update(line(-h[1]*2, ((ll)h[1])*h[1]));
    ll ans=0;
    FOR(i, 2, n){
        ll best=tree->get(h[i]);
        best+=((ll)h[i])*h[i]-w[i];
        tree->update(line(-h[i]*2, best+((ll)h[i])*h[i]));
        if(i==n) ans=best;
    }
    ans+=accumulate(w+2, w+n+1, 0LL);
    writeln(ans);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2588 KB Output is correct
2 Correct 65 ms 3556 KB Output is correct
3 Correct 63 ms 3456 KB Output is correct
4 Correct 48 ms 2688 KB Output is correct
5 Correct 54 ms 14968 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 62 ms 2588 KB Output is correct
7 Correct 65 ms 3556 KB Output is correct
8 Correct 63 ms 3456 KB Output is correct
9 Correct 48 ms 2688 KB Output is correct
10 Correct 54 ms 14968 KB Output is correct
11 Correct 115 ms 10688 KB Output is correct
12 Correct 102 ms 10488 KB Output is correct
13 Correct 31 ms 2788 KB Output is correct
14 Correct 114 ms 10664 KB Output is correct
15 Correct 55 ms 14840 KB Output is correct
16 Correct 51 ms 14972 KB Output is correct
17 Correct 13 ms 2560 KB Output is correct
18 Correct 14 ms 2560 KB Output is correct