166312025-05-07 17:06:57algoproMaximum felosztáscpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva70ms12852 KiB
subtask210/10
3Elfogadva4ms2356 KiB
4Elfogadva4ms2356 KiB
5Elfogadva4ms2360 KiB
6Elfogadva4ms2356 KiB
7Elfogadva3ms820 KiB
8Elfogadva4ms2104 KiB
subtask315/15
9Elfogadva6ms2868 KiB
10Elfogadva6ms2356 KiB
11Elfogadva6ms2612 KiB
12Elfogadva6ms2612 KiB
13Elfogadva4ms2216 KiB
14Elfogadva4ms2068 KiB
15Elfogadva7ms2484 KiB
16Elfogadva14ms3152 KiB
17Elfogadva4ms1336 KiB
18Elfogadva8ms2520 KiB
subtask415/15
19Elfogadva71ms12340 KiB
20Elfogadva72ms12780 KiB
21Elfogadva54ms9520 KiB
22Elfogadva39ms8500 KiB
23Elfogadva37ms8244 KiB
24Elfogadva34ms8500 KiB
25Elfogadva52ms11060 KiB
26Elfogadva41ms12084 KiB
27Elfogadva284ms20268 KiB
28Elfogadva74ms6452 KiB
29Elfogadva41ms8668 KiB
30Elfogadva46ms8244 KiB
31Elfogadva90ms10032 KiB
32Elfogadva64ms8112 KiB
33Elfogadva216ms14136 KiB
34Elfogadva78ms8500 KiB
35Elfogadva159ms12340 KiB
36Elfogadva46ms3204 KiB
37Elfogadva59ms9264 KiB
38Elfogadva61ms8100 KiB
subtask50/60
39Futási hiba2ms756 KiB
40Futási hiba2ms564 KiB
41Futási hiba2ms580 KiB
42Futási hiba2ms564 KiB
43Futási hiba2ms568 KiB
44Futási hiba2ms564 KiB
45Futási hiba1ms564 KiB
46Futási hiba1ms564 KiB
47Futási hiba1ms564 KiB
48Futási hiba1ms564 KiB
49Futási hiba2ms756 KiB
50Futási hiba1ms564 KiB
51Futási hiba1ms564 KiB
52Futási hiba1ms564 KiB
53Futási hiba2ms432 KiB
54Futási hiba2ms564 KiB
55Futási hiba14ms564 KiB
56Futási hiba1ms564 KiB
57Futási hiba1ms576 KiB
58Futási hiba1ms564 KiB
59Futási hiba3ms568 KiB
60Futási hiba2ms564 KiB
61Futási hiba14ms564 KiB
62Futási hiba2ms572 KiB
63Futási hiba3ms568 KiB
64Futási hiba1ms564 KiB
65Futási hiba3ms564 KiB
66Futási hiba1ms564 KiB
67Futási hiba3ms564 KiB
68Futási hiba1ms564 KiB
69Futási hiba3ms696 KiB
70Futási hiba1ms564 KiB
71Futási hiba72ms12656 KiB