oj.uz

Submission #939562

# Submission time Handle Problem Language Result Execution time Memory
939562 2024-03-06T14:00:50 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 72 ms 36964 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e6+5;
pair <int,int> t[N*4];
void build(int v,int tl,int tr){
    t[v]={1e9,1e18};
    if(tl!=tr){
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
}
int f(int m,int x,int c){
    return m*x+c;
}
void insert(int v,int tl,int tr ,int m,int c){
    if(tl==tr){
        if(f(t[v].ff,tl,t[v].ss)>f(m,tl,c))t[v]={m,c};
    }
    else{
        int tm=(tl+tr)/2;
        if(m<t[v].ff){
            swap(m,t[v].ff);swap(c,t[v].ss);
        }
        if(f(m,tm,c)>=f(t[v].ff,tm,t[v].ss))insert(v*2,tl,tm,m,c);
        else{
            insert(v*2+1,tm+1,tr,t[v].ff,t[v].ss);
            t[v]={m,c};
        }
    }
}
int get(int v,int tl,int tr,int x){
    if(tl==tr)return f(t[v].ff,x,t[v].ss);
    int tm=(tl+tr)/2;
    if(x<=tm)return min(f(t[v].ff,x,t[v].ss),get(v*2,tl,tm,x));
    else return min(f(t[v].ff,x,t[v].ss),get(v*2+1,tm+1,tr,x));
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector <int> h(n+1),w(n+1),dp(n+1);
    for(int i=1;i<=n;i++)cin>>h[i];
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    build(1,1,1e6);
    insert(1,1,1e6,-2*h[1],-w[1]+h[1]*h[1]);
    for(int i=2;i<=n;i++){
        dp[i]=get(1,1,1e6,h[i])+h[i]*h[i]-w[i];
        insert(1,1,1e6,-2*h[i],dp[i]+h[i]*h[i]);
    }
    cout<<dp[n]+sum<<"\n";
}
/*

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 7 ms 33212 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33368 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 36696 KB Output is correct
2 Correct 62 ms 36688 KB Output is correct
3 Correct 63 ms 36816 KB Output is correct
4 Correct 57 ms 36684 KB Output is correct
5 Correct 54 ms 36484 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 7 ms 33212 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33368 KB Output is correct
6 Correct 62 ms 36696 KB Output is correct
7 Correct 62 ms 36688 KB Output is correct
8 Correct 63 ms 36816 KB Output is correct
9 Correct 57 ms 36684 KB Output is correct
10 Correct 54 ms 36484 KB Output is correct
11 Correct 72 ms 36944 KB Output is correct
12 Correct 67 ms 36688 KB Output is correct
13 Correct 63 ms 36688 KB Output is correct
14 Correct 72 ms 36964 KB Output is correct
15 Correct 55 ms 36448 KB Output is correct
16 Correct 55 ms 36684 KB Output is correct
17 Correct 50 ms 36696 KB Output is correct
18 Correct 51 ms 36688 KB Output is correct