@[Neven](/user/670998) 使用 `long long` 即可。
by DaShaber @ 2023-07-20 15:22:37
@[caibyte](/user/392304) 感谢大佬orz,调了一个晚上,交了70多次,头都快秃了~
by Neven @ 2023-07-20 16:23:27
6
by I_am_a_rookie_O @ 2023-07-25 21:07:55
楼主改后正解
#include<bits/stdc++.h>
using namespace std;
long long x,d,k,minn,maxx,mo=1;
long long f[9999999],lft,rgt,mid,ans;
struct node
{
int n, m;
}
``` a[9999999];
bool tfz(int g){
minn=max(mo,d-g);
maxx=d+g;
memset(f, -127, sizeof(f));
f[0]=0;
for(int i=1;i<=x;i++){
for(int j=i-1;j>=0;j--){
if(a[i].n-a[j].n<minn)
continue;
if(a[i].n-a[j].n>maxx)
break;
f[i]=max(f[i],f[j]+a[i].m);
if(f[i]>=k) return 1;
}
}
return 0;
}
``` int main(){
cin>>x>>d>>k;
for(int i=1;i<=x;i++){
cin>>a[i].n>>a[i].m;
}
rgt=min(a[x].n,2000);
while(lft<=rgt){
mid=(lft+rgt)/2;
if(tfz(mid)){
ans=mid;
rgt=mid-1;
}else{
lft=mid+1;
}
}
if(ans==0)
{
cout<<-1;
return 0;
}
else
cout<<ans<<endl;
return 0;
}
by I_am_a_rookie_O @ 2023-07-25 21:35:37