oj.uz

Submission #349412

# Submission time Handle Problem Language Result Execution time Memory
349412 2021-01-17T14:52:51 Z doowey Building Bridges (CEOI17_building) C++14
100 / 100
 91 ms 11628 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
const ld INF = (ld)4e18;
int h[N];
ll w[N];
ll dp[N];

ll sq(ll x){
    return (x * 1ll * x);
}

bool Q;

struct Line{
  ll ai;
  ll bi;
  mutable ld lim;
  bool operator< (const Line &T) const {
    if(Q) return ai < T.ai;
    else return lim < T.lim;
  }
};

struct Hull : multiset<Line>{
    ld intersect(Line F1, Line F2){
        return ld(F1.bi-F2.bi)/ld(F2.ai-F1.ai);
    }
    bool valid(iterator aq){
        iterator pv = aq;
        if(pv == begin()) return true;
        pv -- ;
        iterator nx = aq;
        nx ++ ;
        if(nx == end()) return true;
        return intersect(*pv,*nx) > intersect(*pv,*aq);
    }
    void upd(iterator &it){
        iterator nx = it;
        nx ++ ;
        if(nx == end()){
            it->lim=INF;
        }
        else{
            it->lim=intersect(*it,*nx);
        }
    }
    void add(ll aa, ll bb){
        aa=-aa;
        bb=-bb;
        Q=true;
        Line cur = {aa,bb,INF};
        auto it = lower_bound(cur);
        if(it != end()){
            if(it->ai == aa){
                if(it->bi >= bb){
                    return;
                }
                else{
                    erase(it);
                }
            }
        }
        it = insert(cur);
        if(!valid(it)){
            erase(it);
            return;
        }
        while(1){
            auto nx = it;
            nx++;
            if(nx==end()) break;
            if(valid(nx)) break;
            erase(nx);
        }
        while(it!=begin()){
            auto nx = it;
            nx--;
            if(valid(nx)) break;
            erase(nx);
        }
        upd(it);
        auto pv = it;
        if(pv != begin()){
            pv--;
            upd(pv);
        }
    }
    ll query(ld x){
        Q = false;
        auto it = lower_bound({0,0,x});
        return -((it->ai)*x+(it->bi));
    }
};

ll ax[N];
ll bx[N];

int main(){
    fastIO;
    int n;
    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];
        dp[i]=inf;
    }
    dp[1]=0;
    Hull dpv;
    for(int i = 1; i <= n; i ++ ){
        if(i > 1){
            dp[i]=dpv.query(h[i])+sq(h[i])+w[i-1];
        }
        ax[i]=-2ll*h[i];
        bx[i]=sq(h[i])-w[i]+dp[i];
        dpv.add(ax[i],bx[i]);
    }
    cout << dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4104 KB Output is correct
2 Correct 66 ms 3948 KB Output is correct
3 Correct 66 ms 3948 KB Output is correct
4 Correct 63 ms 3948 KB Output is correct
5 Correct 61 ms 5356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 67 ms 4104 KB Output is correct
7 Correct 66 ms 3948 KB Output is correct
8 Correct 66 ms 3948 KB Output is correct
9 Correct 63 ms 3948 KB Output is correct
10 Correct 61 ms 5356 KB Output is correct
11 Correct 61 ms 3820 KB Output is correct
12 Correct 72 ms 4060 KB Output is correct
13 Correct 48 ms 3820 KB Output is correct
14 Correct 68 ms 3948 KB Output is correct
15 Correct 91 ms 11628 KB Output is correct
16 Correct 60 ms 5484 KB Output is correct
17 Correct 21 ms 3820 KB Output is correct
18 Correct 21 ms 3820 KB Output is correct