oj.uz

Submission #858369

# Submission time Handle Problem Language Result Execution time Memory
858369 2023-10-08T09:12:41 Z Tenis0206 Building Bridges (CEOI17_building) C++11
30 / 100
 48 ms 67156 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;
const int hmax = 1e6;
const int oo = INT_MAX;

int n;
int h[nmax + 5], w[nmax + 5];
int sp[nmax + 5];

int dp[nmax + 5];

pair<int,int> lc[4 * hmax + 5];

int get_val(pair<int,int> f, int x)
{
    if(f.first==oo)
    {
        return oo;
    }
    return f.first * x + f.second;
}

bool is_smaller(pair<int,int> f, pair<int,int> g, int x)
{
    return get_val(f, x) < get_val(g, x);
}

int query(int poz, int nod, int st, int dr)
{
    if(st==dr)
    {
        return get_val(lc[nod], poz);
    }
    int mij = (st + dr) >> 1;
    if(poz <= mij)
    {
        return min(get_val(lc[nod],poz), query(poz,nod*2,st,mij));
    }
    return min(get_val(lc[nod],poz), query(poz,nod*2+1,mij+1,dr));
}

void update(pair<int,int> f, int nod, int st, int dr)
{
    int mij = (st + dr) >> 1;
    bool okst = is_smaller(f, lc[nod], st);
    bool okmij = is_smaller(f, lc[nod], mij);
    if(okmij)
    {
        swap(f,lc[nod]);
    }
    if(st==dr)
    {
        return;
    }
    if(okst!=okmij)
    {
        update(f,nod*2,st,mij);
    }
    else
    {
        update(f,nod*2+1,mij+1,dr);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        sp[i] = sp[i - 1] + w[i];
    }
    for(int i=1;i<=4*hmax;i++)
    {
        lc[i] = {oo,oo};
    }
    dp[1] = 0;
    update({-2 * h[1],dp[1] + 1LL * h[1] * h[1] - sp[1]},1,1,hmax);
    for(int i=2;i<=n;i++)
    {
        dp[i] = query(h[i],1,1,hmax) + 1LL * h[i] * h[i] + sp[i - 1];
        update({-2 * h[i],dp[i] + 1LL * h[i] * h[i] - sp[i]},1,1,hmax);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66132 KB Output is correct
2 Correct 43 ms 66996 KB Output is correct
3 Correct 42 ms 67156 KB Output is correct
4 Correct 40 ms 66912 KB Output is correct
5 Incorrect 37 ms 66896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 63064 KB Output is correct
2 Correct 9 ms 63068 KB Output is correct
3 Correct 10 ms 63068 KB Output is correct
4 Correct 9 ms 62952 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 48 ms 66132 KB Output is correct
7 Correct 43 ms 66996 KB Output is correct
8 Correct 42 ms 67156 KB Output is correct
9 Correct 40 ms 66912 KB Output is correct
10 Incorrect 37 ms 66896 KB Output isn't correct
11 Halted 0 ms 0 KB -