AT_abc240_f [ABC240F] Sum Sum Max

思路

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

$$i \times A_1 + (i - 1) \times A_2 + \dots + 1 \times A_x$$

在 $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;  
}