oj.uz

Submission #171617

# Submission time Handle Problem Language Result Execution time Memory
171617 2019-12-29T11:58:09 Z nicolaalexandra Building Bridges (CEOI17_building) C++14
100 / 100
 180 ms 37532 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(1000000000000,1000000000000);
    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;
    init (1,1,maxi);
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 33144 KB Output is correct
2 Correct 34 ms 33116 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 35 ms 33144 KB Output is correct
5 Correct 35 ms 33272 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 36984 KB Output is correct
2 Correct 156 ms 36884 KB Output is correct
3 Correct 155 ms 36988 KB Output is correct
4 Correct 150 ms 36984 KB Output is correct
5 Correct 147 ms 36936 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 33144 KB Output is correct
2 Correct 34 ms 33116 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 35 ms 33144 KB Output is correct
5 Correct 35 ms 33272 KB Output is correct
6 Correct 163 ms 36984 KB Output is correct
7 Correct 156 ms 36884 KB Output is correct
8 Correct 155 ms 36988 KB Output is correct
9 Correct 150 ms 36984 KB Output is correct
10 Correct 147 ms 36936 KB Output is correct
11 Correct 180 ms 37532 KB Output is correct
12 Correct 166 ms 37240 KB Output is correct
13 Correct 161 ms 37368 KB Output is correct
14 Correct 178 ms 37528 KB Output is correct
15 Correct 142 ms 37232 KB Output is correct
16 Correct 146 ms 37244 KB Output is correct
17 Correct 143 ms 37368 KB Output is correct
18 Correct 146 ms 37388 KB Output is correct