oj.uz

Submission #868295

# Submission time Handle Problem Language Result Execution time Memory
868295 2023-10-31T03:12:22 Z Truly_ Building Bridges (CEOI17_building) C++14
100 / 100
 51 ms 65620 KB 
#define nametask "bridgepol"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define SZ(a) (int) a.size()
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FOD(i, b, a) for (int i = b; i >= a; i--)
#define int long long

using namespace std;
typedef long long ll;
typedef pair <int, int> pi;
const int N = 1e5 + 5;
const int oo = 1e12 + 10;
const int MAX = 1e6;

struct line{
    int a, b;
    line(){
        a = b = oo;
    }
};

int n;
int h[N], w[N];
int s[N];
line t[4 * MAX + 5];

int calc(line y, int x){
    return (1LL * y.a * x + y.b);
}

void upd_it(int id, int l, int r, line y){
    int mid = (l + r) / 2;
    if (calc(t[id], l) <= calc(y, l) && calc(t[id], r) <= calc(y, r)) return;
    if (calc(t[id], l) >= calc(y, l) && calc(t[id], r) >= calc(y, r)){
        t[id] = y;
        return;
    }
    if (calc(t[id], l) <= calc(y, l) && calc(t[id], mid) <= calc(y, mid)){
        upd_it(id * 2 + 1, mid + 1, r, y);
        return;
    }
    if (calc(t[id], l) >= calc(y, l) && calc(t[id], mid) >= calc(y, mid)){
        upd_it(id * 2 + 1, mid + 1, r, t[id]);
        t[id] = y;
        return;
    }
    if (calc(t[id], mid + 1) <= calc(y, mid + 1) && calc(t[id], r) <= calc(y, r)){
        upd_it(id * 2, l, mid, y);
        return;
    }
    if (calc(t[id], mid + 1) >= calc(y, mid + 1) && calc(t[id], r) >= calc(y, r)){
        upd_it(id * 2, l, mid, t[id]);
        t[id] = y;
        return;
    }
    upd_it(id * 2, l, mid, y);
    upd_it(id * 2 + 1, mid + 1, r, y);
}

int get_it(int id, int l, int r, int u){
    if (l > u || r < u) return ((int)1e18);
    int mid = (l + r) / 2;
    int res = calc(t[id], u);
    if (l == r) return res;
    res = min(res, get_it(id * 2, l, mid, u));
    res = min(res, get_it(id * 2 + 1, mid + 1, r, u));
    return res;
}

void solve(){
    line tmp;
    tmp.a = -2 * h[1];
    tmp.b = -w[1] + 1LL * h[1] * h[1];
    upd_it(1, 0, MAX, tmp);
    FOR(i, 2, n - 1){
        int val = get_it(1, 0, MAX, h[i]) - w[i] + 1LL * h[i] * h[i];
        tmp.a = -2 * h[i];
        tmp.b = val + 1LL * h[i] * h[i];
        upd_it(1, 0, MAX, tmp);
    }
    cout << s[n] + get_it(1, 0, MAX, h[n]) - w[n] + 1LL * h[n] * h[n];
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    if (fopen(nametask".inp", "r")){
        freopen(nametask".inp", "r", stdin);
        freopen(nametask".out", "w", stdout);
    }
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> w[i];
    FOR(i, 1, n) s[i] = s[i - 1] + w[i];
    solve();
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64088 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 9 ms 64172 KB Output is correct
4 Correct 9 ms 64148 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 65368 KB Output is correct
2 Correct 47 ms 65372 KB Output is correct
3 Correct 47 ms 65620 KB Output is correct
4 Correct 46 ms 65372 KB Output is correct
5 Correct 42 ms 65372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64088 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 9 ms 64172 KB Output is correct
4 Correct 9 ms 64148 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 48 ms 65368 KB Output is correct
7 Correct 47 ms 65372 KB Output is correct
8 Correct 47 ms 65620 KB Output is correct
9 Correct 46 ms 65372 KB Output is correct
10 Correct 42 ms 65372 KB Output is correct
11 Correct 49 ms 65260 KB Output is correct
12 Correct 51 ms 65372 KB Output is correct
13 Correct 42 ms 65368 KB Output is correct
14 Correct 48 ms 65368 KB Output is correct
15 Correct 46 ms 65404 KB Output is correct
16 Correct 43 ms 65372 KB Output is correct
17 Correct 33 ms 65372 KB Output is correct
18 Correct 33 ms 65412 KB Output is correct