oj.uz

Submission #320686

# Submission time Handle Problem Language Result Execution time Memory
320686 2020-11-09T14:04:07 Z phathnv Building Bridges (CEOI17_building) C++11
100 / 100
 125 ms 9956 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const ll INF = 1e18;

struct line{
    ll a, b;
    line(ll _a = 0, ll _b = 0){
        a = _a;
        b = _b;
    }
    ll y(int x){
        return a * x + b;
    }
};

struct segmentTree{
    line d[N * 4];
    int x[N];
    void build(int id, int l, int r, int _x[]){
        d[id] = line(0, INF);
        if (l == r){
            x[l] = _x[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, _x);
        build(id << 1 | 1, mid + 1, r, _x);
    }
    void addLine(int id, int l, int r, line val){
        if (val.y(x[l]) >= d[id].y(x[l]) && val.y(x[r]) >= d[id].y(x[r]))
            return;
        if (val.y(x[l]) <= d[id].y(x[l]) && val.y(x[r]) <= d[id].y(x[r])){
            d[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        addLine(id << 1, l, mid, val);
        addLine(id << 1 | 1, mid + 1, r, val);
    }
    ll getMin(int id, int l, int r, int pos){
        if (pos < l || r < pos)
            return INF;
        ll res = d[id].y(x[pos]);
        if (l == r)
            return res;
        int mid = (l + r) >> 1;
        res = min(res, getMin(id << 1, l, mid, pos));
        res = min(res, getMin(id << 1 | 1, mid + 1, r, pos));
        return res;
    }
} ST;

int n, h[N], w[N];
int x[N], nX;
ll s[N];

void readInput(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
}

void solve(){
    for(int i = 1; i <= n; i++){
        s[i] = s[i - 1] + w[i];
        x[i] = h[i];
    }
    sort(x + 1, x + 1 + n);
    nX = unique(x + 1, x + 1 + n) - (x + 1);

    ll res = 0;
    ST.build(1, 1, nX, x);
    ST.addLine(1, 1, nX, line(-2 * h[1], (ll) h[1] * h[1] - s[1]));
    for(int i = 2; i <= n; i++){
        int pos = lower_bound(x + 1, x + 1 + nX, h[i]) - x;
        res = ST.getMin(1, 1, nX, pos) + (ll) h[i] * h[i] + s[i - 1];
        ST.addLine(1, 1, nX, line(-2 * h[i], res + (ll) h[i] * h[i] - s[i]));
    }
    printf("%lld", res);
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message

building.cpp: In function 'void readInput()':
building.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
building.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%d", &h[i]);
      |         ~~~~~^~~~~~~~~~~~~
building.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%d", &w[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9352 KB Output is correct
2 Correct 94 ms 9316 KB Output is correct
3 Correct 96 ms 9324 KB Output is correct
4 Correct 80 ms 9316 KB Output is correct
5 Correct 84 ms 9700 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 93 ms 9352 KB Output is correct
7 Correct 94 ms 9316 KB Output is correct
8 Correct 96 ms 9324 KB Output is correct
9 Correct 80 ms 9316 KB Output is correct
10 Correct 84 ms 9700 KB Output is correct
11 Correct 107 ms 9956 KB Output is correct
12 Correct 123 ms 9956 KB Output is correct
13 Correct 61 ms 9828 KB Output is correct
14 Correct 125 ms 9956 KB Output is correct
15 Correct 84 ms 9836 KB Output is correct
16 Correct 85 ms 9836 KB Output is correct
17 Correct 33 ms 9700 KB Output is correct
18 Correct 32 ms 9580 KB Output is correct