oj.uz

Submission #700888

# Submission time Handle Problem Language Result Execution time Memory
700888 2023-02-19T10:30:17 Z leeminhduc2 Building Bridges (CEOI17_building) C++17
100 / 100
 119 ms 10756 KB 
///leeminhduc2 on his way to TST
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define ii pair<int,int>
#define sz(x) (int) (x).size()
#define pb push_back
using namespace std;
template<class T1,class T2> bool maximize(T1 &a,T2 b) {return(a<b ? a=b,1:0);};
template<class T1,class T2> bool minimize(T1 &a,T2 b) {return(a>b ? a=b,1:0);};

const int N=1e5+10;
int n,m;
ll h[N],w[N],dp[N];
struct line
{
    ll a,b;
    ll operator()(const ll &x)
    {
        return a*x+b;
    }
};
vector <ll> vec;
line lichao_tree[4*N];

void update(int id,int l,int r,line d)
{

    bool ok1=(d(vec[l])<=lichao_tree[id](vec[l])),ok2=(d(vec[r])<=lichao_tree[id](vec[r]));
    if (ok1&&ok2)
    {
        lichao_tree[id]=d;
    }
    else if (ok1||ok2)
    {
        int mid=(l+r)/2;
        update(id*2,l,mid,d);
        update(id*2+1,mid+1,r,d);
    }
}

ll get(int id,int l,int r,int pos)
{
    if (l==r) return lichao_tree[id](vec[pos]);
    int mid=(l+r)/2;
    if (pos<=mid) return min(lichao_tree[id](vec[pos]),get(id*2,l,mid,pos));
    else return min(lichao_tree[id](vec[pos]),get(id*2+1,mid+1,r,pos));
}

void Lucifer()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> h[i];
    for (int i=1;i<=n;i++)
    {
        cin >> w[i];
        w[i]+=w[i-1];
    }

    for (int i=1;i<=n;i++) vec.pb(h[i]);
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
    m=sz(vec);
    for (int i=1;i<=4*m;i++) lichao_tree[i].a=0,lichao_tree[i].b=1e18;
    for (int i=1;i<=n;i++)
    {
        line d;

        if(i==1) dp[i]=0ll;
        else dp[i]=get(1,0,m-1,lower_bound(vec.begin(),vec.end(),h[i])-vec.begin())+h[i]*h[i]+w[i-1];
        d.a=-2ll*h[i];
        d.b=dp[i]-w[i]+h[i]*h[i];
        update(1,0,m-1,d);
    }
    cout << dp[n];

}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Lucifer();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5040 KB Output is correct
2 Correct 73 ms 5100 KB Output is correct
3 Correct 68 ms 5088 KB Output is correct
4 Correct 67 ms 4540 KB Output is correct
5 Correct 79 ms 10756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 71 ms 5040 KB Output is correct
7 Correct 73 ms 5100 KB Output is correct
8 Correct 68 ms 5088 KB Output is correct
9 Correct 67 ms 4540 KB Output is correct
10 Correct 79 ms 10756 KB Output is correct
11 Correct 88 ms 8736 KB Output is correct
12 Correct 88 ms 8544 KB Output is correct
13 Correct 43 ms 4732 KB Output is correct
14 Correct 119 ms 8648 KB Output is correct
15 Correct 92 ms 10700 KB Output is correct
16 Correct 67 ms 10696 KB Output is correct
17 Correct 19 ms 4548 KB Output is correct
18 Correct 28 ms 4640 KB Output is correct