oj.uz

Submission #868296

# Submission time Handle Problem Language Result Execution time Memory
868296 2023-10-31T03:14:31 Z Truly_ Building Bridges (CEOI17_building) C++14
100 / 100
 55 ms 64608 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--)

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

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

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

ll 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);
}

ll get_it(int id, int l, int r, int u){
    if (l > u || r < u) return ((ll)1e18);
    int mid = (l + r) / 2;
    ll 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){
        ll 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:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(nametask".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 64532 KB Output is correct
2 Correct 50 ms 64600 KB Output is correct
3 Correct 48 ms 64604 KB Output is correct
4 Correct 46 ms 64608 KB Output is correct
5 Correct 46 ms 64600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64092 KB Output is correct
2 Correct 9 ms 64092 KB Output is correct
3 Correct 9 ms 64092 KB Output is correct
4 Correct 10 ms 64092 KB Output is correct
5 Correct 9 ms 64140 KB Output is correct
6 Correct 55 ms 64532 KB Output is correct
7 Correct 50 ms 64600 KB Output is correct
8 Correct 48 ms 64604 KB Output is correct
9 Correct 46 ms 64608 KB Output is correct
10 Correct 46 ms 64600 KB Output is correct
11 Correct 50 ms 64604 KB Output is correct
12 Correct 53 ms 64604 KB Output is correct
13 Correct 44 ms 64604 KB Output is correct
14 Correct 50 ms 64604 KB Output is correct
15 Correct 46 ms 64548 KB Output is correct
16 Correct 43 ms 64604 KB Output is correct
17 Correct 33 ms 64600 KB Output is correct
18 Correct 32 ms 64600 KB Output is correct