Submission #45291

#	Time	Username	Problem	Language	Result	Execution time	Memory
45291		nickyrio	Building Bridges (CEOI17_building)	C++17	100 / 100	253 ms	10368 KiB

building

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

// dp[i] = min(dp[j] + h[j] * h[j] - remove[j] + remove[i - 1] + h[i] * h[i] - 2 * h[i] * h[j])

struct line {
    long long a, b;
    line () {}
    line (long long a, long long b): a(a), b(b) {}
}IT[N << 2];
vector<long long> ranking;
long long Get(line d, int pos) {
    if (d.a == 1e18 && d.b == 1e18) return 1e18;
    return d.a * ranking[pos - 1] + d.b;
}

void Up(int k, int l, int r, int u, int v, line val) {
    if (l > v || r < u) return;
    int m = (l + r) >> 1;
    if (u <= l && r <= v) {
        if (Get(IT[k], l) >= Get(val, l) && Get(IT[k], r) >= Get(val, r)) {
            IT[k] = val; return;
        }
        if (Get(IT[k], l) <= Get(val, l) && Get(IT[k], r) <= Get(val, r)) {
            return;
        }
    }
    Up(k << 1, l, m, u, v, val);
    Up(k << 1 | 1, m + 1, r, u, v, val);
}

long long Query(int k, int l, int r, int pos) {
    //DEBUG(k);DEBUG(IT[k].a);DEBUG(IT[k].b);
    long long ans = Get(IT[k], pos);
    if (l == r) return ans;
    int m = (l + r) >> 1;
    if (pos <= m) return min(ans, Query(k << 1, l, m, pos));
    return min(ans, Query(k << 1 | 1, m + 1, r, pos));
}

long long h[N], w[N], dp[N];
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else 
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    int n;
    cin >> n;
    FOR(i, 1, n) {
        cin >> h[i];
        ranking.push_back(h[i]);
    }
    sort(ranking.begin(), ranking.end());
    FOR(i, 1, n) cin >> w[i];
    FOR(i, 1, n) w[i] += w[i - 1];
    dp[1] = 0;
    // a = -2 * h[j]
    // b = dp[j] + h[j] * h[j] - w[j]
    FOR(i, 1, n << 2) IT[i] = line(1e18, 1e18);
    Up(1, 1, n, 1, n, line(-h[1] * 2, h[1] * h[1] - w[1]));
    FOR(i, 2, n) {
        int pos = lower_bound(ranking.begin(), ranking.end(), h[i]) - ranking.begin() + 1;
    //    DEBUG(pos);
        dp[i] = Query(1, 1, n, pos) + h[i] * h[i] + w[i - 1];
        Up(1, 1, n, 1, n, line(-h[i] * 2, dp[i] + h[i] * h[i] - w[i]));
    }
    //Arr(dp, 1, n);
    cout << dp[n];
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

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