Submission #1307264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307264		HoriaHaivas	Calvinball championship (CEOI15_teams)	C++20	30 / 100	414 ms	968 KiB

teams

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int mod=1e6+7;
int dp[2][10005][2];
int n;
vector<int> v;

void modit(int &x)
{
    if (x>=mod)
        x-=mod;
}

int smaller(vector<int> &v)///il fac strict (cred)
{
    int i,j,ans;
    dp[0][0][1]=1;
    for (i=1;i<=n;i++)
    {
         for (j=1;j<=n;j++)
         {
              dp[i%2][j][0]=0;
              dp[i%2][j][1]=0;
         }
         for (j=1;j<=n;j++)
         {
              dp[i%2][j][0]+=(dp[(i-1)%2][j][0]*j)%mod;
              modit(dp[i%2][j][0]);
              dp[i%2][j][0]+=(dp[(i-1)%2][j-1][0]);
              modit(dp[i%2][j][0]);
              dp[i%2][j][0]+=(dp[(i-1)%2][j][1]*(v[i]-1))%mod;
              modit(dp[i%2][j][0]);
              if (v[i]<=j)
              dp[i%2][j][1]+=(dp[(i-1)%2][j][1]);
              if (v[i]==j)
              dp[i%2][j][1]+=(dp[(i-1)%2][j-1][1]);
              modit(dp[i%2][j][1]);
         }
    }
    ans=0;
    for(j=1;j<=n;j++)
    {
        ans+=dp[n%2][j][0];
        modit(ans);
    }
    return ans;
}


signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i,x;
    cin >> n;
    v.push_back(0);
    for (i=1;i<=n;i++)
    {
         cin >> x;
         v.push_back(x);
    }
    cout << (smaller(v)+1)%mod;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10