oj.uz

Submission #1004459

# Submission time Handle Problem Language Result Execution time Memory
1004459 2024-06-21T09:12:53 Z messiuuuuu Žarulje (COI15_zarulje) C++14
22 / 100
 46 ms 29008 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e3 + 5;
const int MOD = 1e9 + 7;

int n, k;
int dp[MAXN][MAXN], a[MAXN];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = a[n + 1] = -2e9;
    dp[1][n] = 1;
    for (int le = n; le >= 1; le--)
    {
        for (int l = 1; l + le - 1 <= n; l++)
        {
            int r = l + le - 1;
            if (a[l - 1] > a[r + 1])
            {
                dp[l][r] += dp[l - 1][r];
                dp[l][r] %= MOD;
            }
            if (a[l - 1] < a[r + 1])
            {
                dp[l][r] += dp[l][r + 1];
                dp[l][r] %= MOD;
            }
            if (a[l - 1] == a[r + 1])
            {
                dp[l][r] += dp[l - 1][r];
                dp[l][r] %= MOD;
                 dp[l][r] += dp[l][r + 1];
                dp[l][r] %= MOD;
            }
        }
    }
    while (k-- > 0)
    {
        int p;
        cin >> p;
        cout << dp[p][p] << '\n';
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 8 ms 6232 KB Output is correct
3 Correct 22 ms 14172 KB Output is correct
4 Correct 24 ms 14172 KB Output is correct
5 Correct 19 ms 14164 KB Output is correct
6 Correct 20 ms 14168 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 29008 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 8 ms 6232 KB Output is correct
3 Correct 22 ms 14172 KB Output is correct
4 Correct 24 ms 14172 KB Output is correct
5 Correct 19 ms 14164 KB Output is correct
6 Correct 20 ms 14168 KB Output is correct
7 Runtime error 46 ms 29008 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -