oj.uz

Submission #479262

# Submission time Handle Problem Language Result Execution time Memory
479262 2021-10-11T03:55:57 Z Rainbowbunny Building Bridges (CEOI17_building) C++17
100 / 100
 106 ms 65252 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 1000005;
const long long INF = 1e18;

struct Line
{
    long long k, b;
    Line(long long k = 0, long long b = INF) : k(k), b(b) {}
    long long eval(long long x)
    {
        return k * x + b;
    }
};

int n;
long long ans, h[MAXN], w[MAXN], dp[MAXN];

Line IT[4 * MAXV];

void Update(int node, int l, int r, Line L)
{
    int mid = (l + r) >> 1;
    bool lef = IT[node].eval(l) > L.eval(l);
    bool m = IT[node].eval(mid) > L.eval(mid);
    if(m)
    {
        swap(L, IT[node]);
    }
    if(l == r)
    {
        return;
    }
    if(lef != m)
    {
        Update(node << 1, l, mid, L);
    }
    else
    {
        Update(node << 1 | 1, mid + 1, r, L);
    }
}

long long Get(int node, int l, int r, int i)
{
    int mid = (l + r) >> 1;
    if(l == r)
    {
        return IT[node].eval(i);
    }
    if(i <= mid)
    {
        return min(IT[node].eval(i), Get(node << 1, l, mid, i));
    } 
    else
    {
        return min(IT[node].eval(i), Get(node << 1 | 1, mid + 1, r, i));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.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];
    }
    for(int i = 1; i <= n; i++)
    {
        if(i != 1)
        {
            dp[i] = Get(1, 0, MAXV, h[i]) + h[i] * h[i] + w[i - 1];
        }
        else
        {
            dp[i] = 0;
        }
        Line tmp(-2 * h[i], h[i] * h[i] - w[i] + dp[i]);
        Update(1, 0, MAXV, tmp);
    }
    cout << dp[n] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62916 KB Output is correct
2 Correct 34 ms 62908 KB Output is correct
3 Correct 32 ms 62880 KB Output is correct
4 Correct 35 ms 62936 KB Output is correct
5 Correct 32 ms 62984 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 65252 KB Output is correct
2 Correct 79 ms 65148 KB Output is correct
3 Correct 83 ms 65164 KB Output is correct
4 Correct 82 ms 65200 KB Output is correct
5 Correct 73 ms 65228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62916 KB Output is correct
2 Correct 34 ms 62908 KB Output is correct
3 Correct 32 ms 62880 KB Output is correct
4 Correct 35 ms 62936 KB Output is correct
5 Correct 32 ms 62984 KB Output is correct
6 Correct 85 ms 65252 KB Output is correct
7 Correct 79 ms 65148 KB Output is correct
8 Correct 83 ms 65164 KB Output is correct
9 Correct 82 ms 65200 KB Output is correct
10 Correct 73 ms 65228 KB Output is correct
11 Correct 106 ms 65248 KB Output is correct
12 Correct 88 ms 65192 KB Output is correct
13 Correct 80 ms 65152 KB Output is correct
14 Correct 83 ms 65224 KB Output is correct
15 Correct 68 ms 65196 KB Output is correct
16 Correct 74 ms 65244 KB Output is correct
17 Correct 62 ms 65156 KB Output is correct
18 Correct 72 ms 65220 KB Output is correct