oj.uz

Submission #961841

# Submission time Handle Problem Language Result Execution time Memory
961841 2024-04-12T14:47:41 Z LucaIlie Building Bridges (CEOI17_building) C++17
0 / 100
 37 ms 3744 KB 
#include <bits/stdc++.h>

using namespace std;

struct func1 {
    long long a, b;

    long long operator() ( long long x ) {
        return a * x + b;
    }
};

const int MAX_N = 1e5;
const int MAX_H = 10;
long long h[MAX_N], w[MAX_N], dp[MAX_N];
func1 maxFunc[4 * MAX_H];

void addLine( int v, int l, int r, func1 f ) {
    int mid = (l + r) / 2;

    if ( maxFunc[v].a < f.a )
        swap( maxFunc[v], f );

    if ( f( mid ) < maxFunc[v]( mid ) ) {
        swap( maxFunc[v], f );
        if ( l != r )
            addLine( v * 2 + 1, l, mid, f );
    } else {
        if ( l != r )
            addLine( v * 2 + 2, mid + 1, r, f );
    }
}

long long getMin( int v, int l, int r, int x ) {
    if ( l == r )
        return maxFunc[v]( x );

    int mid = (l + r) / 2;
    if ( x <= mid )
        return min( maxFunc[v]( x ), getMin( v * 2 + 1, l, mid, x ) );
    return min( maxFunc[v]( x ), getMin( v * 2 + 2, mid + 1, r, x ) );
}

int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ )
        cin >> h[i];
    for ( int i = 0; i < n; i++ )
        cin >> w[i];
    for ( int i = 1; i < n; i++ )
        w[i] += w[i - 1];

    for ( int v = 0; v < 4 * MAX_H; v++ )
        maxFunc[v] = { (long long)1e7, (long long)1e12 };
    addLine( 0, 1, MAX_H, { -2 * h[0], dp[0] - w[0] + h[0] * h[0] } );
    for ( int i = 1; i < n; i++ ) {
        dp[i] = getMin( 0, 1, MAX_H, h[i] ) + w[i - 1] + h[i] * h[i];
        addLine( 0, 1, MAX_H, { -2 * h[i], dp[i] - w[i] + h[i] * h[i] } );
    }

    cout << dp[n - 1];

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 3744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -