Rectangle

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: 

%lld      Java class name: Main

 

frog has a piece of paper divided into 

n rows and m columns. Today, she would like to draw a rectangle whose perimeter is not greater than k.

 

 

There are 

8 (out of 9) ways when n=m=2,k=6

 

Find the number of ways of drawing.

 

Input

The input consists of multiple tests. For each test:

 

The first line contains 

3 integer n,m,k (1≤n,m≤5⋅104,0≤k≤109).

 

Output

For each test, write 

1 integer which denotes the number of ways of drawing.

 

Sample Input

2 2 61 1 050000 50000 1000000000

Sample Output

801562562500625000000

有技巧的暴力搜索方法：

　　　　设总方格长和宽分别为n,m，一个长为i，宽为j(j 可以大于i,这里只是为了与总方格相对应)的矩形，可以找到有(n-i+1)*(m-j+1)个这样的矩形。

　　　　并且， i <= min(n,k-1), 取过i后，j <= min(m,k-i);有i = (1 ~ min(n,k-1)),j = (1~min(m,k-i));所以可以通过枚举i,并且由于j的值符合等差级数，可以通过“首项加末项乘以项数除以二”快速求得j。

　　　　所有，sum[i] = (n-i+1),sum[j] = ( (m-1+1)+(m-j+1) ) * j / 2 ; ans += sum[i]*sum[j],即得。

 

#include
       
        #include
        
         #include
         
          #include
          
           #define ll long long//BNUOJ似乎不识别__int64;using namespace std;int main(){    ll n,m,k;    while(~scanf("%I64d%I64d%I64d",&n,&m,&k)){        k /= 2;        ll ans = 0;        ll nn = min(n,k-1);        for(ll i = 1; i <= nn; i++){            ll j = min(m,k - i);            ans += (n - i + 1)*(m + m - j + 1)*j/2;        }        cout<
           
            <