oj.uz

Submission #223746

# Submission time Handle Problem Language Result Execution time Memory
223746 2020-04-16T09:39:00 Z dolphingarlic Žarulje (COI15_zarulje) C++14
22 / 100
 38 ms 23160 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

int a[2002];
ll dp[2002][2002];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    dp[1][n] = 1;
    for (int j = n - 1; j; j--) {
        FOR(i, 1, n - j + 2) {
            if (a[i - 1] >= a[i + j]) dp[i][i + j - 1] += dp[i - 1][i + j - 1];
            if (a[i + j] >= a[i - 1]) dp[i][i + j - 1] += dp[i][i + j];
            if (dp[i][i + j - 1] >= MOD) dp[i][i + j - 1] -= MOD;
        }
    }

    while (k--) {
        int pos;
        cin >> pos;
        cout << dp[pos][pos] << '\n';
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 13 ms 8320 KB Output is correct
3 Correct 38 ms 23160 KB Output is correct
4 Correct 37 ms 23032 KB Output is correct
5 Correct 36 ms 23036 KB Output is correct
6 Correct 36 ms 23032 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 13 ms 8320 KB Output is correct
3 Correct 38 ms 23160 KB Output is correct
4 Correct 37 ms 23032 KB Output is correct
5 Correct 36 ms 23036 KB Output is correct
6 Correct 36 ms 23032 KB Output is correct
7 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -