oj.uz

Submission #419839

# Submission time Handle Problem Language Result Execution time Memory
419839 2021-06-07T13:51:57 Z schse Financial Report (JOI21_financial) C++17
28 / 100
 718 ms 4176 KB 
#include <bits/stdc++.h>
using namespace std;

int N, D;
vector<int> arr;
map<int, int> dp[500];

int rec(int n, int cmax = -1)
{
    int score = arr[n] > cmax ? 1 : 0;
    int tmp = 0;
    int cmal = cmax;

    if (dp[n].count(cmax))
        return dp[n][cmax];

    if (n == N - 1)
        return dp[n][cmax] = score;

    cmax = max(cmax, arr[n]);
    for (int i = 1; i <= D && i + n <= N - 1; i++)
        tmp = max(tmp, rec(n + i, cmax));
    return dp[n][cmal] = score + tmp;
}

int main()
{
    cin >> N >> D;
    arr.resize(N);
    for (int &i : arr)
        cin >> i;

    assert(N <= 400);
    //compression

    {
        vector<int> arr2 = arr;
        sort(arr2.begin(), arr2.end());
        map<int, int> copr;
        int c = 1;
        copr[arr2[0]] = ++c;
        for (int i = 1; i < N; i++)
            if (arr2[i - 1] < arr2[i])
                copr[arr2[i]] = ++c;
        for (int &i : arr)
            i = copr[i];
    }

    int score = 0;
    for (int i = 0; i < N; i++)
        score = max(score, rec(i));
    cout << score;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 9 ms 1740 KB Output is correct
29 Correct 6 ms 1132 KB Output is correct
30 Correct 49 ms 2848 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 718 ms 4176 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 9 ms 1536 KB Output is correct
35 Correct 17 ms 1944 KB Output is correct
36 Correct 135 ms 3456 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 6 ms 972 KB Output is correct
39 Correct 66 ms 3396 KB Output is correct
40 Correct 75 ms 3444 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 9 ms 1740 KB Output is correct
29 Correct 6 ms 1132 KB Output is correct
30 Correct 49 ms 2848 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 718 ms 4176 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 9 ms 1536 KB Output is correct
35 Correct 17 ms 1944 KB Output is correct
36 Correct 135 ms 3456 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 6 ms 972 KB Output is correct
39 Correct 66 ms 3396 KB Output is correct
40 Correct 75 ms 3444 KB Output is correct
41 Runtime error 4 ms 460 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 2776 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 2756 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 9 ms 1740 KB Output is correct
29 Correct 6 ms 1132 KB Output is correct
30 Correct 49 ms 2848 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 718 ms 4176 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 9 ms 1536 KB Output is correct
35 Correct 17 ms 1944 KB Output is correct
36 Correct 135 ms 3456 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 6 ms 972 KB Output is correct
39 Correct 66 ms 3396 KB Output is correct
40 Correct 75 ms 3444 KB Output is correct
41 Runtime error 4 ms 460 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -