oj.uz

Submission #881832

# Submission time Handle Problem Language Result Execution time Memory
881832 2023-12-02T03:27:09 Z Zero_OP Building Bridges (CEOI17_building) C++14
0 / 100
 16 ms 7516 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]));
    }
 
    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 Correct 1 ms 2408 KB Output is correct
2 Incorrect 0 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 16 ms 7516 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 2408 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -