Submission #907143

#	Time	Username	Problem	Language	Result	Execution time	Memory
907143		Dec0Dedd	Building Bridges (CEOI17_building)	C++14	100 / 100	71 ms	8888 KiB

building

#include <bits/stdc++.h>
 
using namespace std;
 
typedef complex<long long> point;
#define ll long long
#define x real
#define y imag
 
const int MAXN = 2e5;
const int MAXH = 2e6;
const long long INF = 4e18;
 
long long dp[MAXN];
 
struct Line {
  ll a, b;
  ll operator()(ll x) {
      return a*x+b;
  }
};
 
struct Node {
  Line seg;
  Node *left = NULL, *right = NULL;
  Node(Line x): seg(x) {};
};
 
void insert(int l, int r, Line seg, Node *nd) {
    int m = (l+r)/2;
    bool left = nd->seg(l) > seg(l);
    bool mid = nd->seg(m) > seg(m);
 
    if (mid) swap(seg, nd->seg);
 
    if (r-l == 1) {
        return;
    } else if (left != mid) {
        if (nd->left) insert(l, m, seg, nd->left);
        else nd->left = new Node(seg);
    } else {
        if (nd->right) insert(m, r, seg, nd->right);
        else nd->right = new Node(seg);
    }
}
 
ll query(int l, int r, ll x, Node *nd) {
    int m = (l+r)/2;
 
    if (r-l == 1) {
        return nd->seg(x);
    } else if (x < m && nd->left) {
        return min(nd->seg(x), query(l, m, x, nd->left));
    } else if (nd->right) {
        return min(nd->seg(x), query(m, r, x, nd->right));
    } else {
        return nd->seg(x);
    }
}
 
int main() {
 
    int n;
    cin>>n;
 
    long long h[n], w[n];
    for (int i=0; i<n; ++i) cin>>h[i];
    for (int i=0; i<n; ++i) cin>>w[i];
 
    long long suf[n+1];
    suf[n] = 0;
    for (int i=n-1; i>=0; --i) suf[i] = suf[i+1]+w[i];
 
    Node *root = new Node{{0, INF}};
    dp[0] = 0;
    insert(-MAXH, MAXH, Line{-2*h[0], h[0]*h[0]+suf[1]}, root);
    for (int i=1; i<n; ++i) {
        dp[i] = query(-MAXH, MAXH, h[i], root) + h[i]*h[i] - suf[i];
        insert(-MAXH, MAXH, Line{-2*h[i], h[i]*h[i]+suf[i+1]+dp[i]}, root);
    }
 
    cout<<dp[n-1]<<endl;
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40