oj.uz

Submission #791206

# Submission time Handle Problem Language Result Execution time Memory
791206 2023-07-23T15:54:23 Z nonono Building Bridges (CEOI17_building) C++14
100 / 100
 69 ms 67220 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 1e18;
const int mxN = 1e5 + 10;
const int mxM = 1e6 + 10;

int n;
int h[mxN], w[mxN];
int pref[mxN];
int dp[mxN];

int sqr(int x) {
    return x * x;
}

int f(pair<int, int> a, int x) {
    if(a.first == inf) return inf;
    return a.first * x + a.second;
}

pair<int, int> line[mxM << 2];

void add_line(int id, int l, int r, pair<int, int> nw) {
    if(f(nw, l) >= f(line[id], l) && f(nw, r) >= f(line[id], r)) return ;
    if(f(nw, l) <= f(line[id], l) && f(nw, r) <= f(line[id], r)) {
        swap(line[id], nw);
        return ;
    }
    
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[id], l);
    bool mid = f(nw, m) < f(line[id], m);
    
    if(mid) {
        swap(line[id], nw);
    }
    
    if(r - l == 1) {
        return ;
    } else if(lef != mid) {
        add_line(id * 2, l, m, nw);
    } else {
        add_line(id * 2 + 1, m, r, nw);
    }
}

int get(int id, int l, int r, int x) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[id], x);
    } else if(x < m) {
        return min(f(line[id], x), get(id * 2, l, m, x));
    } else {
        return min(f(line[id], x), get(id * 2 + 1, m, r, x));
    }
}

signed main() {
    #define taskname ""

    if(fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }

    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n;
    
    for(int i = 1; i <= n; i ++) cin >> h[i];
    for(int i = 1; i <= n; i ++) cin >> w[i];
    
    for(int i = 1; i <= n; i ++) {
        pref[i] = pref[i - 1] + w[i];
    }
    
    int N = 1e6 + 1;
    for(int i = 1; i <= (N << 2); i ++) {
        line[i] = {inf, inf};
    }
    
    dp[1] = 0;
    add_line(1, 0, 1e6 + 1, make_pair(- 2 * h[1], sqr(h[1]) + dp[1] - pref[1]));
    
    for(int i = 2; i <= n; i ++) {
        dp[i] = get(1, 0, 1e6 + 1, h[i]) + sqr(h[i]) + pref[i - 1];
        add_line(1, 0, 1e6 + 1, make_pair(- 2 * h[i], sqr(h[i]) + dp[i] - pref[i]));
    }
    
    cout << dp[n] << "\n";
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 23 ms 62824 KB Output is correct
3 Correct 23 ms 62856 KB Output is correct
4 Correct 23 ms 62956 KB Output is correct
5 Correct 24 ms 62932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 66056 KB Output is correct
2 Correct 60 ms 65956 KB Output is correct
3 Correct 64 ms 66024 KB Output is correct
4 Correct 58 ms 65988 KB Output is correct
5 Correct 53 ms 65932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 23 ms 62824 KB Output is correct
3 Correct 23 ms 62856 KB Output is correct
4 Correct 23 ms 62956 KB Output is correct
5 Correct 24 ms 62932 KB Output is correct
6 Correct 63 ms 66056 KB Output is correct
7 Correct 60 ms 65956 KB Output is correct
8 Correct 64 ms 66024 KB Output is correct
9 Correct 58 ms 65988 KB Output is correct
10 Correct 53 ms 65932 KB Output is correct
11 Correct 69 ms 67212 KB Output is correct
12 Correct 67 ms 66984 KB Output is correct
13 Correct 58 ms 67148 KB Output is correct
14 Correct 63 ms 67220 KB Output is correct
15 Correct 58 ms 66952 KB Output is correct
16 Correct 52 ms 66936 KB Output is correct
17 Correct 43 ms 67028 KB Output is correct
18 Correct 42 ms 67116 KB Output is correct