oj.uz

Submission #154442

# Submission time Handle Problem Language Result Execution time Memory
154442 2019-09-21T20:45:00 Z dolphingarlic Building Bridges (CEOI17_building) C++14
0 / 100
 34 ms 3704 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

set<pair<ll, ll>> lines;
ll h[100001], w[100001], tot = 0;
ll dp[100001];

bool check(ll h, pair<ll, ll> l1, pair<ll, ll> l2) {
    return (-l2.first * h + l2.second <= -l1.first * h + l1.second);
}
ll calc(ll h, pair<ll, ll> l) {
    return (-l.first * h + l.second);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) cin >> h[i];
    FOR(i, 1, n + 1) {
        cin >> w[i];
        tot += w[i];
    }

    dp[1] = -w[1];
    lines.insert({2 * h[1], dp[1] + h[1] * h[1]});
    FOR(i, 2, n + 1) {
        while (check(h[i], *lines.begin(), *next(lines.begin()))) lines.erase(lines.begin());
        dp[i] = calc(h[i], *lines.begin()) - w[i] + h[i] * h[i];
        lines.insert({2 * h[i], dp[i] + h[i] * h[i]});
    }

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

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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