oj.uz

Submission #230127

# Submission time Handle Problem Language Result Execution time Memory
230127 2020-05-08T16:27:48 Z nicolaalexandra Calvinball championship (CEOI15_teams) C++14
100 / 100
 397 ms 608 KB 
#include <bits/stdc++.h>
#define DIM 10010
#define MOD 1000007
using namespace std;
int v[DIM],maxi[DIM],dp[2][DIM];
int n,i,j;
int main (){

   // ifstream cin ("teams.in");
   // ofstream cout ("teams.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i];
        maxi[i] = max (maxi[i-1],v[i]);
    }

    /// dp[i][j] - in cate moduri pot construi un sir cu i elemente stiind ca am pus pana la j deja
    for (i=0;i<=n;i++)
        dp[0][i] = 1;

    int sol = v[n], t = 1;
    for (i=1;i<n;i++){
        for (j=1;j<=n;j++)
            dp[t][j] = (dp[1-t][j+1] + 1LL * dp[1-t][j] * j % MOD) % MOD;

        sol = (sol + 1LL * dp[t][maxi[n-i-1]] * (v[n-i]-1) % MOD) % MOD;
        t = 1-t;
    }

    cout<<sol;

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
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 5 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 256 KB Output is correct

Subtask #5
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 5 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 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 9 ms 384 KB Output is correct
2 Correct 9 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 387 ms 608 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 516 KB Output is correct
2 Correct 394 ms 516 KB Output is correct
3 Correct 397 ms 512 KB Output is correct