153052025-02-18 09:44:01TortelliniJrSzitakötő (50 pont)cpp17Wrong answer 2/5025ms6244 KiB
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int countValidDirections(int N, int K, vector<int>& sizes) {
    // Initialize DP table
    vector<vector<int>> dp(N + 1, vector<int>(2, 0));
    dp[K][0] = 1; // Rózsabimbó can start moving left
    dp[K][1] = 1; // Rózsabimbó can start moving right

    // Process each larva from K to N
    for (int i = K; i < N; ++i) {
        if (sizes[i] < sizes[i + 1]) {
            dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % MOD;
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][1]) % MOD;
        } else {
            dp[i + 1][0] = (dp[i + 1][0] + dp[i][1]) % MOD;
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD;
        }
    }

    // Process each larva from K to 1
    for (int i = K; i > 1; --i) {
        if (sizes[i] < sizes[i - 1]) {
            dp[i - 1][0] = (dp[i - 1][0] + dp[i][0]) % MOD;
            dp[i - 1][1] = (dp[i - 1][1] + dp[i][1]) % MOD;
        } else {
            dp[i - 1][0] = (dp[i - 1][0] + dp[i][1]) % MOD;
            dp[i - 1][1] = (dp[i - 1][1] + dp[i][0]) % MOD;
        }
    }

    // The result is the sum of all valid configurations
    int result = (dp[N][0] + dp[N][1] + dp[1][0] + dp[1][1]) % MOD;
    return result;
}

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

    int N, K;
    cin >> N >> K;
    vector<int> sizes(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> sizes[i];
    }

    int result = countValidDirections(N, K, sizes);
    cout << result << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Accepted0/01ms316 KiB
2Wrong answer0/024ms6196 KiB
3Wrong answer0/11ms316 KiB
4Accepted1/11ms316 KiB
5Wrong answer0/11ms316 KiB
6Accepted1/11ms316 KiB
7Wrong answer0/11ms316 KiB
8Wrong answer0/11ms316 KiB
9Wrong answer0/11ms316 KiB
10Wrong answer0/21ms316 KiB
11Wrong answer0/21ms316 KiB
12Wrong answer0/21ms500 KiB
13Wrong answer0/21ms500 KiB
14Wrong answer0/21ms508 KiB
15Wrong answer0/21ms384 KiB
16Wrong answer0/21ms316 KiB
17Wrong answer0/22ms316 KiB
18Wrong answer0/22ms512 KiB
19Wrong answer0/21ms320 KiB
20Wrong answer0/21ms316 KiB
21Wrong answer0/11ms556 KiB
22Wrong answer0/221ms6208 KiB
23Wrong answer0/220ms6244 KiB
24Wrong answer0/224ms6120 KiB
25Wrong answer0/225ms6208 KiB
26Wrong answer0/224ms6200 KiB
27Wrong answer0/218ms6164 KiB
28Wrong answer0/223ms6196 KiB
29Wrong answer0/220ms6204 KiB
30Wrong answer0/225ms6056 KiB
31Wrong answer0/225ms6204 KiB