oj.uz

Submission #1114346

# Submission time Handle Problem Language Result Execution time Memory
1114346 2024-11-18T16:06:20 Z proplayer Building Bridges (CEOI17_building) C++14
100 / 100
 86 ms 12872 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 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3796 KB Output is correct
2 Correct 65 ms 3920 KB Output is correct
3 Correct 59 ms 3916 KB Output is correct
4 Correct 54 ms 3664 KB Output is correct
5 Correct 56 ms 5356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 58 ms 3796 KB Output is correct
7 Correct 65 ms 3920 KB Output is correct
8 Correct 59 ms 3916 KB Output is correct
9 Correct 54 ms 3664 KB Output is correct
10 Correct 56 ms 5356 KB Output is correct
11 Correct 54 ms 4032 KB Output is correct
12 Correct 62 ms 3904 KB Output is correct
13 Correct 44 ms 3920 KB Output is correct
14 Correct 57 ms 4024 KB Output is correct
15 Correct 86 ms 12872 KB Output is correct
16 Correct 54 ms 5456 KB Output is correct
17 Correct 12 ms 3664 KB Output is correct
18 Correct 17 ms 3776 KB Output is correct