oj.uz

Submission #790526

# Submission time Handle Problem Language Result Execution time Memory
790526 2023-07-22T19:33:06 Z skittles1412 Ancient Books (IOI17_books) C++17
42 / 100
 2000 ms 18664 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

ll minimum_walk(vector<int> arr, int kv) {
    int n = sz(arr), trans[n - 1] {};
    for (int i = 0; i < n; i++) {
        for (int j = i; j < arr[i]; j++) {
            trans[j]++;
            dbg(i, j);
        }
    }
    int sort_p, sort_s;
    for (sort_p = 0; sort_p < n && arr[sort_p] == sort_p; sort_p++)
        ;
    for (sort_s = n - 1; sort_s >= 0 && arr[sort_s] == sort_s; sort_s--)
        ;
    int dp[n][n];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][n - 1] = 0;
    for (int l = 0; l < n; l++) {
        for (int r = n - 1; r >= 0; r--) {
            if (l <= sort_p && r >= sort_s) {
                dp[l][r] = 0;
            }
            for (int i = l; i <= r; i++) {
                dp[l][r] = min({dp[l][r], dp[arr[i]][r], dp[l][arr[i]]});
            }
            if (l) {
                dp[l][r] = min(dp[l][r], 1 + dp[l - 1][r]);
            }
            if (r + 1 < n) {
                dp[l][r] = min(dp[l][r], 1 + dp[l][r + 1]);
            }
        }
    }
    long ans = 2 * dp[kv][kv];
    for (auto& a : trans) {
        ans += a * 2;
    }
    return ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 382 ms 4200 KB Output is correct
20 Correct 365 ms 4204 KB Output is correct
21 Correct 346 ms 4204 KB Output is correct
22 Correct 381 ms 4200 KB Output is correct
23 Correct 371 ms 4204 KB Output is correct
24 Correct 351 ms 4200 KB Output is correct
25 Correct 349 ms 4200 KB Output is correct
26 Correct 363 ms 4200 KB Output is correct
27 Correct 355 ms 4180 KB Output is correct
28 Correct 372 ms 4204 KB Output is correct
29 Correct 355 ms 4200 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 382 ms 4200 KB Output is correct
20 Correct 365 ms 4204 KB Output is correct
21 Correct 346 ms 4204 KB Output is correct
22 Correct 381 ms 4200 KB Output is correct
23 Correct 371 ms 4204 KB Output is correct
24 Correct 351 ms 4200 KB Output is correct
25 Correct 349 ms 4200 KB Output is correct
26 Correct 363 ms 4200 KB Output is correct
27 Correct 355 ms 4180 KB Output is correct
28 Correct 372 ms 4204 KB Output is correct
29 Correct 355 ms 4200 KB Output is correct
30 Execution timed out 2064 ms 18664 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 4200 KB Output is correct
2 Correct 353 ms 4200 KB Output is correct
3 Correct 359 ms 4204 KB Output is correct
4 Correct 352 ms 4204 KB Output is correct
5 Correct 350 ms 4180 KB Output is correct
6 Correct 368 ms 4204 KB Output is correct
7 Correct 370 ms 4204 KB Output is correct
8 Correct 358 ms 4216 KB Output is correct
9 Correct 363 ms 4200 KB Output is correct
10 Correct 344 ms 4204 KB Output is correct
11 Correct 355 ms 4204 KB Output is correct
12 Correct 361 ms 4204 KB Output is correct
13 Correct 390 ms 4200 KB Output is correct
14 Correct 384 ms 4204 KB Output is correct
15 Correct 364 ms 4180 KB Output is correct
16 Correct 351 ms 4204 KB Output is correct
17 Correct 362 ms 4204 KB Output is correct
18 Correct 352 ms 4204 KB Output is correct
19 Correct 361 ms 4200 KB Output is correct
20 Correct 356 ms 4204 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 382 ms 4200 KB Output is correct
20 Correct 365 ms 4204 KB Output is correct
21 Correct 346 ms 4204 KB Output is correct
22 Correct 381 ms 4200 KB Output is correct
23 Correct 371 ms 4204 KB Output is correct
24 Correct 351 ms 4200 KB Output is correct
25 Correct 349 ms 4200 KB Output is correct
26 Correct 363 ms 4200 KB Output is correct
27 Correct 355 ms 4180 KB Output is correct
28 Correct 372 ms 4204 KB Output is correct
29 Correct 355 ms 4200 KB Output is correct
30 Execution timed out 2064 ms 18664 KB Time limit exceeded
31 Halted 0 ms 0 KB -