I’m getting WA on FRSCR, but I have compared it to a brute program without finding any bug.
I use a binary search for this question.
I can’t check it on Toolkit, so help me please.
Solution is below.
c++(g++ 4.3.2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dd ch=getchar()
inline int read()
{
int x=0;char dd;bool f=false;
while(!isdigit(ch))f|=ch==’-’,dd;
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
return f?-x:x;
}
#undef dd
void write(int x)
{
if(x<0)x=-x,putchar(’-’);
if(x>9)write(x/10);
putchar(x%10+48);
}
const int N=105,P=1e6+100;
int p,n,m;
int a[N],b[N];
int sum[P],tot=0;
int ans,res;
inline int calc(int mid)
{
ans=0,res=0;
for(int i=1;i<=n;i++)
{
int id=upper_bound(sum+1,sum+1+tot,mid/a[i])-sum-1;
if(id>tot)continue;
// while(sum[id]*a[i]<mid)id++;
// while(sum[id]*a[i]>mid)id–;
ans+=id;
}
mid=p-mid;
for(int i=1;i<=m;i++)
{
int id=upper_bound(sum+1,sum+1+tot,mid/b[i])-sum-1;
if(id>tot)continue;
// while(sum[id]*b[i]<mid)id++;
// while(sum[id]*b[i]>mid)id–;
res+=id;
}
return min(res,ans);
}
inline void sol()
{
int l=0,r=p+1;
while(r-l>1)
{
int mid=(l+r)>>1;
calc(mid);
if(ans<=res)l=mid;
else r=mid;
}
int final_ans=calc(l);
r=p;
while(r-l>1)
{
int mid=(l+r)>>1;
calc(mid);
if(ans>=res)r=mid;
else l=mid;
}
final_ans=max(final_ans,calc®);
write(final_ans);putchar(’\n’);
}
signed main()
{
freopen(“cr.in”,“r”,stdin);
freopen(“cr.out”,“w”,stdout);
int T=read();
for(int i=1;;i++)
{
sum[i]=sum[i-1]+i;
if(sum[i]>2e9){tot=i-1;break;}
}
while(T–)
{
p=read(),n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
sol();
}
return 0;
}
And here is my brute program.
#include<bits/stdc++.h>
#define re register
using namespace std;
#define dd ch=getchar()
inline int read()
{
int x=0;char dd;bool f=false;
while(!isdigit(ch))f|=ch==’-’,dd;
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
return f?-x:x;
}
#undef dd
void write(int x)
{
if(x<0)x=-x,putchar(’-’);
if(x>9)write(x/10);
putchar(x%10+48);
}
const int N=105;
int n,m,p;
int a[N],b[N];
inline int calc(int mid)
{
int ans=0,res=0;
for(int i=1;i<=n;i++)
for(re int pos=a[i],sum=a[i];pos<=mid;sum+=a[i],pos+=sum)
ans++;
mid=p-mid;
for(int i=1;i<=m;i++)
for(re int pos=b[i],sum=b[i];pos<=mid;sum+=b[i],pos+=sum)
res++;
return min(ans,res);
}
inline void sol()
{
int ans=0;
for(int i=1;i<=p;i++)
ans=max(ans,calc(i));
write(ans),putchar(’\n’);
}
int main()
{
freopen(“cr.in”,“r”,stdin);
freopen(“std.out”,“w”,stdout);
int T=read();
while(T–)
{
p=read(),n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
sol();
}
return 0;
}
(Forgive me for my bad English because I am talking to you with a translator.)
created
last reply
- 4
replies
- 640
views
- 2
users
- 2
links