제출 #1025974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025974		model_code	Text editor (CEOI24_editor)	C++17	0 / 100	0 ms	348 KiB

Main

// Author: Tymofii Reizin
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

ll calcNo1(vector<ll>& l, int sl, int sc, int el, int ec)
{
    ll minMid = sc;
    for (int i = min(sl, el); i <= max(sl, el); ++i)
        minMid = min(minMid, l[i]);
    ll minim = minMid;
    ll res = 1e18;
    if (sc <= minMid)
        res = abs(ec - sc) + abs(sl - el);
    for (int i = sl - 1; i >= 0; --i)
    {
        minim = min(minim, minMid);
        if (l[i] > minim)
            continue;
        res = min(res, abs(ec - l[i]) + abs(i - sl) + abs(i - el));
    }
    minim = minMid;
    for (int i = sl + 1; i < (int)l.size(); ++i)
    {
        minim = min(minim, minMid);
        if (l[i] > minim)
            continue;
        res = min(res, abs(ec - l[i]) + abs(i - sl) + abs(i - el));
    }
    return res;
}

ll calcYes1(vector<ll>& l, int sl, int sc, int el, int ec)
{
    //find for each row start min dist from start
    vector<ll> d1(l.size(), 1e18);
    ll minim = sc;
    d1[sl] = sc;
    for (int i = sl; i >= 0; --i)
    {
        minim = min(minim, l[i]);
        if (minim == sc)
            d1[i + 1] = min(d1[i + 1], abs(l[i] - sc) + 1 + abs(i - sl));
        if (l[i] > minim)
            continue;
        d1[i] = min(d1[i], abs(i - sl) + l[i]);
        d1[i + 1] = min(d1[i + 1], 1ll + abs(i - sl));
    }
    minim = sc;
    for (int i = sl + 1; i < (int)l.size(); ++i)
    {
        minim = min(minim, l[i]);
        if (minim == sc && i + 1 < (int)l.size())
            d1[i + 1] = min(d1[i + 1], abs(l[i] - sc) + 1 + abs(i - sl));
        if (l[i] > minim)
            continue;
        d1[i] = min(d1[i], abs(i - sl) + l[i]);
        if (i + 1 < (int)l.size())
            d1[i + 1] = min(d1[i + 1], 1ll + abs(i - sl));
    }
    for (int i = 1; i < (int)l.size(); ++i)
        d1[i] = min(d1[i], d1[i - 1] + 1);
    for (int i = (int)l.size() - 2; i >= 0; --i)
        d1[i] = min(d1[i], d1[i + 1] + 1);
    //find min dist to finish for each row start
    ll res = d1[el] + ec;
    minim = l[el];
    for (int i = el - 1; i >= 0; --i)
    {
        minim = min(minim, l[i]);
        if (l[i] > minim)
            continue;
        res = min(res, d1[i + 1] + 1 + abs(el - i) + abs(ec - l[i]));
    }
    minim = l[el];
    for (int i = el; i + 1 < (int)l.size(); ++i)
    {
        minim = min(minim, l[i]);
        if (l[i] > minim)
            continue;
        res = min(res, d1[i + 1] + 1 + abs(el - i) + abs(ec - l[i]));
    }
    return res;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    int sl, sc, el, ec;
    cin >> sl >> sc >> el >> ec;
    --sl;
    --sc;
    --el;
    --ec;
    vector<ll> l(n);
    for (ll &i : l)
        cin >> i;
    cout << calcNo1(l, sl, sc, el, ec) << "\n";
    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