Submission #1071742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071742		jer033	Text editor (CEOI24_editor)	C++17	19 / 100	1627 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlii = tuple<ll, int, int>;
using tiii = tuple<int, int, int>;
using pii = pair<int, int>;
const int INF = 2'001'111'111;

int main()
{
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int sl, sc, el, ec;
    cin >> sl >> sc >> el >> ec;
    vector<int> width(N+1, 0);
    for (int i=1; i<=N; i++)
        cin >> width[i];
    if (N<=2)
    {
        if ((sl==el) and (sc==ec))
            cout << "0\n";
        else if (el==2)
            cout << "1\n";
        else if (sl==2)
            cout << 1+min(ec-1, width[1]+1-ec) << '\n';
        else
            cout << min(abs(sc-ec), 2+min(ec-1, width[1]+1-ec)) << '\n';
    }
    else
    {
        vector<vector<vector<pii>>> edges(N+1);
        vector<vector<int>> dists(N+1);
        for (int i=1; i<=N; i++)
        {
            int maxj = 1+width[i];
            edges[i].push_back({});
            dists[i].push_back(INF);
            for (int j=1; j<=maxj; j++)
            {
                vector<pii> edg;
                //go left
                if (j!=1)
                    edg.push_back({i, j-1});
                else if (i!=1)
                    edg.push_back({i-1, 1+width[i-1]});

                //go right
                if (j!=maxj)
                    edg.push_back({i, j+1});
                else if (i!=N)
                    edg.push_back({i+1, 1});

                //go up
                if (i!=1)
                    edg.push_back({i-1, min(j, 1+width[i-1])});

                //go down
                if (i!=N)
                    edg.push_back({i+1, min(j, 1+width[i+1])});
                
                edges[i].push_back(edg);
                dists[i].push_back(INF);
            }
        }
        queue<pii> visitlist;
        visitlist.push({sl, sc});
        dists[sl][sc] = 0;
        while (!visitlist.empty())
        {
            pii kk = visitlist.front();
            visitlist.pop();
            int k1 = kk.first;
            int k2 = kk.second;
            for (pii qq: edges[k1][k2])
            {
                int q1 = qq.first;
                int q2 = qq.second;
                if (dists[q1][q2] == INF)
                {
                    dists[q1][q2] = dists[k1][k2]+1;
                    visitlist.push({q1, q2});
                }
            }
        }
        cout << dists[el][ec] << '\n';
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44