oj.uz

Submission #258108

# Submission time Handle Problem Language Result Execution time Memory
258108 2020-08-05T11:23:08 Z doowey Calvinball championship (CEOI15_teams) C++14
100 / 100
 554 ms 820 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e4 + 1;
const int MOD = (int)1e6 + 7;
int dp[2][N][2];

int mult(int a, int b){
    return (a * 1ll * b) % MOD;
}

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    dp[0][0][0] = 1;
    int a;
    int low;
    for(int i = 1; i <= n; i ++ ){
        cin >> a;
        for(int j = 0; j < i ; j ++ ){
            add(dp[1][j][1], mult(dp[0][j][1],j));
            add(dp[1][j+1][1],dp[0][j][1]);
            low = min(j,a-1);
            add(dp[1][j][1],mult(dp[0][j][0],low));
            if(j >= a)
                add(dp[1][j][0],dp[0][j][0]);
            if(j + 1 <= a)
                add(dp[1][j+1][(j+1)<a],dp[0][j][0]);
        }
        for(int j = 0 ; j <= i ; j ++ ){
            dp[0][j][0]=dp[1][j][0];
            dp[0][j][1]=dp[1][j][1];
            dp[1][j][0]=0;
            dp[1][j][1]=0;
        }
    }
    int ans = 0;
    for(int j = 1; j <= n; j ++ ){
        ans += dp[0][j][0] + dp[0][j][1];
        ans %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 384 KB Output is correct
2 Correct 117 ms 384 KB Output is correct
3 Correct 142 ms 504 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 632 KB Output is correct
2 Correct 490 ms 504 KB Output is correct
3 Correct 554 ms 820 KB Output is correct