# 【codeforces 572C】Lengthening Sticks

2016-12-24 08:23:56来源:CSDN作者:harlow_cheng人点击

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given three sticks with positive integer lengths of a, b, and c centimeters. You can increase length of some of them by some positive integer number of centimeters (different sticks can be increased by a different length), but in total by at most l centimeters. In particular, it is allowed not to increase the length of any stick.

Determine the number of ways to increase the lengths of some sticks so that you can form from them a non-degenerate (that is, having a positive area) triangle. Two ways are considered different, if the length of some stick is increased by different number of centimeters in them.

Input
The single line contains 4 integers a, b, c, l (1 ≤ a, b, c ≤ 3·105, 0 ≤ l ≤ 3·105).

Output
Print a single integer — the number of ways to increase the sizes of the sticks by the total of at most l centimeters, so that you can make a non-degenerate triangle from it.

Examples
input
1 1 1 2
output
4
input
1 2 3 1
output
2
input
10 2 1 7
output
0
Note
In the first sample test you can either not increase any stick or increase any two sticks by 1 centimeter.

In the second sample test you can increase either the first or the second stick by one centimeter. Note that the triangle made from the initial sticks is degenerate and thus, doesn’t meet the conditions.

【题目链接】:http://codeforces.com/contest/572/problem/C

【题解】

x,y,z为非负数

x+1+y+1+z+1=i+3

【完整代码】

``#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;//const int MAXN = x;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);LL a,b,c,l,total = 0;LL solv(LL a,LL b,LL c,LL l){    if (b+c>a)        return 1LL*0;    //a>=b+c    LL ma = min(a-b-c,l);    return 1LL*(ma+2)*(ma+1)/2;    // y + z + no used == ma;}int main(){    //freopen("F://rush.txt","r",stdin);    rei(a);rei(b);rei(c);rei(l);    rep1(i,0,l)        total += (1LL*(i+2)*(i+1))/2;    //a+x b+y c+z    // x+1 + y+1 + z+1 == i+3;    rep1(i,0,l)    {        total -= solv(a+i,b,c,l-i);        total -= solv(b+i,a,c,l-i);        total -= solv(c+i,a,b,l-i);    }    printf("%I64d/n",total);    return 0;}``