oj.uz

Submission #310924

# Submission time Handle Problem Language Result Execution time Memory
310924 2020-10-08T14:23:56 Z BeanZ Building Bridges (CEOI17_building) C++14
100 / 100
 97 ms 67364 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int lim = 1e6;
const int mod = 1e9 + 7;
pair<ll, ll> st[N * 4];
ll h[N], dp[N], sum[N], w[N];
ll f(pair<ll, ll> x, ll v){
    return x.first * v + x.second;
}
void add(pair<ll, ll> x, ll k, ll l, ll r){
    ll mid = (l + r) >> 1;
    bool left = f(x, l) < f(st[k], l);
    bool m = f(x, mid) < f(st[k], mid);
    if (m) swap(st[k], x);
    if (l == r) return;
    else if (left != m) add(x, k << 1, l, mid);
    else add(x, k << 1 | 1, mid + 1, r);
}
ll get(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    ll res = f(st[k], v);
    if (l == r) return res;
    else if (v <= mid) return min(res, get(k << 1, l, mid, v));
    else return min(res, get(k << 1 | 1, mid + 1, r, v));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i], sum[i] = sum[i - 1] + w[i];
    for (int i = 1; i <= (lim * 4); i++) st[i] = {0, 3e17};
    add({-2 * h[1], h[1] * h[1] - w[1] + dp[1]}, 1, 1, lim);
    for (int i = 2; i <= n; i++){
        dp[i] = sum[i - 1] + h[i] * h[i] + get(1, 1, lim, h[i]);
        add({-2 * h[i], h[i] * h[i] - sum[i] + dp[i]}, 1, 1, lim);
    }
    cout << dp[n];
}
/*
*/

Compilation message

building.cpp: In function 'int main()':
building.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62968 KB Output is correct
2 Correct 34 ms 63012 KB Output is correct
3 Correct 35 ms 62968 KB Output is correct
4 Correct 35 ms 62968 KB Output is correct
5 Correct 34 ms 62968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 67156 KB Output is correct
2 Correct 89 ms 67192 KB Output is correct
3 Correct 83 ms 67196 KB Output is correct
4 Correct 83 ms 67064 KB Output is correct
5 Correct 77 ms 67064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62968 KB Output is correct
2 Correct 34 ms 63012 KB Output is correct
3 Correct 35 ms 62968 KB Output is correct
4 Correct 35 ms 62968 KB Output is correct
5 Correct 34 ms 62968 KB Output is correct
6 Correct 88 ms 67156 KB Output is correct
7 Correct 89 ms 67192 KB Output is correct
8 Correct 83 ms 67196 KB Output is correct
9 Correct 83 ms 67064 KB Output is correct
10 Correct 77 ms 67064 KB Output is correct
11 Correct 92 ms 67364 KB Output is correct
12 Correct 97 ms 67064 KB Output is correct
13 Correct 77 ms 67260 KB Output is correct
14 Correct 95 ms 67320 KB Output is correct
15 Correct 74 ms 67052 KB Output is correct
16 Correct 76 ms 67064 KB Output is correct
17 Correct 71 ms 67332 KB Output is correct
18 Correct 67 ms 67192 KB Output is correct