oj.uz

Submission #1081558

# Submission time Handle Problem Language Result Execution time Memory
1081558 2024-08-30T07:20:04 Z jk_ Calvinball championship (CEOI15_teams) C++14
100 / 100
 94 ms 644 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1000007;

int main() {
  int n; cin >> n;
  vector<int> v;
  copy_n(istream_iterator<int>(cin), n, back_inserter(v));
  vector<int> prefixmax(n);
  partial_sum(v.begin(), v.end(), prefixmax.begin(), [](int a, int b) { return max(a, b); });
  int64_t ans = 1;

  array<vector<int>, 2> dp;
  dp[0].assign(n, 1);
  dp[1].assign(n, 1);

  for (int i = n-1; i >= 1; --i) {
    if (i==n-1) {
      dp[0].assign(n, 1);
    } else {
      auto& dp0 = dp[(n-i-1)%2];
      auto& dp1 = dp[(n-i)%2];
      for (int k = 1; k <= i; ++k)
        dp0[k] = (k*(int64_t)dp1[k] + dp1[k+1])%mod;
    }

    ans = (ans + (v[i]-1)*(int64_t)dp[(n-i-1)%2][prefixmax[i-1]])%mod;
  }
  cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 624 KB Output is correct
2 Correct 90 ms 604 KB Output is correct
3 Correct 94 ms 644 KB Output is correct