Submission #1268611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268611		Zero_OP	Building Bridges (CEOI17_building)	C++17	0 / 100	98 ms	196608 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);
    }
}

#ifdef LOCAL
    #define dbg(...) (cerr << "#" << __LINE__ << " [" << #__VA_ARGS__ << "] = ", print_dbg(__VA_ARGS__))
    #define ASSERT(cond) if(!(cond)) { cerr << "Assertion " << (#cond) << " failed at line : " << __LINE__; exit(0); }

    tcT> void print_one(const T& x){
        cerr << x;
    }

    tcT> void print_iterator(T a, T b){
        bool first = false;
        cerr << "{";
        for(T it = a; it != b; ++it){
            if(first) cerr << ", ";
            cerr << (*it);
            first = true;
        }
        cerr << "}";
    }

    tcT> void print_one(const vector<T>& a){ print_iterator(all(a)); }
    tcT> void print_one(const set<T>& a){ print_iterator(all(a)); }
    tcT> void print_one(const multiset<T>& a){ print_iterator(all(a)); }

    void print_dbg(){ cerr << '\n'; }
    tcT> void print_dbg(const T& x){ print_one(x); cerr << '\n'; }
    tcT, class...U> void print_dbg(const T& A, const U&...B){
        print_one(A); cerr << ", ";
        print_dbg(B...);
    }
#else
    #define dbg(...) ((void)0)
    #define ASSERT(...) ((void)0)
#endif // LOCAL

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

struct LichaoTree{
    vector<Line> st;
    vi coord;
    int n;
    LichaoTree(vi _coord) : coord(_coord), n(sz(_coord)), st(n << 2, Line(0, inf)) {}

    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];

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

    int m = sz(coord);
    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));
    }
    ASSERT(false);
}

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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40