Submission #1363100

#TimeUsernameProblemLanguageResultExecution timeMemory
1363100hyyhBuilding Bridges (CEOI17_building)C++20
0 / 100
77 ms4556 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <unordered_map>

#define int long long

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)

int const INF = 1e18+10;

struct Line{
    int m,c;

    Line(int a,int b) : m(a),c(b) {}

    int getval(int x){
        return m*x+c;
    }
};

struct Node{
    Line ln;
    Node* l;
    Node* r;

    Node(Line a) : ln(a),l(nullptr),r(nullptr) {}
    Node() : ln(Line(0,INF)),l(nullptr),r(nullptr) {}
};

typedef Node* pnode;
pnode root = new Node();

void update(pnode &node,int l,int r,Line ln){
    if(!node) node = new Node();
    int md = l+(r-l)/2;
    if(node->ln.getval(md) >= ln.getval(md)) swap(node->ln,ln);
    if(node->ln.getval(l) > ln.getval(l)) update(node->l,l,md,ln);
    if(node->ln.getval(r) > ln.getval(r)) update(node->r,md+1,r,ln);
}

int query(pnode &node,int l,int r,int idx){
    if(l > idx || r < idx) return INF;
    if(!node) node = new Node();
    if(l == r && l == idx) return node->ln.getval(idx);
    int md = l+(r-l)/2;
    int q1 = query(node->l,l,md,idx);
    int q2 = query(node->r,md+1,r,idx);
    return min({node->ln.getval(idx),q1,q2});
}

signed main(){
    int n;cin >> n;
    int maxans = 1e18;
    vector<int> h(n);
    vector<int> cost(n);
    vector<int> pref(n+1);
    pref[0] = 0;
    for(int i{};i < n;i++) cin >> h[i];
    for(int i{};i < n;i++){
        cin >> cost[i];
        pref[i+1] = pref[i]+cost[i];
    }
    int dpval = 0;
    update(root,1,maxans,Line(-2*h[0],h[0]*h[0]+pref[1]));
    for(int i{1};i < n;i++){
        dpval = query(root,1,maxans,h[i])+h[i]*h[i]+pref[i];
        update(root,1,maxans,Line(-2*h[i],h[i]*h[i]-pref[i+1]+dpval));
    }
    cout << dpval;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...