oj.uz

Submission #349409

# Submission time Handle Problem Language Result Execution time Memory
349409 2021-01-17T14:41:12 Z doowey Building Bridges (CEOI17_building) C++14
100 / 100
 90 ms 12524 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 ri;
  bool operator< (const Line &T) const {
    if(Q) return ai < T.ai;
    else return ri < T.ri;
  }
};

struct Hull : multiset<Line>{
  ld div(ld a, ld b){
    return a/b;
  }
  ld inter(Line A, Line B){
    return div((A.bi)-(B.bi),(B.ai)-(A.ai));
  }
  bool hasl(iterator it){
    return (it != begin());
  }
  bool har(iterator it){
    it++;
    return (it != end());
  }
  bool bad(iterator it){
    if(!hasl(it) || !har(it)) return false;
    auto pv = it;
    auto nx = it;
    pv -- ;
    nx ++ ;
    return inter(*pv,*nx) <= inter(*pv,*it);
  }
  void upd(iterator &it){
    auto ni = it;
    ni ++ ;
    if(ni == end()){
      it->ri = INF;
    }
    else{
      it->ri = inter(*it, *ni);
    }
  }
  void add(ll ai, ll bi){
    ai=-ai;
    bi=-bi;
    Q = true;
    Line cur = {ai, bi, inf};
    auto it = lower_bound(cur);
    if(it != end()){
      if(it->ai == ai){
        if(it->bi >= bi){
          return;
        }
        else{
          it=erase(it); //
        }
      }
    }
    it=insert(cur);
    if(bad(it)){
      erase(it);
      return;
    }
    auto nx = it;
    nx++;
    while(1){
      if(nx==end()) break;
      if(bad(nx))nx=erase(nx);
      else break;
    }
    nx = it;
    while(1){
      if(it==begin()) break;
      nx=it;
      nx--;
      if(bad(nx))erase(nx);
      else break;
    }
    upd(it);
    nx = it;
    if(nx != begin()){
      nx--;
      upd(nx);
    }
  }
  ll query(ld xi){
    Q = false;
    auto it = lower_bound({0,0,xi});
    return -((it->ai) * xi + (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 69 ms 3948 KB Output is correct
2 Correct 67 ms 4972 KB Output is correct
3 Correct 68 ms 4972 KB Output is correct
4 Correct 62 ms 4844 KB Output is correct
5 Correct 59 ms 6508 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 69 ms 3948 KB Output is correct
7 Correct 67 ms 4972 KB Output is correct
8 Correct 68 ms 4972 KB Output is correct
9 Correct 62 ms 4844 KB Output is correct
10 Correct 59 ms 6508 KB Output is correct
11 Correct 61 ms 5184 KB Output is correct
12 Correct 70 ms 4988 KB Output is correct
13 Correct 43 ms 4972 KB Output is correct
14 Correct 69 ms 5228 KB Output is correct
15 Correct 90 ms 12524 KB Output is correct
16 Correct 58 ms 6380 KB Output is correct
17 Correct 22 ms 4972 KB Output is correct
18 Correct 21 ms 4972 KB Output is correct