思路

题目要求的是 \(\max_{a = 1}^{n}\{\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\}\)，所以我们将 \(\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\) 化简一下，得：

在 \(a\) 每增加 \(1\) 时，这个和 \(s\) 将会变为 \(s + \sum_{i = 1}^{x}a_i + a_x\)。

• 如果在 \(x_i \geq 0\) 时，显然对于答案是有贡献的，全部加上即可。

• 如果在 \(x_i < 0\) 时，显然当 \(s\) 没有被减下 \(0\) 时，对于答案都是有贡献的，加上即可。但是在后面需要将剩下的都要加上。

code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10,inf = 1e18 + 10;
int T,n,m;

inline int read(){
	int r = 0,w = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-') w = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		r = (r << 1) + (r << 3) + (c ^ 48);
		c = getchar();
	}
	return r * w;
}

signed main(){
	T = read();
	while (T--){
		int Max = -inf,sum = 0,res = 0;
		n = read();
		m = read();
		for (re int i = 1;i <= n;i++){
			int x,y;
			x = read();
			y = read();
			if (x >= 0){
				res += sum * y + x * (y + 1) * y / 2;
				Max = max(Max,res);
			}
			else{
				int l = max(1ll,min(sum / (-x),y));//注意这里需要与 1 取 max，避免 sum / (-x) 为负数 
				int del = sum * l + x * (l + 1) * l / 2;
				Max = max(Max,res + del);
				res += sum * y + x * (y + 1) * y / 2;
				Max = max(Max,res);
			}
			sum += x * y;
		}
		printf("%lld\n",Max);
	}
	return 0;
}