153052025-02-18 09:44:01TortelliniJrSzitakötő (50 pont)cpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/024ms6196 KiB
3Hibás válasz0/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Hibás válasz0/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Hibás válasz0/11ms316 KiB
8Hibás válasz0/11ms316 KiB
9Hibás válasz0/11ms316 KiB
10Hibás válasz0/21ms316 KiB
11Hibás válasz0/21ms316 KiB
12Hibás válasz0/21ms500 KiB
13Hibás válasz0/21ms500 KiB
14Hibás válasz0/21ms508 KiB
15Hibás válasz0/21ms384 KiB
16Hibás válasz0/21ms316 KiB
17Hibás válasz0/22ms316 KiB
18Hibás válasz0/22ms512 KiB
19Hibás válasz0/21ms320 KiB
20Hibás válasz0/21ms316 KiB
21Hibás válasz0/11ms556 KiB
22Hibás válasz0/221ms6208 KiB
23Hibás válasz0/220ms6244 KiB
24Hibás válasz0/224ms6120 KiB
25Hibás válasz0/225ms6208 KiB
26Hibás válasz0/224ms6200 KiB
27Hibás válasz0/218ms6164 KiB
28Hibás válasz0/223ms6196 KiB
29Hibás válasz0/220ms6204 KiB
30Hibás válasz0/225ms6056 KiB
31Hibás válasz0/225ms6204 KiB