rt

这是我的 $O(n^2)$，代码：

#include <bits/stdc++.h>
#include <chrono>
#define int long long
using namespace std;
const int N=5e4+16;

struct node{
	int u,v;
}a[N];

int n,ans;

bool cmp(node a,node b){
	return a.v<b.v;
}

signed main(){
	auto start=chrono::high_resolution_clock::now();
	freopen("jiaqiang.out","r",stdin);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].v,&a[i].u);
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=1;j<i;j++){
			sum+=abs(a[i].u-a[j].u);
		}
		ans+=sum*a[i].v;
	}
	printf("%lld\n",ans);
	auto end=chrono::high_resolution_clock::now();
	auto duration=chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
	cout<<"Elapsed time:"<<duration<<"ms\n";
	
	return 0;
}

这是造极限数据的代码：

#include <bits/stdc++.h>
using namespace std;

int N=50000,M=50000;

signed main(){
	freopen("jiaqiang.out","w",stdout);
	cout<<N<<endl;
	for(int i=1;i<=N;i++){
		cout<<M-rand()%50000<<" "<<M-rand()%50000<<endl;
	}
	
	
	return 0;
}

这是运行界面：

测了几次，时间都在 800ms 至 900ms，使用 C++ 20 O2。