Submission #1268618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268618		Zero_OP	Building Bridges (CEOI17_building)	C++20	100 / 100	45 ms	7752 KiB

building

#include <bits/stdc++.h>

using namespace std;

bool BEGIN_ALLOC;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

tcT> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

tcT> bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

tcT> using max_heap = priority_queue<T>;
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;

#define task "task"
void setIO(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}

const ll inf = 1e18;
struct Line{
    ll a, b;
    Line() : a(0), b(inf) {}
    Line(ll _a, ll _b) : a(_a), b(_b) {}
    ll eval(ll x){ return a * x + b; }
};

vi coord;
struct LichaoTree{
    vector<Line> st;
    LichaoTree(int n) : st(n << 2) {}

    void add(int id, int l, int r, Line d){
        if(l == r){
            if(st[id].eval(coord[l]) > d.eval(coord[l])) swap(st[id], d);
        } else{
            int mid = l + r >> 1;
            if(st[id].eval(coord[mid]) > d.eval(coord[mid])) swap(st[id], d);
            if(st[id].a > d.a) add(id << 1 | 1, mid + 1, r, d);
            if(st[id].a < d.a) add(id << 1, l, mid, d);
        }
    }

    ll query(int id, int l, int r, ll x){
        if(l == r) return st[id].eval(x);
        int mid = l + r >> 1;
        if(x <= coord[mid]) return min(st[id].eval(x), query(id << 1, l, mid, x));
        else return min(st[id].eval(x), query(id << 1 | 1, mid + 1, r, x));
    }
};

void testcase(){
    int N;
    cin >> N;
    vi h(N), w(N);
    rep(i, 0, N) cin >> h[i];
    rep(i, 0, N) cin >> w[i];

    coord = vi(all(h));
    sort(all(coord)); compact(coord);

    int m = sz(coord);
    LichaoTree tr(m);
    tr.add(1, 0, m - 1, Line(-2 * h[0], 1LL * h[0] * h[0] - w[0]));
    ll sum = w[0];
    rep(i, 1, N){
        ll tmp = tr.query(1, 0, m - 1, h[i]);
        ll dp = 1LL * h[i] * h[i] + sum + tmp;
        if(i == N - 1){
            cout << dp << '\n';
            return;
        }

        sum += w[i];
        tr.add(1, 0, m - 1, Line(-2 * h[i], 1LL * h[i] * h[i] - sum + dp));
    }
}

bool END_ALLOC;
int main(){
    setIO();
    int tests = 1;
    //cin >> tests;
    while(tests--) testcase();
    double static_mem = ((&BEGIN_ALLOC) - (&END_ALLOC)) / (1024.0 * 1024.0);
    cerr << "[Static memory : " << fixed << setprecision(2) << (static_mem) << " MB]\n";
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40