蒟蒻C++ TLE求调(给关注)
查看原帖
蒟蒻C++ TLE求调(给关注)
938212
OMG_NOIP楼主2023/10/11 10:05

最多也才25的平方,怎么会T呢?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,ans=-1;
struct Point{
	ll x,y;
}p[505];
ll dis(ll a,ll b){return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y);}
bool cmp1(Point a,Point b){return a.x<b.x;}
bool cmp2(Point a,Point b){return a.y<b.y;}
void dfs(ll now,ll have,ll len){
//	cout<<"x = "<<p[now].x<<"     y = "<<p[now].y<<"     have = "<<have<<"     len = "<<len<<endl;
	ans=max(ans,len+have);
	for(ll i=1+now;i<=n;i++){
		if(i==now)continue;
		if(p[i].x>=p[now].x&&dis(now,i)-1<=have){
			dfs(i,have-dis(now,i)+1,len+dis(now,i));
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
	sort(p+1,p+1+n,cmp1);
	stable_sort(p+1,p+1+n,cmp2);
//	cout<<endl;
//	for(ll i=1;i<=n;i++)cout<<p[i].x<<"  "<<p[i].y<<endl;
//	cout<<endl;
	for(ll i=1;i<=n;i++){
		dfs(i,m,1);
//		cout<<endl;	
	}
	cout<<ans;
	return 0;
}
2023/10/11 10:05
加载中...