Submission #1370196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370196		ojuz	Building Bridges (CEOI17_building)	C++20	0 / 100	24 ms	4060 KiB

building

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct line{
    ll a=(ll)1e12,b=(ll)1e18;
    ll val(ll x){
        return a*x+b;
    }
};


const int mxn=1e5+5;
const int mxs=1e6+5;
int n;
ll pre[mxn];
ll h[mxn];
ll w[mxn];
ll dp[mxn];
line segtree[mxs*4];

ll query(int x,int l=0,int r=mxs,int v=1){
    if(l==r) return segtree[v].val(x);
    int mid=(l+r)/2;
    if(x<=mid){
        return min(segtree[v].val(x),query(x,l,mid,v*2));
    }
    return min(segtree[v].val(x),query(x,mid+1,r,v*2+1));
}

void update(line L,int l=0,int r=mxs,int v=1){
    if(l==r){
        if(L.val(l)<segtree[v].val(l)){
            segtree[v]=L;
        }
        return;
    }
    int mid=(l+r)/2;
    if(segtree[v].a>L.a){
        swap(segtree[v],L);
    }
    if(L.val(mid)<segtree[v].val(mid)){
        swap(segtree[v],L);
        update(L,mid+1,r,v*2+1);
    }
    else{
        update(L,l,mid,v*2);
    }
}

int main() {_
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        
        pre[i]=pre[i-1]+w[i];
    }
    line L;
	L.a=-2*h[1],L.b=-pre[1];
    update(L);
    for(int i=2;i<=n;i++){
        dp[i]=h[i]*h[i]+pre[i]-w[i]-query(h[i])-w[i];
        line L;
		L.a=-2*h[i];
		L.b=dp[i]+h[i]*h[i];
        update(L);
    }
    cout<<dp[n]+pre[n];
    return 0;
}


/*
//dpi=dpj+(hi-hj)*(hi-hj)-wi

//dpi=dpj+hi*hi+hj*hj-2*hi*hj-wi

//y=ax+b

*/

//maybe timeflew wanna gold

Compilation message (stderr)

building.cpp: In function 'void setIO(std::string)':
building.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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