Submission #1112862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112862	2024-11-15T04:35:06 Z	slycelote	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	592 KB

triusis

#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); iostream::sync_with_stdio(false);

    int n, m; cin >> n >> m;
    const ll NEGINF = -1 - (n+1)*m;

    vector<ll> a(n+2);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] -= i*m;
    }
    a[n+1] = NEGINF;

    vector<int> dp(n+2);
    for (int i = n; i >= 0; --i) {
        int j = i+1;
        while (a[j] > a[i])
            ++j;
        dp[i] = dp[j] + j - i - 1;

        ll maxval = NEGINF;
        for (int j = i+1; j <= n+1; ++j) {
            if (maxval < a[j] && a[j] <= a[i]) {
                dp[i] = min(dp[i], dp[j] + j - i - 1);
            }
            maxval = max(maxval, a[j]);
        }

    }

    cout << dp[0] << endl;
}

Subtask #1

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Incorrect	1 ms	336 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Incorrect	1 ms	336 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Incorrect	1 ms	336 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	592 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Incorrect	1 ms	336 KB	Output isn't correct
13	Halted	0 ms	0 KB	-