제출 #1177523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177523		alexdd	Text editor (CEOI24_editor)	C++20	0 / 100	565 ms	1114112 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n,slin,scol,elin,ecol;
int l[1000005];
int solve()
{
    int rez=INF;
    for(int le=min(slin,elin);le>=1;le--)
    {
        for(int ri=max(slin,elin);ri<=n;ri++)
        {
            int mnm=INF,pm,um;
            for(int i=le;i<=ri;i++)
            {
                if(l[i] < mnm)
                {
                    mnm = l[i];
                    pm = um = i;
                }
                else if(l[i] == mnm)
                    um = i;
            }
            int aux=0;
            aux += ri-le;
            aux += min(slin,elin) - le;
            aux += ri - max(slin,elin);


            rez = min(rez, aux + abs(ecol - min(scol, mnm)));
            rez = min(rez, aux + scol + abs(mnm - ecol) + (ri == pm));
            if(scol <= mnm) rez = min(rez, aux + (mnm - scol) + 1 + ecol + (le == um));
            if(scol > mnm) rez = min(rez, aux + 1 + ecol + (le == um));
        }
    }
    return rez;
}
int solve_brut()
{
    vector<vector<int>> dist(n+2);
    for(int i=1;i<=n;i++)
    {
        dist[i].resize(l[i]+2,INF);
    }
    deque<pair<int,int>> dq;
    dist[slin][scol]=0;
    dq.push_back({slin,scol});
    while(!dq.empty())
    {
        int lin = dq.front().first, col = dq.front().second;
        dq.pop_front();
        if(col==0)
        {
            if(lin>1 && dist[lin-1][l[lin-1]]==INF)
            {
                dist[lin-1][l[lin-1]] = dist[lin][col] + 1;
                dq.push_back({lin-1, l[lin-1]});
            }
        }
        else
        {
            if(dist[lin][col-1]==INF)
            {
                dist[lin][col-1] = dist[lin][col] + 1;
                dq.push_back({lin, col-1});
            }
        }
        if(col==l[lin])
        {
            if(lin<n && dist[lin+1][0]==INF)
            {
                dist[lin+1][0] = dist[lin][col] + 1;
                dq.push_back({lin+1, 0});
            }
        }
        else
        {
            if(dist[lin][col+1]==INF)
            {
                dist[lin][col+1] = dist[lin][col] + 1;
                dq.push_back({lin, col+1});
            }
        }

        if(lin>1 && dist[lin-1][min(col,l[lin-1])]==INF)
        {
            dist[lin-1][min(col,l[lin-1])] = dist[lin][col] + 1;
            dq.push_back({lin-1, min(col,l[lin-1])});
        }
        if(lin<n && dist[lin+1][min(col,l[lin+1])]==INF)
        {
            dist[lin+1][min(col,l[lin+1])] = dist[lin][col] + 1;
            dq.push_back({lin+1, min(col,l[lin+1])});
        }
    }
    return dist[elin][ecol];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>slin>>scol>>elin>>ecol;
    ecol--;
    scol--;
    for(int i=1;i<=n;i++)
        cin>>l[i];
    int brut = solve_brut(), mine = solve();
    //assert(brut <= mine);
    assert(mine - 5 <= brut);
    cout<<brut;
    return 0;
}

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