Submission #615394

#	Time	Username	Problem	Language	Result	Execution time	Memory
615394		nohaxjustsoflo	Rice Hub (IOI11_ricehub)	C++17	100 / 100	23 ms	3328 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=1;
    for(ll i=0; i<n; i++)
    {
        ll l=i, r=n;
        //cout << "i " << i << "\n";
        while(r-l>1)
        {
            int m=(l+r)/2;
            ll r2=m;
            ll l2=i;
            ll m2=(l2+r2)/2;
            ll cost=0;
            cost+=p[r2]-p[m2]-(r2-m2)*a[m2];
            cost+=(m2-l2)*a[m2]-((m2?p[m2-1]:0)-(l2?p[l2-1]:0));
            //cout << "tebra " << l2 << " " << m2 << " " << r2 << " " << cost << "\n";
            if(cost<=B) l=m;
            else r=m;
        }
        ans=max(ans,l-i+1);
    }
    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
5 0 1
0 2 7 10 12
*/

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