rt

一直 TLE # 2 WA # 4

#include <iostream>
#include <ctime>
#include <random>
using namespace std;
const long long ma = 20000 + 10,inf = 9223372036854775807;
const double det = 0.99;
double top;
long long T,dn;
long long n,m,nowl,nowr,newl,newr,noww,neww,ans = inf;
long long s[ma],a[ma],b[ma],w[ma],ss[ma];
double get()
{
	long long sum = w[n+1] - ss[nowr] * (b[nowr] - b[n+1]) - ss[nowl] * (b[nowl] - b[nowr]);
	if(sum < ans)
		ans = sum;
	return sum;
}
void sa()
{
	mt19937 ra(random_device{}());
	double t = n;
	dn = 0;
	while(t > 5e-1)
	{
		long long mi = t;
		//cout << mi << endl;
		uniform_real_distribution<>a(-mi,mi);
		noww = get();
		if(dn&1)
		{
			newl = nowl + a(ra);
			if(newl < 1 || n <= newl)
				continue;
			swap(nowl,newl);
		}
		else
		{
			newr = nowr + a(ra);
			if(newr < 1 || n <= newr)
				continue;
			swap(nowr,newr);
		}
		neww = get();
		double dt = neww - noww;
		if(neww < noww)
			noww = neww;
		else if(exp(-dt/t) * mt19937::max() < ra())
		{
			if(dn&1)
				swap(nowl,newl);
			else
				swap(nowr,newr);
		}
		t *= det;
		dn++;
	}
}
signed main()
{
	cin >> n;
	top = n;
	for(int i = 1; i <= n; i++)
		cin >> s[i] >> a[i],ss[i] = ss[i-1] + s[i];
	for(int i = n; i >= 1; i--)
		b[i] = b[i+1] + a[i];
	long long tot = 0;
	for(int i = 1; i <= n+1; i++)
	{
		w[i] = w[i-1] + tot * a[i-1];
		tot += s[i];
	}
	nowl = n/3;
	nowr = n/3*2;
	double st = clock();
	sa();
	double et = clock();
	double per = et-st;
	while((et-st + per) / CLOCKS_PER_SEC < 0.8)
	{
		sa();
		et = clock();
	}
	cout << ans;
}