oj.uz

Submission #940859

# Submission time Handle Problem Language Result Execution time Memory
940859 2024-03-07T19:06:25 Z vivo2006 Building Bridges (CEOI17_building) C++17
100 / 100
 81 ms 66548 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() {m = b = 1e12 + 10;}
    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 + 10, Line(-2 * h[0], h[0] * h[0] + cur));
    for(int i = 1; i < n; i ++)
    {
        cur = tree.query(0, 0, 1e6 + 10, 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 + 10, 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 64084 KB Output is correct
2 Correct 11 ms 64200 KB Output is correct
3 Correct 10 ms 64152 KB Output is correct
4 Correct 10 ms 64092 KB Output is correct
5 Correct 11 ms 64160 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 65364 KB Output is correct
2 Correct 64 ms 65276 KB Output is correct
3 Correct 65 ms 65452 KB Output is correct
4 Correct 60 ms 65220 KB Output is correct
5 Correct 60 ms 65224 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 64084 KB Output is correct
2 Correct 11 ms 64200 KB Output is correct
3 Correct 10 ms 64152 KB Output is correct
4 Correct 10 ms 64092 KB Output is correct
5 Correct 11 ms 64160 KB Output is correct
6 Correct 67 ms 65364 KB Output is correct
7 Correct 64 ms 65276 KB Output is correct
8 Correct 65 ms 65452 KB Output is correct
9 Correct 60 ms 65220 KB Output is correct
10 Correct 60 ms 65224 KB Output is correct
11 Correct 81 ms 66352 KB Output is correct
12 Correct 68 ms 66304 KB Output is correct
13 Correct 69 ms 66260 KB Output is correct
14 Correct 77 ms 66548 KB Output is correct
15 Correct 67 ms 66132 KB Output is correct
16 Correct 58 ms 66128 KB Output is correct
17 Correct 54 ms 66416 KB Output is correct
18 Correct 53 ms 66284 KB Output is correct