Submission #1110906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110906		luvna	Building Bridges (CEOI17_building)	C++14	30 / 100	79 ms	3424 KiB

building

#include<bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define endl "\n"
#define sz(v) (int)(v).size()
#define int long long

using namespace std;

typedef long long ll;

const int N = 1e5 + 15;
const ll INF = 1e18;

int n;
int h[N];
ll pref[N];
ll dp[N];

struct line{
    ll slope, c;
    line(ll slope, ll c) : slope(slope), c(c) {}
    ll f(ll x) {return slope*x + c;}
};

struct CHT{
    vector<line> lines;

    bool dump(line d1, line d2, line d3){
        return 1.0l*(d1.c - d2.c) / (1.0l*(d2.slope - d1.slope)) <= 1.0l*(d2.c - d3.c) / (1.0l*(d3.slope - d2.slope));
    }

    void add(line d){
        while(sz(lines) > 1 && dump(d, lines.back(), lines[sz(lines)-2])) lines.pop_back();
        lines.push_back(d);
    }

    ll query(ll x){
        int l = 0, r = sz(lines)-1;
        while(l < r){
            int mid = (l+r) >> 1;
            if(lines[mid].f(x) >= lines[mid+1].f(x)) l = mid+1;
            else r = mid;
        }
        return lines[l].f(x);
//        ll ans = 100000000;
//        for(int i = 0; i < sz(lines); i++) ans = min(ans, lines[i].f(x));
//        return ans;
    }

    void reload(){
        while(!lines.empty()) lines.pop_back();
    }
} solver;

vector<int> upd;

void dnc(int l, int r){
    if(l == r) return;

    int mid = (l+r) >> 1;

    dnc(l,mid);

    for(int i = l; i <= mid; i++) upd.push_back(i);

    sort(upd.begin(), upd.end(), [&](int x, int y){
        return h[x] < h[y];
    });

    for(int i : upd) solver.add(line(-2LL*h[i], 1LL*h[i]*h[i] + dp[i] - pref[i]));

    for(int i = mid+1; i <= r; i++){
        dp[i] = min(dp[i], 1LL*h[i]*h[i] + pref[i-1] + solver.query(h[i]));
    }

    solver.reload();
    while(!upd.empty()) upd.pop_back();

    dnc(mid+1,r);
}

void solve(){
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> pref[i], pref[i] += pref[i-1];


    memset(dp, 0x3f, sizeof(dp));

    dp[1] = 0;

    dnc(1,n);

   cout << dp[n];
}

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

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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