[CF1413E] Solo mid Oracle

Description

游戏参数描述为 (a,b,c,d)，表示有一个技能，单次攻击的伤害为 (a)，随后的 (c) 秒中每秒恢复 (b)，每次攻击后 (d) 秒后才能进行下一次攻击。求能造成的瞬时最大伤害为多少，无解输出 (-1)。

Solution

无解的充要条件是 (a>bc)。

对于一次攻击，在它执行后的每一秒，其影响分别为 (a, a-b, a-2b, ...)，设 (t(a,b)) 为最大的满足 (a-tb ge 0) 的整数 (t)，显然 (t=[frac a b])，则一个技能的存在时间如超过 (t) 秒则不如不用。

很显然我们需要使得第一个技能存在不超过 (t) 秒，因此我们可以容纳 (n=[frac t d]) 组技能的间隔时间。因此我们执行 (n) 组完整的技能，外加一个技能的开头，因此造成的总贡献为 ((n+1)a - frac {n(n+1)} 2 bd)。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c,d,t,n;
        cin>>a>>b>>c>>d;
        if(a>b*c)
        {
            puts("-1");
        }
        else
        {
            int t=a/b;
            int n=t/d;
            cout<<(n+1)*a-n*(n+1)/2*b*d<<endl;
        }
    }
}