oj.uz

Submission #869645

# Submission time Handle Problem Language Result Execution time Memory
869645 2023-11-05T07:23:16 Z MON Building Bridges (CEOI17_building) C++17
100 / 100
 84 ms 65872 KB 
#include<iostream>
using namespace std;
using ll = long long;

constexpr int CHAO = 1e6 + 1;

struct line
{
    int m; ll b;
    line(int a,ll c) : m(a),b(c) {}
    line() : m(0),b(1LL<<62) {}
    ll operator ()(int x){return 1LL * x * m + b;}
}li[CHAO * 4];

void baga(line f,int a = 1,int l = 0,int r = CHAO)
{
    if(l + 1 == r)
        {
            if(f(l) < li[a](l))
                swap(f,li[a]);
            return;
        }

    int mid = l + (r - l) / 2;
    if(f.m > li[a].m) swap(f,li[a]);
    if(f(mid) < li[a](mid)) swap(f,li[a]),baga(f,a<<1,l,mid);
    else baga(f,a<<1|1,mid,r);

}

ll get(int x,int a = 1 ,int l = 0 , int r = CHAO)
{
    if(l + 1 == r) return li[a](x);
    int mid = l + (r - l) / 2;
    if(x < mid) return min(li[a](x),get(x,a<<1,l,mid));
    return min(li[a](x),get(x,a<<1|1,mid,r));
}

int main()
{
    int n; cin >> n; int h[n + 1],w[n + 1];
    ll ans = 0; for(int i = 1; i <= n ; i++) cin >> h[i];
    for(int i = 1; i <= n ; i++) cin >> w[i],ans += w[i];
    ll dp[n + 1]; dp[1] = -w[1]; baga(line(-2 * h[1],1LL * h[1] * h[1] - w[1]));
    for(int i = 2; i <= n ; i++)
    {
        dp[i] = get(h[i]) + 1LL * h[i] * h[i] -w[i];
        baga(line(-2*h[i],1LL * h[i] * h[i] + dp[i]));
    }

    cout << ans + dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62812 KB Output is correct
2 Correct 10 ms 62812 KB Output is correct
3 Correct 9 ms 62812 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 65616 KB Output is correct
2 Correct 68 ms 65712 KB Output is correct
3 Correct 69 ms 65600 KB Output is correct
4 Correct 66 ms 65872 KB Output is correct
5 Correct 61 ms 65364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62812 KB Output is correct
2 Correct 10 ms 62812 KB Output is correct
3 Correct 9 ms 62812 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63072 KB Output is correct
6 Correct 68 ms 65616 KB Output is correct
7 Correct 68 ms 65712 KB Output is correct
8 Correct 69 ms 65600 KB Output is correct
9 Correct 66 ms 65872 KB Output is correct
10 Correct 61 ms 65364 KB Output is correct
11 Correct 79 ms 65620 KB Output is correct
12 Correct 75 ms 65468 KB Output is correct
13 Correct 69 ms 65616 KB Output is correct
14 Correct 84 ms 65872 KB Output is correct
15 Correct 62 ms 65352 KB Output is correct
16 Correct 61 ms 65364 KB Output is correct
17 Correct 59 ms 65620 KB Output is correct
18 Correct 59 ms 65668 KB Output is correct