oj.uz

Submission #985274

# Submission time Handle Problem Language Result Execution time Memory
985274 2024-05-17T14:15:22 Z windowwife Building Bridges (CEOI17_building) C++17
100 / 100
 79 ms 13032 KB 
//fully dynamic convex hull trick/ linecontainer practice uwu :3
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 4;
ll n, h[maxn], w[maxn], tw, dp[maxn];
struct Line
{
    bool type;
    long double i;
    ll x, y;

};
bool operator < (const Line& A, const Line& B)
{
    if (A.type || B.type) return A.i < B.i; //for binary search
    return A.x > B.x; //for the convex hull, change to < if asking for max
}
set<Line> hull;
bool has_prev (set<Line>::iterator it)
{
    return it != hull.begin();
}
bool has_next (set<Line>::iterator it)
{
    return it != hull.end() && next(it) != hull.end();
}
long double isect (set<Line>::iterator A, set<Line>::iterator B)
{
    return (long double)1.0 * (A->y - B->y)/(B->x - A->x);
}
bool check (set<Line>::iterator it)
{
    if (has_next(it) && next(it)->y <= it->y) return false; //it > next(it) for all x
    return !(has_prev(it) && has_next(it) && isect(prev(it), next(it)) <= isect(prev(it), it)); //normal convex hull also have this
}
void change_isect (set<Line>::iterator it)
{
    if (has_prev(it))
    {
        Line l = *it;
        l.i = isect(prev(it), it);
        hull.insert(hull.erase(it), l);
    }
}
void add_line (ll x, ll y)
{
    set<Line>::iterator it;
    //parallel case
    it = hull.lower_bound({0, 0, x, y});
    if (it != hull.end() && it->x == x)
    {
        if (it->y <= y) return; //change to >= if asking for max
        hull.erase(it);
    }
    it = hull.insert({0, 0, x, y}).first;
    if (check(it))
    {
        while (has_prev(it) && !check(prev(it))) hull.erase(prev(it));
        while (has_next(it) && !check(next(it))) hull.erase(next(it));
        if (has_next(it)) change_isect(next(it));
        change_isect(it);
    }
    else hull.erase(it);
}
ll solve (ll q)
{
    Line l = *prev(hull.upper_bound({1, (long double)q, 0, 0}));
    return l.x*q + l.y;
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    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];
        tw += w[i];
    }
    dp[1] = -w[1];
    for (int i = 2; i <= n; i++)
    {
        add_line(-2*h[i - 1], dp[i - 1] + h[i - 1]*h[i - 1]);
        dp[i] = h[i]*h[i] - w[i] + solve(h[i]);
    }
    cout << tw + dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3924 KB Output is correct
2 Correct 60 ms 3796 KB Output is correct
3 Correct 60 ms 3924 KB Output is correct
4 Correct 56 ms 3672 KB Output is correct
5 Correct 50 ms 5720 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 65 ms 3924 KB Output is correct
7 Correct 60 ms 3796 KB Output is correct
8 Correct 60 ms 3924 KB Output is correct
9 Correct 56 ms 3672 KB Output is correct
10 Correct 50 ms 5720 KB Output is correct
11 Correct 53 ms 3928 KB Output is correct
12 Correct 61 ms 3860 KB Output is correct
13 Correct 37 ms 3756 KB Output is correct
14 Correct 61 ms 4064 KB Output is correct
15 Correct 79 ms 13032 KB Output is correct
16 Correct 50 ms 5456 KB Output is correct
17 Correct 17 ms 3676 KB Output is correct
18 Correct 16 ms 3800 KB Output is correct