2015弱校联盟(1) - E. Rectangle

时间:2022-12-22 10:17:08

E. Rectangle
Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Submit Status
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 6
1 1 0
50000 50000 1000000000

Sample Output

8
0
156256250062500000

有技巧的暴力,枚举一条边,计算另外一条边的情况

#include <bits/stdc++.h>
#define LL long long
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;


int main()
{
LL n,m,k;
while(cin>>n>>m>>k)
{
LL ans=0;
k/=2;
for(int i=1;i<=n&&k-i>0;i++)
{
LL a=(n-i+1);
LL b=min(k-i,m);
LL c=(m+(m-b+1))*b/2;
ans+=(a*c);
}
cout<<ans<<endl;
}
return 0;
}