oj.uz

Submission #881823

# Submission time Handle Problem Language Result Execution time Memory
881823 2023-12-02T03:19:21 Z Zero_OP Building Bridges (CEOI17_building) C++14
0 / 100
 21 ms 8284 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;
typedef long double ld;

struct line{
    ll a, b;
    line(ll a = 0, ll b = 0) : a(a), b(b) {}
    ll eval(ll x){
        return a * x + b;
    }
};

vector<line> lines;
ld slope(const line& A, const line& B){
    return (ld)(B.b - A.b) / (A.a - B.a);
}

void add(line d){
    while(lines.size() > 1 and slope(d, lines.back()) <= slope(lines.back(), lines[lines.size() - 2])){
        lines.pop_back();
    }
    lines.push_back(d);
}

ll query(ll x){
    int l = 0, r = lines.size();
    while(l < r){
        int mid = l + r >> 1;
        if(lines[mid].eval(x) >= lines[mid + 1].eval(x)) l = mid + 1;
        else r = mid;
    }
    return lines[l].eval(x);
}

int n;
ll dp[N], h[N], w[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    add(line(h[1], h[1] * h[1] + dp[1] - w[1]));
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + query(-2 * h[i]);
        add(line(h[i], h[i] * h[i] + dp[i] - w[i]));
    }

    for(int i = 1; i <= n; ++i) cout << dp[i] << " \n"[i == n];

    cout << dp[n];
    return 0;
}

Compilation message

building.cpp: In function 'll query(ll)':
building.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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