oj.uz

Submission #956151

# Submission time Handle Problem Language Result Execution time Memory
956151 2024-04-01T07:58:16 Z Aiperiii Building Bridges (CEOI17_building) C++14
30 / 100
 67 ms 36708 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;
}
int get(int v,int tl,int tr,int x){
    if(tl==tr)return f(t[v].ff,tl,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));
}
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(t[v].ff>m){
            swap(t[v].ff,m);
            swap(t[v].ss,c);
        }
        if(f(t[v].ff,tm,t[v].ss)<=f(m,tm,c)){
            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};
        }
    }
}
signed main(){
    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 11 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 36692 KB Output is correct
2 Correct 66 ms 36688 KB Output is correct
3 Correct 67 ms 36688 KB Output is correct
4 Correct 63 ms 36708 KB Output is correct
5 Incorrect 59 ms 36692 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 8 ms 33372 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 66 ms 36692 KB Output is correct
7 Correct 66 ms 36688 KB Output is correct
8 Correct 67 ms 36688 KB Output is correct
9 Correct 63 ms 36708 KB Output is correct
10 Incorrect 59 ms 36692 KB Output isn't correct
11 Halted 0 ms 0 KB -