oj.uz

Submission #987302

# Submission time Handle Problem Language Result Execution time Memory
987302 2024-05-22T14:18:21 Z proplayer Building Bridges (CEOI17_building) C++14
100 / 100
 83 ms 12832 KB 
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
using lli = long long;
using ld = long double;
const int maxN = 1e5 + 5;
struct Tline
{
    bool type;
    ld x;
    lli a,b;
};
using setit = set<Tline>::iterator;
bool operator < (Tline l1,Tline l2)
{
    if (l1.type || l2.type) return l1.x < l2.x;
    return l1.a > l2.a;
}
struct Tcht
{
    set<Tline> cht;
    bool has_prev(setit it) {return it != cht.begin();}
    bool has_next(setit it) {return it != cht.end() && next(it) != cht.end();}
    ld cut(setit x,setit y) {return ld(x->b - y->b) / (y->a - x->a);}
    bool bad(setit it)
    {
        if (has_next(it) && it->b >= next(it)->b) return true;
        return has_next(it) && has_prev(it) && cut(prev(it),next(it)) >= cut(it,next(it));
    }
    void calc_x(setit it)
    {
        if (has_prev(it))
        {
            Tline l = *it;
            l.x = cut(prev(it),it);
            cht.insert(cht.erase(it),l);
        }
    }
    void add(lli a,lli b)
    {
        setit it = cht.lower_bound({0,0,a,b});
        if (it != cht.end() && a == it->a)
        {
            if (it->b <= b) return;
            cht.erase(it);
        }
        it = cht.insert({0,0,a,b}).first;
        if (bad(it)) cht.erase(it);
        else
        {
            while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
            while (has_next(it) && bad(next(it))) cht.erase(next(it));
            if (has_next(it)) calc_x(next(it));
            calc_x(it);
        }
    }
    lli get(lli x)
    {
        Tline l = *prev(cht.upper_bound({1,ld(x),0,0}));
        return l.a * x + l.b;
    }
};
Tcht c;
lli h[maxN],w[maxN],sumw,n,f[maxN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("XAYCAU.inp","r",stdin);
    //freopen("XAYCAU.out","w",stdout);
    cin >> n;sumw = 0;
    for (int i = 1;i <= n;++i) cin >> h[i];
    for (int i = 1;i <= n;++i)
    {
        cin >> w[i];
        sumw += w[i];
    }
    f[1] = -w[1];
    for (int i = 2;i <= n;++i)
    {
        c.add(-2 * h[i - 1],f[i - 1] + h[i - 1] * h[i - 1]);
        f[i] = c.get(h[i]) - w[i] + h[i] * h[i];
        //cout << c.get(h[i]) << " ";
    }
    cout << f[n] + sumw;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3924 KB Output is correct
2 Correct 62 ms 3920 KB Output is correct
3 Correct 60 ms 3900 KB Output is correct
4 Correct 58 ms 3740 KB Output is correct
5 Correct 53 ms 5488 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 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2476 KB Output is correct
6 Correct 62 ms 3924 KB Output is correct
7 Correct 62 ms 3920 KB Output is correct
8 Correct 60 ms 3900 KB Output is correct
9 Correct 58 ms 3740 KB Output is correct
10 Correct 53 ms 5488 KB Output is correct
11 Correct 54 ms 3912 KB Output is correct
12 Correct 63 ms 3896 KB Output is correct
13 Correct 38 ms 3672 KB Output is correct
14 Correct 65 ms 4408 KB Output is correct
15 Correct 83 ms 12832 KB Output is correct
16 Correct 53 ms 5336 KB Output is correct
17 Correct 18 ms 3676 KB Output is correct
18 Correct 16 ms 3768 KB Output is correct