oj.uz

Submission #231013

# Submission time Handle Problem Language Result Execution time Memory
231013 2020-05-12T10:41:02 Z AlexLuchianov Calvinball championship (CEOI15_teams) C++14
100 / 100
 323 ms 632 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) ? (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 10000;
int const modulo = 1000007;
int v[5 + nmax], pref[5 + nmax];
int dp[5 + nmax];

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++) {
    cin >> v[i];
    pref[i] = max(pref[i - 1], v[i]);
  }
  for(int i = 0; i <= n; i++)
    dp[i] = 1;

  ll result = 0;
  for(int i = n; 1 <= i; i--){
    for(int j = 1; j < v[i]; j++) {
      result += dp[pref[i - 1]];
      if(modulo <= result)
        result -= modulo;
    }
    for(int j = 0; j <= n; j++)
      dp[j] = (1LL * dp[j] * j + dp[j + 1]) % modulo;
  }
  cout << (result + 1) % modulo;
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 512 KB Output is correct
2 Correct 236 ms 504 KB Output is correct
3 Correct 323 ms 632 KB Output is correct