Submission #1086959

#TimeUsernameProblemLanguageResultExecution timeMemory
1086959MrPavlitoRice Hub (IOI11_ricehub)C++17
68 / 100
77 ms848 KiB
#include "ricehub.h" #include <bits/stdc++.h> //#define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second #define endl "\n" #define pii pair<int,int> using namespace std; const int MAXN = 1e5+5; const int mod7 = 1e9+7; const long long inf = 1e18; int n; int besthub(int R, int L, int X[], long long B) { n = R; if(n <= 5000) { int mx = 0; for(int i=0; i<n; i++) { int l = i; int r = i; long long trsum = 0; while(trsum <= B) { if(l == 0 && r!=n-1 && trsum + (X[r+1] - X[i]) <= B) { trsum += (X[++r] - X[i]); } else if(r == n-1 && l!=0 && trsum + (X[i] - X[l-1]) <= B) { trsum += (X[i] - X[--l]); } else if(l!=0 && r!=n-1 && (X[i] - X[l-1]) >= (X[r+1] - X[i]) && trsum+(X[r+1] - X[i])<=B) { trsum+=(X[++r] - X[i]); } else if(l!=0 && r!=n-1 && (X[i] - X[l-1]) <= (X[r+1] - X[i])&& trsum+(X[i] - X[l-1])<=B) { trsum+=(X[i] - X[--l]); } else break; } mx = max(mx, r-l+1); } return mx; } else { int l = 0;int r =1; int i =0; long long trsum = 0; int cntr = 0; int cntl =0; int mx = 0; while(r<n) { while(r<n) { if(trsum+ X[r] - X[i] <= B) { trsum+= X[r++] - X[i]; cntr++; } else if(trsum > B && l<i && X[r] - X[i] < X[i] - X[l] && trsum+ (X[r] - X[i]) - (X[i] - X[l]) <= B) { trsum -= (X[i] - X[l]); trsum += (X[r] - X[i]); l++; r++; } else if(trsum > B && l<i) { cntl--; trsum -= (X[i] - X[l++]); } else break; } mx = max(mx, r-l); i++; trsum += (i-l) *1ll * (X[i] - X[i-1]); trsum -= (r-i) *1ll * (X[i] - X[i-1]); } return mx; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...