제출 #479258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479258		Mike4235	Building Bridges (CEOI17_building)	C++17	100 / 100	64 ms	9668 KiB

building

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int mode;
struct Line{
    mutable int a, b; mutable double k;
    bool operator<(const Line &p) const{
        return mode ? k < p.k : a < p.a;
    }
};
struct ConvexHull{
    multiset<Line> s;
    double div(int a, int b) {return 1.0 * a / b;}
    template<class T>bool isect(T x, T y) {
        if (y == s.end()) {x->k = INF; return 0;}
        if (x->a == y->a) {x->k = (x->b >= y->b ? INF : -INF);}
        else x->k = div(y->b - x->b, x->a - y->a);
        return x->k >= y->k;
    }
    void add(int a, int b) {
        auto z = s.insert({a, b, 0}), x = z++, y = x;
        while (isect(x, z)) z = s.erase(z);
        if (x != s.begin() && isect(--x, y)) isect(x, s.erase(y));
        while ((y = x) != s.begin() && isect(--x, y)) isect(x, s.erase(y));
    }
    int query(int x) {
        mode = 1;
        auto pos = s.lower_bound({0, 0, x});
        mode = 0;
        return -(pos->a) * x - pos->b;
    }
};
 
ConvexHull hull;
int n, h[100005], w[100005], dp[100005];

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n;
    for1(i,1,n) cin >> h[i];
    for1(i,1,n) cin >> w[i];

    int cur = w[1];
    hull.add(2 * h[1], -(h[1] * h[1] - cur));
    for1(i,2,n) {
        dp[i] = hull.query(h[i]) + h[i] * h[i] + cur;
        cur += w[i];
        hull.add(2 * h[i], -(h[i] * h[i] - cur + dp[i]));
    }

    cout << dp[n];
    
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In member function 'long long int ConvexHull::query(long long int)':
building.cpp:56:41: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
   56 |         auto pos = s.lower_bound({0, 0, x});
      |                                         ^

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