oj.uz

Submission #569943

# Submission time Handle Problem Language Result Execution time Memory
569943 2022-05-28T10:28:18 Z 600Mihnea Calvinball championship (CEOI15_teams) C++17
70 / 100
 183 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int M =  1000007;

int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

const int N = 10000 + 7;
int n, a[N], mx = 0, ways[N][N]; /// ways[length left][current max]

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] > mx) {
      assert(a[i] == mx + 1);
      mx = a[i];
    }
  }

  for (int mx = 1; mx <= n; mx++) {
    ways[0][mx] = 1;
  }

  for (int len = 1; len <= n; len++) {
    for (int mx = 1; mx <= n; mx++) {
      /// ways[len][mx]
      ways[len][mx] = add(mul(mx, ways[len - 1][mx]), ways[len - 1][mx + 1]);
    }
  }


  int sol = 1;

  mx = 0;
  for (int i = 1; i <= n; i++) {
    for (int pl = 1; pl < a[i]; pl++) {
      addup(sol, ways[n - i][mx]);
    }
    mx = max(mx, a[i]);
  }
  cout << sol << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 4 ms 3284 KB Output is correct
3 Correct 4 ms 3304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8276 KB Output is correct
2 Correct 12 ms 8276 KB Output is correct
3 Correct 15 ms 8320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 179 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -