oj.uz

답안 #898231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898231 2024-01-04T11:51:15 Z wibulord Building Bridges (CEOI17_building) C++14
100 / 100
 44 ms 9808 KB 
//#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 3128 KB Output is correct
2 Correct 33 ms 3676 KB Output is correct
3 Correct 33 ms 3676 KB Output is correct
4 Correct 31 ms 3676 KB Output is correct
5 Correct 28 ms 4960 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 36 ms 3128 KB Output is correct
7 Correct 33 ms 3676 KB Output is correct
8 Correct 33 ms 3676 KB Output is correct
9 Correct 31 ms 3676 KB Output is correct
10 Correct 28 ms 4960 KB Output is correct
11 Correct 31 ms 3932 KB Output is correct
12 Correct 41 ms 3868 KB Output is correct
13 Correct 25 ms 3676 KB Output is correct
14 Correct 36 ms 3932 KB Output is correct
15 Correct 44 ms 9808 KB Output is correct
16 Correct 27 ms 4944 KB Output is correct
17 Correct 16 ms 3676 KB Output is correct
18 Correct 17 ms 3828 KB Output is correct