oj.uz

Submission #940856

# Submission time Handle Problem Language Result Execution time Memory
940856 2024-03-07T18:57:26 Z vivo2006 Building Bridges (CEOI17_building) C++14
0 / 100
 55 ms 6228 KB 
#include<iostream>
#include<cstring>

#define MAXN 100001
#define int long long

using namespace std;

long long n, total, h[MAXN], w[MAXN], cur, dp[MAXN];

struct Line
{
    long long m, b;
    Line() {}
    Line(long long _m, long long _b)
    {
        m = _m;
        b = _b;
    }
    long long operator() (long long x)
    {
        return m * x + b;
    }
};
struct LiChao
{
    Line arr[40 * MAXN];
    void add(int ind, int l, int r, Line seg)
    {
        if(l == r)
        {
            if(arr[ind](l) > seg(l))
            {
                arr[ind] = seg;
            }
           return;
        }
        int mid = (l + r) / 2;
        if(seg.m > arr[ind].m) swap(arr[ind], seg);
        if(arr[ind](mid) > seg(mid))
        {
            swap(arr[ind], seg);
            add(ind * 2 + 1, l, mid, seg);
        }
        else
        {
            add(ind * 2 + 2, mid + 1, r, seg);
        }
    }
    long long query(int ind, int l, int r, int x)
    {
        if(l == r)
        {
            return arr[ind](x);
        }
        int mid = (l + r) / 2;
        long long ans = arr[ind](x);
        if(x <= mid) return min(ans, query(ind * 2 + 1, l, mid, x));
        else return min(ans, query(ind * 2 + 2, mid + 1, r, x));
    }
}tree;
void read()
{
    cin>>n;
    for(int i = 0; i < n; i ++)
    {
        cin>>h[i];
    }
    for(int i = 0; i < n; i ++)
    {
        cin>>w[i];
        total += w[i];
    }
}
void solve()
{
    cur = -w[0];
    tree.add(0, 0, 1e6 + 1, Line(-2 * h[0], h[0] * h[0] + cur));
    for(int i = 1; i < n; i ++)
    {
        cur = tree.query(0, 0, 1e6 + 1, h[i]) - w[i] + h[i] * h[i];
        //cout<<cur<<": "<<tree.query(0, 0, 1e6 + 1, h[i])<<" "<<-w[i]<<" "<<h[i]<<endl;
        tree.add(0, 0, 1e6 + 1, Line(-2 * h[i], cur + h[i] * h[i]));
    }
    cout<<cur + total<<endl;
}
signed main()
{
    read();
    solve();
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4028 KB Output is correct
2 Correct 55 ms 4944 KB Output is correct
3 Correct 55 ms 5032 KB Output is correct
4 Correct 51 ms 4692 KB Output is correct
5 Incorrect 48 ms 6228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -