Submission #1068693

#TimeUsernameProblemLanguageResultExecution timeMemory
1068693vjudge1Text editor (CEOI24_editor)C++17
14 / 100
410 ms1048576 KiB
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

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

    int n;
    cin >> n;
    pii f, t;
    cin >> f.first >> f.second;
    f.second--;
    f.first--;
    cin >> t.first >> t.second;
    t.first--;
    t.second--;

    vector<int> len(n);
    vector<vector<int> > dist(n);
    for (int i = 0; i < n; i++) {
        cin >> len[i];
        dist[i].resize(len[i] + 1, 1e9);
    }
    dist[f.first][f.second] = 0;
    queue<pii> q;
    q.push(f);
    while (!q.empty()) {
        pii curr = q.front(); q.pop();

        vector<pii> nei;
        pii lft = curr;
        if (lft.second > 0)
            lft.second--;
        else if (lft.first != 0)
            lft = pii(lft.first - 1, len[lft.first - 1]);
        
        pii rght = curr;
        if (rght.second < len[rght.first])
            rght.second++;
        else if (rght.first < n - 1)
            rght.second = 0, rght.first++;
        
        pii up = curr;
        if (curr.first != 0)
        {
            up.first--;
            up.second = min(up.second, len[up.first]);
        }

        pii down = curr;
        if (curr.first != n - 1) {
            down.first++;
            down.second = min(down.second, len[down.first]);
        }

        nei = {up, down, rght, lft};
        for (pii guy : nei) {
            if (dist[guy.first][guy.second] != 1e9)
                continue;
            dist[guy.first][guy.second] = dist[curr.first][curr.second] + 1;
            q.push(guy);
        }
    }

    cout << dist[t.first][t.second] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...