oj.uz

Submission #1068786

# Submission time Handle Problem Language Result Execution time Memory
1068786 2024-08-21T12:08:36 Z vjudge1 Text editor (CEOI24_editor) C++17
14 / 100
 511 ms 40532 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
    int n, sl, sc, el, ec;
    cin >> n >> sl >> sc >> el >> ec;
    int l[n+1];
    bool T = 0;
    for(int i=1; i<=n; ++i) {
        cin >> l[i];
        ++l[i];
        if(i != 1 && l[i] != l[i-1]) T = 1;
    }
    if(!T) {
        int ans = abs(el - sl) + abs(ec - sc);
        if(sl > el) {
            ans = min(ans, sl - el - 1 + sc + l[1] - ec);
        } else if(sl < el) {
            ans = min(ans, el - sl - 1 + l[1] - sc + ec);
        } else {
            if(sc == ec) {
                cout << 0 << endl;
                return;
            }
            if(sc < ec && sl != 1) {
                ans = min(ans, sc + l[1] - ec + 1);
            } else if(ec < sc) {
                ans = min(ans, l[1] - sc + ec + 1);
            }
        }
        cout << ans << endl;
        return;
    }
    if(n == 1) {
        cout << 0 << endl;
        return;
    } else if(n == 2) {
        int ans;
        if(el == 2 && sl != 2) {
            ans = sc;
            ans = min(ans, l[1] - sc + 1);
        } else if(el == 2 && sl == 2) {
            cout << 0 << endl;
            return;
        } else if(sl == 2) {
            ans = ec;
            ans = min(ans, 1 + l[1] - ec);
        } else {
            ans = abs(ec - sc);
            ans = min(ans, l[1] - sc + 1 + ec);
        }
        cout << ans << endl;
        return;
    }
    priority_queue<pair<int,pair<int,int>>>pq;
    vector<vector<int>>dp(n+1, vector<int>(5005, INT_MAX));
    vector<vector<bool>>visited(n+1, vector<bool>(5005, 0));
    dp[sl][sc] = 0;
    pq.push({0, {sl, sc}});
    while(!pq.empty()) {
        int x = pq.top().second.first, y = pq.top().second.second;
        if(x == el && y == ec) break;
        pq.pop();
        if(visited[x][y]) continue;
        visited[x][y] = 1;
        if(x != n) { // down
            int new_y = y;
            new_y = min(new_y, l[x+1]);
            if(dp[x+1][new_y] > dp[x][y] + 1) {
                dp[x+1][new_y] = dp[x][y] + 1;
                pq.push({-dp[x+1][new_y], {x+1, new_y}});
            }
        }
        if(x != 1) { // up
            int new_y = y;
            new_y = min(new_y, l[x-1]);
            if(dp[x-1][new_y] > dp[x][y] + 1) {
                dp[x-1][new_y] = dp[x][y] + 1;
                pq.push({-dp[x-1][new_y], {x-1, new_y}});
            }
        }
        if(y == 1 && x != 1) { // left up
            int new_x = x - 1, new_y = l[new_x];
            if(dp[x][y] + 1 < dp[new_x][new_y]) {
                dp[new_x][new_y] = dp[x][y] + 1;
                pq.push({-dp[new_x][new_y], {new_x, new_y}});
            }
        } else if(y != 1) { // left
            if(dp[x][y] + 1 < dp[x][y-1]) {
                dp[x][y-1] = dp[x][y] + 1;
                pq.push({-dp[x][y-1], {x, y-1}});
            }
        }
        if(y == l[x] && x != n) { // right down
            int new_x = x+1, new_y = 1;
            if(dp[x][y] + 1 < dp[new_x][new_y]) {
                dp[new_x][new_y] = dp[x][y] + 1;
                pq.push({-dp[new_x][new_y], {new_x, new_y}});
            }
        } else if(y != l[x]) { // right
            if(dp[x][y] + 1 < dp[x][y+1]) {
                dp[x][y+1] = dp[x][y] + 1;
                pq.push({-dp[x][y+1], {x, y+1}});
            }
        }
    }
    cout << dp[el][ec] << endl;
}

signed main() {
    solve();
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 26 ms 38236 KB Output is correct
5 Correct 26 ms 32860 KB Output is correct
6 Correct 15 ms 35932 KB Output is correct
7 Correct 48 ms 37652 KB Output is correct
8 Correct 511 ms 40280 KB Output is correct
9 Correct 329 ms 33028 KB Output is correct
10 Correct 275 ms 33864 KB Output is correct
11 Correct 321 ms 33008 KB Output is correct
12 Correct 250 ms 40492 KB Output is correct
13 Correct 422 ms 40392 KB Output is correct
14 Correct 133 ms 40284 KB Output is correct
15 Correct 32 ms 40372 KB Output is correct
16 Correct 41 ms 40448 KB Output is correct
17 Correct 223 ms 40532 KB Output is correct
18 Correct 218 ms 40428 KB Output is correct
19 Correct 271 ms 40528 KB Output is correct
20 Correct 190 ms 36692 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -