Submission #1110903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110903		luvna	Building Bridges (CEOI17_building)	C++14	0 / 100	20 ms	5968 KiB

building

#include<bits/stdc++.h>

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

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.slope - d2.slope) / (1.0l*(d2.c - d1.c)) >= 1.0l*(d2.slope - d3.slope) / (1.0l*(d3.c - d2.c));
    }

    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<line> 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(line(-2LL*h[i], 1LL*h[i]*h[i] + dp[i] - pref[i]));

    sort(upd.begin(), upd.end(), [&](line x, line y){
        return x.slope >= y.slope;
    });

    for(int i = 0; i < sz(upd); i++) solver.add(upd[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];

    //for(int i = 1; i <= n; i++) cout << dp[i] << endl;
}

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:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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