oj.uz

Submission #791203

# Submission time Handle Problem Language Result Execution time Memory
791203 2023-07-23T15:41:00 Z nonono Building Bridges (CEOI17_building) C++14
0 / 100
 39 ms 11880 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) {
    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];
    }
    
    for(int i = 1; i <= (n << 2); i ++) {
        line[i] = {0, 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:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10832 KB Output is correct
2 Correct 36 ms 10872 KB Output is correct
3 Correct 37 ms 10816 KB Output is correct
4 Correct 38 ms 10640 KB Output is correct
5 Incorrect 32 ms 11880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -