Submission #781529

#	Time	Username	Problem	Language	Result	Execution time	Memory
781529		guagua0407	Building Bridges (CEOI17_building)	C++17	100 / 100	52 ms	8268 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={-2*h[1],dp[1]+h[1]*h[1]-pre[1]};
    update(L);
    for(int i=2;i<=n;i++){
        dp[i]=h[i]*h[i]+pre[i]-w[i]+query(h[i]);
        line L={-2*h[i],dp[i]+h[i]*h[i]-pre[i]};
        update(L);
    }
    cout<<dp[n];
    return 0;
}
//maybe its multiset not set
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40