Submission #1146158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146158		wikidere	Building Bridges (CEOI17_building)	C++17	0 / 100	27 ms	1864 KiB

building

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
using namespace std;

struct Pillar {
    int index;
    long long cost;
};

int main() {
    int n;
    cin >> n;
    vector<int> h(n), w(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> w[i];

    vector<long long> dp(n, LLONG_MAX);
    dp[0] = w[0];

    deque<Pillar> dq;
    dq.push_back({0, dp[0]});

    for (int i = 1; i < n; i++) {
        while (!dq.empty() && dq.front().index < i) {
            dq.pop_front();
        }
        
        dp[i] = dq.front().cost + (h[i] - h[dq.front().index]) * (h[i] - h[dq.front().index]);
        dp[i] += w[i];
        
        while (!dq.empty() && dq.back().cost >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back({i, dp[i]});
    }
    
    cout << dp[n-1] << endl;
    return 0;
}

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