Submission #638019

#	Time	Username	Problem	Language	Result	Execution time	Memory
638019		gamo	Building Bridges (CEOI17_building)	C++17	100 / 100	80 ms	66400 KiB

building

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 7;
const int maxH = 1e6 + 7;
const long long INF = 1e18;
#define SQR(x) (x)*(x)

struct Line {
    long long k,m;
    Line() : k(0), m(INF) {}
    Line(long long _k, long long _m) : k(_k), m(_m) {}
    long long getVal(long long x) {return k*x + m;}
}Tree[maxH <<2];

void CapNhat(int n, int L, int R, Line Dnew) {
    long long nowL = Tree[n].getVal(L);
    long long newL = Dnew.getVal(L);
    long long nowR = Tree[n].getVal(R);
    long long newR = Dnew.getVal(R);

    if (nowL <= newL && nowR <= newR) return;
    if (nowL >= newL && nowR >= newR) {Tree[n] = Dnew; return;}

    if (L == R) return;

    int mid = (L+R) >> 1;
    long long nowM = Tree[n].getVal(mid);
    long long newM = Dnew.getVal(mid);

    if (newM < nowM) swap(Dnew,Tree[n]);

    if ( (nowL <= newL && nowM <= newM) || (nowL >= newL && nowM >= newM) )
        CapNhat(2*n+2, mid+1, R, Dnew);
    else CapNhat(2*n+1, L, mid, Dnew);
}

long long TruyVan(int n, int L, int R, long long x) {
    if (x <L || R < x) return INF;
    long long res = Tree[n].getVal(x);
    if (L<R && res < INF) {
        int mid = (L+R) >> 1;
        if (x <= mid)
            res = min(res, TruyVan(2*n+1,L,mid,x));
        else res = min (res,TruyVan(2*n+2,mid+1,R,x));
    }
    return res;
}

int N,M;
long long H[maxN], W[maxN], F[maxN], A[maxN];

long long costW(int l, int r) {
    if (l+1<r) return W[r-1] - W[l+1];
    return 0;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    long long hmax = 0;
    for (int i=1; i<=N; ++i) {cin >> H[i]; hmax = max(hmax,H[i]);}
    W[0] = 0;
    for (int i=1; i<=N; ++i) {cin >> W[i]; W[i]+= W[i-1];}
    //Dp
    F[1] = 0;
    for (int i=2; i<=N; ++i) {
        Line d = Line(-2*H[i-1], F[i-1]+SQR(H[i-1])- W[i-1]);
        CapNhat(0,0,hmax,d);
        long long x = TruyVan(0,0,hmax,H[i]);
        F[i] = x + SQR(H[i])+W[i-1];
        //cout << x<<" "<<F[i] << endl;
    }
    cout<<F[N];
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40