Submission #614245

#TimeUsernameProblemLanguageResultExecution timeMemory
614245nohaxjustsofloRice Hub (IOI11_ricehub)C++17
49 / 100
15 ms1492 KiB
#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]); } while(l<i&&B<0) B+=a[i]-a[l++]; while(r<n&&a[r]-a[i]<=B) B-=a[r++]-a[i]; 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]; ans=max(ans,r-l); } } 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 (stderr)

ricehub.cpp:75:5: warning: "/*" within comment [-Wcomment]
   75 |     /*
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...