1 solutions
-
0
Bullet LV 4 @ 2024-03-29 11:28:18
Author Code (Kamonasish Roy) :
#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+10,MOD=2000000007;
typedef long long ll;
int preix_sum[101][100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
int n,k,x;
cin>>n>>k>>x;
vector<int>arr(n+1);
for(int i=1;i<=n;i++)cin>>arr[i];
for(int i=1;i<=n;i++){
for(int j=x+1;j<=100;j++){
if(arr[i]%j==0){
preix_sum[j][i]=preix_sum[j][i-1]; // cost saving
}
else{
int lagba=j-(arr[i]%j);
preix_sum[j][i]=preix_sum[j][i-1]+lagba;// cost saving
}
}
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=x+1;j<=100;j++){
int l=i,r=n;
while(l<=r){
int mid=l+(r-l)/2;
int cur_sum=preix_sum[j][mid]-preix_sum[j][i-1];// longest subarray which cost less than equal K.
if(cur_sum<=k){
res=max(res,mid-i+1);
l=mid+1;
}
else r=mid-1;
}
}
}
cout<<res<<"\n";
}
return 0;
}Tester Code(Emon Thakur) :
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,k,x; cin>>n>>k>>x;
int a[n],b[n];
for(int i=0;i<n;i++) cin>>a[i];int ans=0,left,right; for(int gcd=x+1;gcd<=200;gcd++) { for(int i=0;i<n;i++) { b[i] = (gcd-(a[i]%gcd))%gcd; } //b[0]=5; left=0,right=0; int rem = k; while(right<n) { if(rem<b[right]) { if(left==right) {left++; right++; continue;} rem += b[left]; ++left; continue; } rem -= b[right]; ans = max(ans,right-left+1); ++right; } if(ans==n) break; } cout<<ans<<endl;
}
int main()
{
solve();
}
- 1
Information
- ID
- 1043
- Difficulty
- 7
- Category
- (None)
- Tags
- (None)
- # Submissions
- 20
- Accepted
- 7
- Accepted Ratio
- 35%
- Uploaded By