【好题】构造+数学+思维——NCPC 2019 Game of Gnomes

/*
这个构造思路为啥想不到呢。。
显然对于一组来说，k+x和x的结果对答案是一样的
枚举完整的k的个数  n/k-m<=i<=n/k 
剩下的平均分 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

ll n,m,k;

int main(){
    cin>>n>>m>>k;
    ll ans=0;
    for(ll i=max(n/k-m,0ll);i<=n/k;i++){
        ll sum=i*k*(i+1)/2;
        ll last=n-i*k;
        sum+=last*i;
        
        ll a=last%m,b=m-a;//a组多，b组少
        ll numa=last/m+1,numb=last/m;
        sum+=(numa*a+numa)*a/2;
        sum+=numb*b*a;
        sum+=(numb*b+numb)*b/2; 
        
        ans=max(ans,sum);
    }
    cout<<ans<<'
';
}