违规紫杉

本题来源：上海市计算机学会竞赛2023年11月丙组月赛（本人比赛时间已到）

描述

给 $n$ 个点染色，每个点都需要一种独一无二的颜色。颜色以数字编号，每个点对颜色都有各自的要求。其中第 $i$ 个点要求颜色的编号为 $1$ 到 $a_i$ 之间的整数。

请统计有多少种染色方案数满足要求，由于答案可能很大，输出模 $1,000,000,007$的余数

对于 $100\%$ 的数据 $1\le n\le 300,000$, $1\le a_i\le 10^9$

贴上楼主其丑无比的代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
const int mod = 1e9+7;
int n;
long long a[maxn],f[maxn],g[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    f[0]=1;
    for(int i=1;i<=n;i++){
        memset(g,0,sizeof(g));
        for(int j=1;j<=a[i];j++)g[j]=f[j-1];
        for(int j=1;j<=a[i];j++)g[j]=(g[j]+g[j-1])%mod;
        for(int j=a[i];j>=1;j--)f[j]=(f[j]+g[j])%mod;
    }
    long long ans=0;
    for(int i=1;i<=a[n];i++)ans=(ans+f[i])%mod;
    printf("%lld\n",ans);
    return 0;
}