oj.uz

Submission #132423

# Submission time Handle Problem Language Result Execution time Memory
132423 2019-07-18T19:56:18 Z Vardanyan Building Bridges (CEOI17_building) C++14
60 / 100
 68 ms 10488 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 = 1e18;
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 INF;
    long long u = ln.k*x+ln.b;
   // if(u<0 && ln.k>=0 && x>=0 && ln.b>=0) u = INF;
    return u;
}
struct node{
    node* l;
    node* r;
    line ln;
    node():l(NULL),r(NULL),ln(0,0){}
};
long long maxn = 1000*1000*2;
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 INF;
    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 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4444 KB Output is correct
2 Correct 68 ms 4344 KB Output is correct
3 Correct 68 ms 4344 KB Output is correct
4 Correct 64 ms 3796 KB Output is correct
5 Correct 56 ms 10488 KB Output is 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 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 68 ms 4444 KB Output is correct
7 Correct 68 ms 4344 KB Output is correct
8 Correct 68 ms 4344 KB Output is correct
9 Correct 64 ms 3796 KB Output is correct
10 Correct 56 ms 10488 KB Output is correct
11 Incorrect 67 ms 4828 KB Output isn't correct
12 Halted 0 ms 0 KB -