oj.uz

Submission #997426

# Submission time Handle Problem Language Result Execution time Memory
997426 2024-06-12T09:53:04 Z Neco_arc Building Bridges (CEOI17_building) C++17
100 / 100
 90 ms 10696 KB 
#include <bits/stdc++.h>
//#include <bits/debug.hpp>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "xay cau"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n;
ll h[maxn], s[maxn];
ll dp[maxn];

struct CHT {
    vector<pair<ll, ll>> P;
    vector<long double> X;

    void init() { P.clear(), X.clear(); }
    bool empty() { return P.empty(); }

    long double inter(pair<ll, ll> x, pair<ll, ll> y) {
        return 1. * (y.second - x.second) / (x.first - y.first);
    }

    void Add(pair<ll, ll> p) {
        long double Nw = -1e18;
        while(!P.empty()) {
            assert(P.back().first <= p.first);
            if(P.back().first == p.first && P.back().second >= p.second) return;

            Nw = inter(p, P.back());
            if(Nw < X.back()) P.pop_back(), X.pop_back();
            else break;
        }

        P.push_back(p), X.push_back(Nw);
    }

    ll get(ll x) {
        if(P.empty()) return -1e18;
        int it = upper_bound(all(X), x) - X.begin() - 1;
        return P[it].first * x + P[it].second;
    }
} Cht[18];

void Add(pair<ll, ll> p) {
    vector<pair<ll, ll>> P = {p};
    fi(i, 0, 17) {
        if(Cht[i].empty()) {
            sort(all(P), greater<pair<ll, ll>>());
            for(auto [x, y] : P) Cht[i].Add({-x, -y});

            break;
        }
        else {
            for(auto [x, y] : Cht[i].P) P.push_back({-x, -y});
            Cht[i].init();
        }
    }
}

ll get(ll x, ll ans = 1e18) {
    fi(i, 0, 17) ans = min(ans, -Cht[i].get(x));
    return ans;
}

void solve()
{

    cin >> n;
    fi(i, 1, n) cin >> h[i];
    fi(i, 1, n) {
        ll x; cin >> x;
        s[i] = s[i - 1] + x;
    }

    Add({ -2 * h[1], h[1] * h[1] - s[1] + dp[1] });
    fi(i, 2, n) {
        dp[i] = get(h[i]) + s[i - 1] + h[i] * h[i];
        Add({ -2 * h[i], h[i] * h[i] - s[i] + dp[i] });
    }

    cout << dp[n];
}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5584 KB Output is correct
2 Correct 90 ms 5624 KB Output is correct
3 Correct 90 ms 5568 KB Output is correct
4 Correct 76 ms 4944 KB Output is correct
5 Correct 47 ms 6656 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 90 ms 5584 KB Output is correct
7 Correct 90 ms 5624 KB Output is correct
8 Correct 90 ms 5568 KB Output is correct
9 Correct 76 ms 4944 KB Output is correct
10 Correct 47 ms 6656 KB Output is correct
11 Correct 80 ms 5204 KB Output is correct
12 Correct 87 ms 5684 KB Output is correct
13 Correct 41 ms 4948 KB Output is correct
14 Correct 87 ms 5536 KB Output is correct
15 Correct 68 ms 10696 KB Output is correct
16 Correct 50 ms 6656 KB Output is correct
17 Correct 33 ms 4948 KB Output is correct
18 Correct 24 ms 4952 KB Output is correct