166442025-05-07 18:04:14algoproMaximum felosztáscpp17Time limit exceeded 25/1001.1s24108 KiB
// UUID: f25383c4-c4b3-461c-abcd-06a49a357bee
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 2001;
const ll INF = 1e15;
const ll MOD = 1e9+7;

ll a[MAXN], b[MAXN], dp[MAXN][MAXN], pref[MAXN][MAXN];
map<ll, int> value_to_bidx;

void solve() {
    int n, m; cin >> n >> m;
    a[0] = INF;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= m; i++) {
        value_to_bidx[b[i]] = i;
    }

    vector<int> st;
    st.emplace_back(0);
    pref[0][0] = dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {

        while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
        st.emplace_back(i);

        for (int a = 1; a <= n; a++) {
            for (int b = 0; b <= m; b++) {
                pref[b][a] = pref[b][a-1] + dp[b][a];
            }
        }

        for (int j = st.size()-1; j >= 1; j--) {
            if (value_to_bidx.count(a[st[j]])) {
                int idx = value_to_bidx[a[st[j]]];

                int l = st[j-1]+1, r = st[j];
                dp[idx][i] += pref[idx-1][r-1] - (l >= 2 ? pref[idx-1][l-2] : 0);
                dp[idx][i] %= MOD;
            }
        }
    }
    cout << dp[m][n] << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded1.093s8348 KiB
subtask210/10
3Accepted2ms316 KiB
4Accepted2ms316 KiB
5Accepted2ms316 KiB
6Accepted2ms328 KiB
7Accepted2ms316 KiB
8Accepted2ms316 KiB
subtask315/15
9Accepted78ms2884 KiB
10Accepted37ms1464 KiB
11Accepted37ms1756 KiB
12Accepted14ms1180 KiB
13Accepted6ms564 KiB
14Accepted2ms316 KiB
15Accepted190ms4660 KiB
16Accepted212ms5252 KiB
17Accepted56ms2112 KiB
18Accepted57ms2356 KiB
subtask40/15
19Time limit exceeded1.077s16232 KiB
20Time limit exceeded1.077s8500 KiB
21Accepted630ms2612 KiB
22Accepted43ms748 KiB
23Accepted43ms564 KiB
24Accepted24ms564 KiB
25Time limit exceeded1.082s8560 KiB
26Time limit exceeded1.082s8600 KiB
27Time limit exceeded1.082s24108 KiB
28Time limit exceeded1.083s24040 KiB
29Accepted82ms844 KiB
30Accepted82ms820 KiB
31Time limit exceeded1.085s5288 KiB
32Time limit exceeded1.083s4148 KiB
33Time limit exceeded1.092s12340 KiB
34Time limit exceeded1.092s12308 KiB
35Time limit exceeded1.085s8432 KiB
36Time limit exceeded1.083s8244 KiB
37Accepted651ms3368 KiB
38Accepted634ms2612 KiB
subtask50/60
39Runtime error2ms316 KiB
40Runtime error2ms316 KiB
41Runtime error1ms316 KiB
42Runtime error1ms564 KiB
43Runtime error2ms316 KiB
44Runtime error1ms316 KiB
45Runtime error1ms316 KiB
46Runtime error1ms316 KiB
47Runtime error1ms316 KiB
48Runtime error1ms508 KiB
49Runtime error1ms316 KiB
50Runtime error1ms316 KiB
51Runtime error2ms316 KiB
52Runtime error2ms508 KiB
53Runtime error2ms316 KiB
54Runtime error2ms316 KiB
55Time limit exceeded1.082s1332 KiB
56Runtime error1ms316 KiB
57Runtime error1ms316 KiB
58Runtime error1ms316 KiB
59Runtime error3ms568 KiB
60Runtime error1ms316 KiB
61Time limit exceeded1.1s2612 KiB
62Runtime error1ms316 KiB
63Runtime error3ms568 KiB
64Runtime error1ms508 KiB
65Runtime error3ms564 KiB
66Runtime error1ms316 KiB
67Runtime error3ms568 KiB
68Runtime error1ms316 KiB
69Runtime error3ms564 KiB
70Runtime error1ms316 KiB
71Runtime error12ms8500 KiB