Submission #615386

#	Time	Username	Problem	Language	Result	Execution time	Memory
615386		nohaxjustsoflo	Rice Hub (IOI11_ricehub)	C++17	0 / 100	5 ms	596 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;
        while(r-l>1)
        {
            int m=(l+r)/2;
            ll r2=i+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));
            if(cost<=B) l=m;
            else r=m;
        }
        ans=max(ans,l-i+1);
    }
    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:58:5: warning: "/*" within comment [-Wcomment]
   58 |     /*
      |

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