oj.uz

Submission #773289

# Submission time Handle Problem Language Result Execution time Memory
773289 2023-07-04T19:31:42 Z Ahmed57 Calvinball championship (CEOI15_teams) C++17
100 / 100
 312 ms 724 KB 
#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    long long dp[2][10001][2];
    int mod = 1000007;
    int n;cin>>n;
    int arr[n];
    for(int i = 0;i<n;i++){
        cin>>arr[i];
    }
    for(int i = n;i>=0;i--){
        for(int e = 0;e<2;e++){
            for(int j = 0;j<=i;j++){
                if(i==n){
                    dp[i&1][j][e] = 1;
                    continue;
                }
                if(e||arr[i]>j){
                    dp[i&1][j][e] = (dp[!(i&1)][j+1][e|(arr[i]<(j+1))]+dp[!(i&1)][j][1]*j)%mod;
                }else{
                    dp[i&1][j][e] = (dp[!(i&1)][j][e]+dp[!(i&1)][j][1]*(arr[i]-1))%mod;
                }
            }
        }
    }
    cout<<dp[0][0][0]<<"\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 632 KB Output is correct
3 Correct 1 ms 596 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 624 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 636 KB Output is correct
2 Correct 3 ms 624 KB Output is correct
3 Correct 4 ms 624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 696 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 724 KB Output is correct
2 Correct 63 ms 644 KB Output is correct
3 Correct 68 ms 660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 596 KB Output is correct
2 Correct 230 ms 596 KB Output is correct
3 Correct 312 ms 696 KB Output is correct