oj.uz

Submission #614246

# Submission time Handle Problem Language Result Execution time Memory
614246 2022-07-30T23:21:05 Z nohaxjustsoflo Rice Hub (IOI11_ricehub) C++17
0 / 100
 1000 ms 468 KB 
#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];
//#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 ans=1,l=0,r=1;
    for(ll i=0; i<n; i++)
    {
        if(i)
        {
            B+=(r-i)*(a[i]-a[i-1]);
            B-=(i-l)*(a[i]-a[i-1]);
        }
        do{
            while(r<n&&a[r]-a[i]<=B) B-=a[r++]-a[i];
            if(B>=0) ans=max(ans,r-l);
            while(l<i&&r<n&&a[i]-a[l]>a[r]-a[i])
            {
                B+=a[i]-a[l++];
                B-=a[r++]-a[i];
                while(r<n&&a[r]-a[i]<=B) B-=a[r++]-a[i];
                if(B>=0) ans=max(ans,r-l);
            }
        }while(B<0);
    }
    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 9
0 3 6 7 8
*/

Compilation message

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1096 ms 212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 1086 ms 212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -