oj.uz

Submission #207842

# Submission time Handle Problem Language Result Execution time Memory
207842 2020-03-09T08:58:00 Z stefdasca Calvinball championship (CEOI15_teams) C++14
100 / 100
 251 ms 508 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod = 1000007;

int n, v[10002];
int dp[2][10002];

int add(int a, int b)
{
    int ans = a+b;
    if(ans >= mod)
        ans -= mod;
    return ans;
}
long long mul(long long a, long long b)
{
    return (a * b) % mod;
}
int main()
{
    cin >> n;
    int maxi = 1;
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        dp[1][max(v[i], maxi) - (v[i] > maxi)] = v[i] - 1;
        maxi = max(maxi, v[i]);
        for(int j = 1; j <= i; ++j)
        {
            dp[1][j] = add(dp[1][j], mul(dp[0][j], j));
            dp[1][j+1] = add(dp[1][j+1], dp[0][j]);
        }
        memcpy(dp[0], dp[1], sizeof(dp[1]));
        memset(dp[1], 0, sizeof(dp[1]));
    }
    int sum = 1;
    for(int i = 1; i <= n; ++i)
        sum = add(sum, dp[0][i]);
    cout << sum;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 376 KB Output is correct
2 Correct 74 ms 376 KB Output is correct
3 Correct 74 ms 504 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 376 KB Output is correct
2 Correct 236 ms 508 KB Output is correct
3 Correct 242 ms 504 KB Output is correct