Submission #881832

#	Time	Username	Problem	Language	Result	Execution time	Memory
881832		Zero_OP	Building Bridges (CEOI17_building)	C++14	0 / 100	16 ms	7516 KiB

building

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
typedef long long ll;
typedef long double ld;
 
struct line{
    ll a, b;
    line(ll a = 0, ll b = 0) : a(a), b(b) {}
    ll eval(ll x){
        return a * x + b;
    }
};
 
vector<line> lines;
ld slope(const line& A, const line& B){
    return (ld)(B.b - A.b) / (A.a - B.a);
}
 
void add(line d){
    while(lines.size() > 1 and slope(d, lines.back()) < slope(lines.back(), lines[lines.size() - 2])){
        lines.pop_back();
    }
    lines.push_back(d);
}
 
ll query(ll x){
    int l = 0, r = lines.size();
    while(l < r){
        int mid = l + r >> 1;
        if(lines[mid].eval(x) >= lines[mid + 1].eval(x)) l = mid + 1;
        else r = mid;
    }
    return lines[l].eval(x);
}
 
int n;
ll dp[N], h[N], w[N];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    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];
 
    add(line(h[1], h[1] * h[1] + dp[1] - w[1]));
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + query(-2 * h[i]);
        add(line(h[i], h[i] * h[i] + dp[i] - w[i]));
    }
 
    cout << dp[n];
    return 0;
}

Compilation message (stderr)

building.cpp: In function 'll query(ll)':
building.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1;
      |                   ~~^~~

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