oj.uz

Submission #171612

# Submission time Handle Problem Language Result Execution time Memory
171612 2019-12-29T11:47:27 Z nicolaalexandra Building Bridges (CEOI17_building) C++14
0 / 100
 123 ms 5368 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define DIMM 1000010
#define INF 1000000000000000000LL
using namespace std;

pair <long long,long long> aint[DIMM*4];
long long h[DIM],w[DIM],sp[DIM],dp[DIM];
int n,i;
long long maxi;
long long f (long long a, long long b, long long x){
    return a*x+b;
}
void add (long long nod, long long st, long long dr, long long a, long long b){
    if (st == dr){
        if (f(a,b,st) < f(aint[nod].first,aint[nod].second,st))
            aint[nod] = make_pair (a,b);
        return;
    }
    long long mid = (st+dr)>>1;
    int ok_mid = 0, ok_dr = 0;
    if (f(a,b,mid) < f(aint[nod].first,aint[nod].second,mid))
        ok_mid = 1;
    if (f(a,b,dr) < f(aint[nod].first,aint[nod].second,dr))
        ok_dr = 1;
    if (!ok_mid && !ok_dr) /// ma duc in stanga
        add (nod<<1,st,mid,a,b);
    else {
        if (!ok_mid && ok_dr)
            add ((nod<<1)|1,mid+1,dr,a,b);
        else {
            /// inseamna ca ok_mid = 1
            swap (aint[nod].first,a);
            swap (aint[nod].second,b);
            if (ok_dr)
                add (nod<<1,st,mid,a,b);
            else add ((nod<<1)|1,mid+1,dr,a,b);
        }
    }
}
long long query (long long nod, long long st, long long dr, long long x){
    if (st == dr)
        return f(aint[nod].first,aint[nod].second,x);

    long long mid = (st+dr)>>1;
    long long sol = INF;
    if (x <= mid)
        sol = query (nod<<1,st,mid,x);
    else sol = query ((nod<<1)|1,mid+1,dr,x);
    return min (sol,f(aint[nod].first,aint[nod].second,x));
}
void init (long long nod, long long st, long long dr){
    aint[nod] = make_pair(INF,INF);
    if (st == dr)
        return;
    long long mid = (st+dr)>>1;
    init (nod<<1,st,mid);
    init ((nod<<1)|1,mid+1,dr);
}
int main (){

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>h[i];
        maxi = max (maxi,h[i]);
    }
    for (i=1;i<=n;i++){
        cin>>w[i];
        sp[i] = sp[i-1] + w[i];
    }
    /// pe primul si ultimul le iau obligatoriu
    /// dp[i] - costul minim sa ajung in i
    //for (i=2;i<=n;i++)
      //  dp[i] = (h[i]-h[1])*(h[i]-h[1]) + sp[i-1]-sp[1];
    maxi = 1000000;
    add (1,1,maxi,-2*h[1],h[1]*h[1]-w[1]);
    for (i=2;i<=n;i++){
        dp[i] = h[i]*h[i] + sp[i-1] + query (1,1,maxi,h[i]);
        add (1,1,maxi,-2*h[i],dp[i]+h[i]*h[i]-sp[i]);
    }
    cout<<dp[n];

    return 0;
}

Subtask #1
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 504 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Incorrect 4 ms 680 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4088 KB Output is correct
2 Correct 122 ms 4088 KB Output is correct
3 Correct 123 ms 4152 KB Output is correct
4 Correct 117 ms 3968 KB Output is correct
5 Incorrect 115 ms 5368 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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Incorrect 4 ms 680 KB Output isn't correct