C++14(g++5.4) 解法, 执行用时: 435ms, 内存消耗: 480K, 提交时间: 2019-08-26 15:53:53

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int c[20],p[20],l[20];
int n;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-y*(a/b);
	return d;
}
int check(int m){
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			ll a=p[i]-p[j],x=0,b=m,y=0,c1=c[j]-c[i];
			ll d=exgcd(a,b,x,y);
			if(c1%d)
				continue;
			x=x*c1/d;
			ll p1=b/d;
			x%=p1;
			if(x<0)
				x+=abs(p1);
			if(x<=min(l[i],l[j]))
				return 0;
		}
	}
	return 1;
}
int main(){
	scanf("%d",&n);
	int mx=-1;
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&c[i],&p[i],&l[i]),mx=max(mx,c[i]);
	for(int i=mx;i<=1e6+5;i++){
		if(check(i)){
			printf("%d\n",i);
			break;
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 311ms, 内存消耗: 380K, 提交时间: 2020-10-11 21:31:34

#include<bits/stdc++.h>
using namespace std;
const int nm=1000000;
int n,m,x,y,c,d,lb;
void euc(int a,int b,int&x,int&y){
	if(!b)x=1,y=0,d=a;
	else euc(b,a%b,y,x),y-=a/b*x;
}struct savage{int c,p,l;}s[nm];
bool cmp(savage a,savage b){return a.p>b.p;}
bool check(int m){
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++){
			euc(s[i].p-s[j].p,m,x,y);
			if((c=s[j].c-s[i].c)%d)continue;
			x*=(c/d),d=m/d,x=(x%d+d)%d;
			if(x<=s[i].l&&x<=s[j].l)return false;
		}return true;
}int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",
		&s[i].c,&s[i].p,&s[i].l);
		lb=max(lb,s[i].c);
	}sort(s,s+n,cmp);
	for(int i=lb;i<=nm;i++)
	if(check(i))return printf("%d\n",i),0;
}