oj.uz

답안 #1068596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068596 2024-08-21T10:51:53 Z vjudge1 Text editor (CEOI24_editor) C++17
14 / 100
 499 ms 40648 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];
    for(int i=1; i<=n; ++i) {
        cin >> l[i];
        ++l[i];
    }
    if(n == 1) {
        int ans = abs(ec - sc);
        ans = min(ans, sc + l[1] - ec);
        ans = min(ans, l[1] - sc + ec);
        cout << ans << endl;
        return;
    }
    if(n == 2) {
        if(sl == el) {
            int ans = abs(ec - sc), tmp = 0;
            tmp += sc + 1;
            tmp += abs(l[(sl+1)%2] - ec);
            ans = min(ans, tmp);
            tmp = 0;
            tmp += l[sl] - sc + 1;
            tmp += ec;
            ans = min(ans, tmp);
            cout << ans << endl;
            return;
        }
        int ans;
        if(sl == 1) {
            int y = sc;
            y = min(y, l[2]);
            ans = 1 + abs(y - ec);
            ans = min(ans, sc + l[2] - ec);
            ans = min(ans, l[1] - sc + ec);
        } else {
            int y = sc;
            y = min(y, l[1]);
            ans = 1 + abs(y - ec);
            ans = min(ans, sc + l[1] - ec);
            ans = min(ans, l[2] - sc + 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 26 ms 38492 KB Output is correct
5 Correct 31 ms 32856 KB Output is correct
6 Correct 19 ms 35932 KB Output is correct
7 Correct 48 ms 37896 KB Output is correct
8 Correct 499 ms 40528 KB Output is correct
9 Correct 313 ms 33036 KB Output is correct
10 Correct 282 ms 33864 KB Output is correct
11 Correct 325 ms 33116 KB Output is correct
12 Correct 247 ms 40452 KB Output is correct
13 Correct 477 ms 40532 KB Output is correct
14 Correct 140 ms 40408 KB Output is correct
15 Correct 45 ms 40284 KB Output is correct
16 Correct 46 ms 40408 KB Output is correct
17 Correct 208 ms 40624 KB Output is correct
18 Correct 213 ms 40532 KB Output is correct
19 Correct 278 ms 40648 KB Output is correct
20 Correct 196 ms 36540 KB Output is correct

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -