---
# System prepended metadata

title: OSP 2023 - Code

---


Problems: [TLX](https://tlx.toki.id/problems/osnp-2023)

# B1
```cpp
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define ll long long
#define fs first
#define sc second
#define pll pair<ll,ll>
using namespace std;

int main() {
    ll n,m,x;cin>>n>>m;
    vec<ll> B(m);
    pll a = {0,n};
    pll b = {0,m};
    for (ll i=0;i<n;i++) cin>>x,a.fs+=x;
    for (ll i=0;i<m;i++) cin>>B[i],b.fs+=B[i];
    sort(B.rbegin(), B.rend());

    auto avg = [&](pll x) {
        return x.fs/((double)x.sc);
    };
    ll ans=0;
    ll i=0;
    while (i+1<m && avg(a)<=avg(b)) {
        do {
            a.fs+=B[i];a.sc++;
            b.fs-=B[i];b.sc--;
            ans+=B[i];
            i++;
        } while (i<m && B[i]==B[i-1]);
    }
    if (avg(a)<=avg(b)) ans=-1;
    cout<<ans<<endl;
}
```

---

# B2
```cpp
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define ll long long
#define fs first
#define sc second
#define pll pair<ll,ll>
using namespace std;

int main() {
    ll n,m,k;cin>>n>>m>>k;
    vec<ll> a(n);
    for (int i=0;i<n;i++) {
        cin>>a[i];
    }
    sort(a.begin(), a.end());
    ll cnt=0;
    for (int i=0;i<n;i++) {
        m+=k;
        auto ptr = upper_bound(a.begin(), a.end(), m);
        if (ptr==a.end()) break;
        m=*ptr;
        cnt++;
    }
    cout<<cnt<<endl;
}
```

---

# B3
```cpp
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define ll long long
#define fs first
#define sc second
#define pll pair<ll,ll>
using namespace std;

const int MXN = (int)1e5+5;
int par[MXN];
int sz[MXN];
ll df[MXN];

void initdsu() {
    for(int i=0;i<MXN;i++) {
        par[i]=i;
        sz[i]=1;
        df[i]=1e9;
    }
}

int gpar(int x) {
    if (par[x]!=x) par[x] = gpar(par[x]);
    return par[x];
}

bool chk(int u, int v) {
    return gpar(u)==gpar(v);
}

void join(int u, int v) {
    if (chk(u,v)) return;
    // cout<<"bf join "<<u<<' '<<v<<endl;
    int pu=gpar(u),pv=gpar(v);
    if (sz[pv]>sz[pu])swap(pu,pv);
    par[pv]=pu;
    sz[pu]+=sz[pv];
    df[pu]=min(df[pu], df[pv]);
}


int main() {
    initdsu();
    ll n,m,k;cin>>n>>m>>k;
    for (int i=0;i<n;i++) {
        cin>>df[i];
    }

    vec<ll> trfs(m);
    for (int i=0;i<m;i++) {
        cin>>trfs[i];
    }
    sort(trfs.begin(), trfs.end());
    
    for (int i=0;i<k;i++) {
        int u,v;
        cin>>u>>v;
        join(u-1,v-1);
    }
    
    vec<ll> islands;
    for (int i=0;i<n;i++) {
        if (gpar(i)==i) {
            islands.pb(df[i]);
            // cout<<"i="<<i<<"cst="<<df[i]<<endl;
        }
    }

    if (islands.size()>trfs.size()) {cout<<-1<<endl; return 0;}
    sort(islands.begin(), islands.end());
    int icnt = islands.size();
    ll res=0;
    for (int i=0;i<icnt;i++) {
        // cout<<"df="<<islands[i]<<" trf="<<trfs[icnt-i-1]<<endl;
        res+=islands[i]*trfs[icnt-i-1];
    }
    cout<<res<<endl;
}
```

---

# B4
```cpp
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define ll long long
#define fs first
#define sc second
#define pll pair<ll,ll>
using namespace std;


int main() {
    ll n,k,x;cin>>n>>k>>x;
    vec<pll> c(n+1);
    for (int i=1;i<=n;i++) cin>>c[i].fs;
    for (int i=1;i<=n;i++) cin>>c[i].sc;
    sort(c.begin(), c.end());
    ll pref[n+1];
    pref[0]=0;
    for (int i=1;i<=n;i++) {
        pref[i]=pref[i-1]+c[i].sc;
    }
    ll ans=0;
    for (int i=1;i<=n;i++) {
        if (abs(x-c[i].fs)>k) continue;
        int lpos=c[i].fs;
        ll trgt;
        if (c[i].fs>=x) trgt = x+k;
        else trgt=x+k-2*abs(lpos-x);
        int ridx = upper_bound(c.begin(), c.end(),make_pair(trgt, (ll)2e9))-c.begin()-1;
        if (ridx<0) continue;
        ans=max(ans, pref[ridx]-pref[i-1]);
    }

    for (int i=n;i>0;i--) {
        if (abs(x-c[i].fs)>k) continue;
        int rpos=c[i].fs;
        ll trgt;
        if (c[i].fs<=x) trgt = x-k;
        else trgt=x-(k-2*abs(rpos-x));
        int lidx = lower_bound(c.begin(), c.end(),make_pair(trgt, (ll)-1))-c.begin();
        ans=max(ans, pref[i]-pref[lidx-1]);
    }
    cout<<ans<<endl;
}
```

---

# B5
Check [My Submission](https://tlx.toki.id/submissions/1478026)

---
