Submission #310924

#	Time	Username	Problem	Language	Result	Execution time	Memory
310924		BeanZ	Building Bridges (CEOI17_building)	C++14	100 / 100	97 ms	67364 KiB

building

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int lim = 1e6;
const int mod = 1e9 + 7;
pair<ll, ll> st[N * 4];
ll h[N], dp[N], sum[N], w[N];
ll f(pair<ll, ll> x, ll v){
    return x.first * v + x.second;
}
void add(pair<ll, ll> x, ll k, ll l, ll r){
    ll mid = (l + r) >> 1;
    bool left = f(x, l) < f(st[k], l);
    bool m = f(x, mid) < f(st[k], mid);
    if (m) swap(st[k], x);
    if (l == r) return;
    else if (left != m) add(x, k << 1, l, mid);
    else add(x, k << 1 | 1, mid + 1, r);
}
ll get(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    ll res = f(st[k], v);
    if (l == r) return res;
    else if (v <= mid) return min(res, get(k << 1, l, mid, v));
    else return min(res, get(k << 1 | 1, mid + 1, r, v));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i], sum[i] = sum[i - 1] + w[i];
    for (int i = 1; i <= (lim * 4); i++) st[i] = {0, 3e17};
    add({-2 * h[1], h[1] * h[1] - w[1] + dp[1]}, 1, 1, lim);
    for (int i = 2; i <= n; i++){
        dp[i] = sum[i - 1] + h[i] * h[i] + get(1, 1, lim, h[i]);
        add({-2 * h[i], h[i] * h[i] - sum[i] + dp[i]}, 1, 1, lim);
    }
    cout << dp[n];
}
/*
*/

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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