Submission #915189

#	Time	Username	Problem	Language	Result	Execution time	Memory
915189		Whisper	Building Bridges (CEOI17_building)	C++14	100 / 100	51 ms	70492 KiB

building

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = a; i >= b; i --)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e6 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //   freopen(name".inp", "r", stdin);
    //   freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

bool minimize(int&a , int b){
    if (a > b){
        a = b; return 1;
    }
    return 0;
}

bool maximize(int&a, int b){
    if (a < b){
        a = b; return 1;
    }
    return 0;
}

int n;
int h[MAX], w[MAX];
int s[MAX];
int dp[MAX];
struct Line{
    int a, b;
    Line():a(0), b(LINF){};
    Line(int _a, int _b){
        a = _a;
        b = _b;
    }

    int f(int x){
        return a * x + b;
    }
};
struct LichaoTree{
    // query for min
    int n;
    vector<Line> f;
    LichaoTree(int _n){
        this -> n = _n;
        f.resize(4 * n + 5);
    }

    void addLine(int id, int l, int r, Line line){
        // nếu là max chỉ cần đổi dấu
        if (l == r){
            if (line.f(l) < f[id].f(l)) f[id] = line;
            return;
        }
        int mid = (l + r) >> 1;
        if (line.a > f[id].a) swap(line, f[id]);
        if (line.f(mid) < f[id].f(mid)){
            swap(line, f[id]);
            addLine(id << 1, l, mid, line);
        }
        else{
            addLine(id << 1 | 1, mid + 1, r, line);
        }
    }

    int qry(int id, int l, int r, int x){
        int ans = f[id].f(x);
        if (l == r) return ans;
        int mid = (l + r) >> 1;
        if (x <= mid)
            return min(ans, qry(id << 1, l, mid, x));
        return min(ans, qry(id << 1 | 1, mid + 1, r, x));
    }

    void addLine(int a, int b){
        addLine(1, 1, n, Line(a, b));
    }
    int qry(int x){
        return qry(1, 1, n, x);
    }
};
namespace SUB1{
    void solve(){
        auto cal = [&](int i, int j){
            return (h[i] - h[j]) * (h[i] - h[j]) - w[j];
        };


        memset(dp, 0x3f, sizeof dp);
        dp[1] = 0;
        for (int i = 2; i <= n; ++i){
            for (int j = 1; j < i; ++j){
                dp[i] = min(dp[i], dp[j] + cal(j, i));
            }
            cout << dp[i] << " ";
        }
        cout << dp[n] + accumulate(w + 2, w + n + 1, 0ll) << " ";
    }
}

void Whisper(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];
    LichaoTree lichao(MAX);
    lichao.addLine(-2 * h[1], h[1] * h[1]);
//    SUB1 :: solve();
//    cout << '\n';
    for (int i = 2; i <= n; i++){
        dp[i] = lichao.qry(h[i]) + h[i] * h[i] - w[i];
        lichao.addLine(-2 * h[i], h[i] * h[i] + dp[i]);
//        cout << dp[i] << " ";
    }
    cout << dp[n] + accumulate(w + 2, w + n + 1, 0ll);
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

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