CF#420 Div.2 B. Okabe and Banana Trees（数学）

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tree in such a point, and it has x + ybananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation . Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe's rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 1018. You can trust him.

Input

The first line of input contains two space-separated integers m and b (1 ≤ m ≤ 1000, 1 ≤ b ≤ 10000).

Output

Print the maximum number of bananas Okabe can get from the trees he cuts.

Examples

input

1 5

output

input

2 3

output

Note

</center>

The graph above corresponds to sample test 1. The optimal rectangle is shown in red and has 30 bananas.

这个题我看了一下，感觉我还是能做出来的。
不过当时比赛的时候因为A题的影响然后。。。。
再次强调自信的重要性。。
这道题唯一卡住我的地方就是那个香蕉数量。小学生都能找出来的规律。。看到答案的时候。。愁死我了。
是这样，给一条直线，直线下方与xy轴的可行域所围的整数点，做这个点关于x，y轴的垂线，围成的红***域，每个点包括边界横纵坐标的总和为某个点的香蕉个数。。。好吧，我承认那个总和我推了好久。。。
只要横纵坐标单独算就行了。例如（2,3）这个点，把围的所有点横纵坐标都写出来：
横坐标：4个0,4个1,4个2；
纵坐标：3个0,3个1,3个2；3个3；
所以通过找规律可知：公式为((x+1)*x/2)*(y+1)+(y(y+1)*y/2)(x+1)
还要注意几点：
1.不要用暴力列举每一个点，更不要用循环算总和，我第一次这样写严重超时，面对闪烁的光标却不出结果我竟无言以对……
2.尽量用一个量表示另一个量，这样能缩小复杂度，而且哪个量最大值最小用哪个表示，这里用y表示x，因为x最大是mb，y最大是b，所以把y作为循环变量很合适。。
3.本题数字非常大，要用long long int，否则答案会出错，因为太大的数int表示不了，而且CF不允许用%lld读64位数据，所以用%I64d，
至此通过！

附上代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int m,b,x,y,i,j;
    long long int sum=0,s=0;
    scanf("%I64d%I64d",&m,&b);
    for(y=0;y<=b;y++)
    {
        x=m*b-m*y;
        s+=((x+1)*x/2)*(y+1)+((y*(y+1))/2)*(x+1);
        if(s>sum)
            sum=s;
        s=0;
    }
    printf("%lld\n",sum);
}