Submission #898231

#	Time	Username	Problem	Language	Result	Execution time	Memory
898231		wibulord	Building Bridges (CEOI17_building)	C++14	100 / 100	44 ms	9808 KiB

building

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define pii pair<int, int>
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(s) (int)((s).size())
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> (i)) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}

const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 1e5 + 1, M = 6;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/

int n;
int w[N], h[N];
ll dp[N], pre[N];

ll SQR(ll x){
    return x*x;
}

bool flag = 0;
#define it multiset<line>::iterator
struct line{
    ll m, b;
    mutable double p;
    line(ll _m, ll _b, double _p){
        m = _m, b = _b, p = _p;
    }
    bool operator < (const line &x) const{
        if(!flag){
            if(m == x.m) return b < x.b;
            return m > x.m;
        }
        return p < x.p;
    }
};

struct linecontainer:multiset<line,less<>>{
    const double inf = 1/.0; 
    bool intersect(it x, it y){
        if(y == end()){
            x->p = inf;
            return false;
        }
        if(x->m == y->m) 
            return true;
        x->p = 1.0*(x->b - y->b) / (y->m - x->m);
        return x->p >= y->p;
    }

    void add(ll m, ll b){
        it z = insert({m,b,0});
        it y = z++;
        it x = y;
        while(intersect(y, z)) intersect(y, z = erase(z));
        while((x = y) != begin() && intersect(--x, y)) intersect(x, y = erase(y));
        while((y = x) != begin() && intersect(--x, y)) intersect(x, y = erase(y));
    }

    ll query(ll x){
        flag = 1;
        line tmp = *lower_bound({0,0,x});
        flag = 0;
        return tmp.m * x + tmp.b;
    }
}hull;

void sol(){ 
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n){
        cin >> w[i];
        pre[i] = pre[i-1] + w[i];
    }
    memset(dp, 0x3f, (n+1)*sizeof(ll));
    dp[1] = 0;
    hull.add(-2*h[1], SQR(h[1]) - w[1]);
    FOR(i, 2, n){ 
        dp[i] = hull.query(h[i]) + pre[i-1] + SQR(h[i]);
        hull.add(-2*h[i], SQR(h[i]) - pre[i] + dp[i]);
    } 
    // FOR(i, 1, n) cout << dp[i] << endl;
    cout << dp[n] << '\n';
}

signed main(){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message (stderr)

building.cpp: In member function 'long long int linecontainer::query(long long int)':
building.cpp:99:38: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
   99 |         line tmp = *lower_bound({0,0,x});
      |                                      ^
building.cpp: In function 'int main()':
building.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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