oj.uz

Submission #638019

# Submission time Handle Problem Language Result Execution time Memory
638019 2022-09-04T09:06:37 Z gamo Building Bridges (CEOI17_building) C++17
100 / 100
 80 ms 66400 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62932 KB Output is correct
2 Correct 29 ms 62868 KB Output is correct
3 Correct 32 ms 62948 KB Output is correct
4 Correct 26 ms 63000 KB Output is correct
5 Correct 26 ms 62944 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 66248 KB Output is correct
2 Correct 66 ms 66196 KB Output is correct
3 Correct 80 ms 66248 KB Output is correct
4 Correct 60 ms 66112 KB Output is correct
5 Correct 51 ms 66096 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62932 KB Output is correct
2 Correct 29 ms 62868 KB Output is correct
3 Correct 32 ms 62948 KB Output is correct
4 Correct 26 ms 63000 KB Output is correct
5 Correct 26 ms 62944 KB Output is correct
6 Correct 63 ms 66248 KB Output is correct
7 Correct 66 ms 66196 KB Output is correct
8 Correct 80 ms 66248 KB Output is correct
9 Correct 60 ms 66112 KB Output is correct
10 Correct 51 ms 66096 KB Output is correct
11 Correct 65 ms 66400 KB Output is correct
12 Correct 68 ms 66244 KB Output is correct
13 Correct 51 ms 66328 KB Output is correct
14 Correct 60 ms 66380 KB Output is correct
15 Correct 56 ms 66056 KB Output is correct
16 Correct 53 ms 66124 KB Output is correct
17 Correct 40 ms 66252 KB Output is correct
18 Correct 40 ms 66252 KB Output is correct