Submission #614275

#	Time	Username	Problem	Language	Result	Execution time	Memory
614275		nohaxjustsoflo	Rice Hub (IOI11_ricehub)	C++17	100 / 100	195 ms	2576 KiB

ricehub

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+5;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const int inf=2e9;
const int K=600;
ll a[mxN], p[mxN];
//#include "ricehub.h"
int besthub(int n, int L, int A[], ll B)
{
    for(int i=0; i<n; i++) a[i]=A[i];
    ll s=0;
    for(int i=0; i<n; i++) p[i]=s+=a[i];
    ll ans=0;
    for(ll i=0; i<n; i++)
    {
        ll l=0, r=1e9+1;
        while(r-l>1)
        {
            int m=(l+r)/2;
            int r2=prev(upper_bound(a,a+n,a[i]+m))-a;
            int l2=lower_bound(a,a+n,a[i]-m)-a;
            ll cost=0;
            cost+=p[r2]-p[i]-(r2-i)*a[i];
            cost+=(i-l2)*a[i]-((i?p[i-1]:0)-(l2?p[l2-1]:0));
            if(cost<=B) l=m;
            else r=m;
        }
        int r2=prev(upper_bound(a,a+n,a[i]+l))-a;
        int l2=lower_bound(a,a+n,a[i]-l)-a;
        if(r2-l2+1==n) return n;
        ll cost=0;
        cost+=p[r2]-p[i]-(r2-i)*a[i];
        cost+=(i-l2)*a[i]-((i?p[i-1]:0)-(l2?p[l2-1]:0));
        ans=max(ans,r2-l2+1+(B-cost)/r);

    }
    return ans;
}
/*
int besthub2(int n, int L, int X[], ll B)
{
    int ans=0;
    for(int i=0; i<n; i++)
    {
        int p=X[i];
        vector<int> a(n);
        for(int i=0; i<n; i++) a[i]=abs(X[i]-p);
        sort(a.begin(),a.end());
        ll x=B;
        int j=0;
        while(j<n&&a[j]<=x) x-=a[j++];
        cout << "i " << i << " " << j << "\n";
        ans=max(ans,j);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, L, B; cin >> n >> L >> B;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    cout << besthub(n,L,a,B) << " " << besthub2(n,L,a,B);
    return 0;
    /*
    while(1)
    {
        int n=mt_rand()%5+1, L=0, B=mt_rand()%10;
        int a[n];
        for(int i=0; i<n; i++) a[i]=mt_rand()%15;
        sort(a,a+n);
        if(besthub(n,L,a,B)!=besthub2(n,L,a,B))
        {
            cout << n << " " << B << "\n";
            for(int i=0; i<n; i++) cout << a[i] << " ";
            cout << "\n";
            return 0;
        }
    }
}*/


/*
5 0 7
5 10 11 11 11
*/

Compilation message (stderr)

ricehub.cpp:82:5: warning: "/*" within comment [-Wcomment]
   82 |     /*
      |

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32