oj.uz

Submission #132414

# Submission time Handle Problem Language Result Execution time Memory
132414 2019-07-18T19:45:02 Z Vardanyan Building Bridges (CEOI17_building) C++14
30 / 100
 107 ms 6772 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000*100+5;
long long dp[N];
long long a[N];
long long b[N];
long long pref[N];
const long long INF = 100000000000000;
struct line{
    long long k,b;
    line():k(0),b(0){}
    line(long long _k,long long _b):k(_k),b(_b){}
};
long long f(line ln,long long x){
    if(ln.k+ln.b == 0) return 1000000000000000000;
    return ln.k*x+ln.b;
}
struct node{
    node* l;
    node* r;
    line ln;
    node():l(NULL),r(NULL),ln(0,0){}
};
long long maxn = INF;
void add_line(node* v,line ln,long long l = -maxn,long long r = maxn){
    if(l>r) return;
    long long m = (l+r)/2;
    bool lef = f(ln,l)<f(v->ln,l);
    bool mid = f(ln,m)<f(v->ln,m);
    if(mid){
        swap(v->ln,ln);
    }
    if(lef!=mid){
        if(v->l == NULL) v->l = new node();
        add_line(v->l,ln,l,m);
    }
    else{
        if(v->r == NULL) v->r = new node();
        add_line(v->r,ln,m+1,r);
    }
}
long long get(node* v,long long x,long long l = -maxn,long long r = maxn){
    if(v == NULL || l>r) return 1000000000000000000;
    if(l == r){
        return f(v->ln,x);
    }
    long long m = (l+r)/2;
    if(f(v->ln,x)<f(v->ln,m)){
        return min(f(v->ln,x),get(v->l,x,l,m));
    }
    else{
        return min(f(v->ln,x),get(v->r,x,m+1,r));
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=n;i++){
        cin>>b[i];
        pref[i] = pref[i-1]+b[i];
       // dp[i] = INF;
    }
    dp[1] = 0;
    node* root = new node();
    add_line(root,line(a[1],dp[1]+a[1]*a[1]-pref[1]));
    for(int i = 2;i<=n;i++){
        /*for(int j = 1;j<i;j++){
            dp[i] = min(dp[i],dp[j]+(a[i]-a[j])*(a[i]-a[j])+pref[i-1]-pref[j]);
        }*/
        long long x = get(root,-2*a[i]);
        dp[i] = x+a[i]*a[i]+pref[i-1];
        add_line(root,line(a[i],dp[i]+a[i]*a[i]-pref[i]));
   //     cout<<dp[i]<<endl;
    }
    cout<<dp[n]<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 4420 KB Output is correct
2 Correct 102 ms 4472 KB Output is correct
3 Correct 107 ms 4484 KB Output is correct
4 Correct 96 ms 3752 KB Output is correct
5 Incorrect 86 ms 6772 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 103 ms 4420 KB Output is correct
7 Correct 102 ms 4472 KB Output is correct
8 Correct 107 ms 4484 KB Output is correct
9 Correct 96 ms 3752 KB Output is correct
10 Incorrect 86 ms 6772 KB Output isn't correct