166312025-05-07 17:06:57algoproMaximum felosztáscpp17Runtime error 40/100284ms20268 KiB
// UUID: 43f5cb11-8f07-4858-8c05-dc2139ac8e95
#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];
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;
    }

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        ll mx = 0;
        for (int j = i; j >= 1; j--) {
            mx = max(mx, a[j]);
            if (value_to_bidx.count(mx)) {
                int idx = value_to_bidx[mx];
                dp[i][idx] += dp[j-1][idx-1];
                dp[i][idx] %= MOD;
            }
        }
    }
    cout << dp[n][m] << "\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
2Accepted70ms12852 KiB
subtask210/10
3Accepted4ms2356 KiB
4Accepted4ms2356 KiB
5Accepted4ms2360 KiB
6Accepted4ms2356 KiB
7Accepted3ms820 KiB
8Accepted4ms2104 KiB
subtask315/15
9Accepted6ms2868 KiB
10Accepted6ms2356 KiB
11Accepted6ms2612 KiB
12Accepted6ms2612 KiB
13Accepted4ms2216 KiB
14Accepted4ms2068 KiB
15Accepted7ms2484 KiB
16Accepted14ms3152 KiB
17Accepted4ms1336 KiB
18Accepted8ms2520 KiB
subtask415/15
19Accepted71ms12340 KiB
20Accepted72ms12780 KiB
21Accepted54ms9520 KiB
22Accepted39ms8500 KiB
23Accepted37ms8244 KiB
24Accepted34ms8500 KiB
25Accepted52ms11060 KiB
26Accepted41ms12084 KiB
27Accepted284ms20268 KiB
28Accepted74ms6452 KiB
29Accepted41ms8668 KiB
30Accepted46ms8244 KiB
31Accepted90ms10032 KiB
32Accepted64ms8112 KiB
33Accepted216ms14136 KiB
34Accepted78ms8500 KiB
35Accepted159ms12340 KiB
36Accepted46ms3204 KiB
37Accepted59ms9264 KiB
38Accepted61ms8100 KiB
subtask50/60
39Runtime error2ms756 KiB
40Runtime error2ms564 KiB
41Runtime error2ms580 KiB
42Runtime error2ms564 KiB
43Runtime error2ms568 KiB
44Runtime error2ms564 KiB
45Runtime error1ms564 KiB
46Runtime error1ms564 KiB
47Runtime error1ms564 KiB
48Runtime error1ms564 KiB
49Runtime error2ms756 KiB
50Runtime error1ms564 KiB
51Runtime error1ms564 KiB
52Runtime error1ms564 KiB
53Runtime error2ms432 KiB
54Runtime error2ms564 KiB
55Runtime error14ms564 KiB
56Runtime error1ms564 KiB
57Runtime error1ms576 KiB
58Runtime error1ms564 KiB
59Runtime error3ms568 KiB
60Runtime error2ms564 KiB
61Runtime error14ms564 KiB
62Runtime error2ms572 KiB
63Runtime error3ms568 KiB
64Runtime error1ms564 KiB
65Runtime error3ms564 KiB
66Runtime error1ms564 KiB
67Runtime error3ms564 KiB
68Runtime error1ms564 KiB
69Runtime error3ms696 KiB
70Runtime error1ms564 KiB
71Runtime error72ms12656 KiB