Submission #1262230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262230		biank	Text editor (CEOI24_editor)	C++20	100 / 100	78 ms	27720 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
 
#define fst first
#define snd second
 
#define pb push_back
#define eb emplace_back

const ll INF = 1e18;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, s_l, s_c, t_l, t_c;
    cin >> n >> s_l >> s_c >> t_l >> t_c;
    --s_l, --s_c, --t_l, --t_c;
    vi l(n);
    forn(i, n) cin >> l[i];
    vi minFromS(n), minToT(n);
    auto init = [&](vi &mini, int k) {
        forsn(i, k + 1, n) mini[i] = min(mini[i - 1], l[i]);
        dforn(i, k) mini[i] = min(mini[i + 1], l[i]);
    };
    minFromS[s_l] = s_c, minToT[t_l] = l[t_l]; 
    init(minFromS, s_l), init(minToT, t_l);
    ll ans = INF;
    forn(i, n) {
        ll i_c = min(minFromS[i], minToT[i]);
        ans = min(ans, abs(s_l - i) + abs(i - t_l) + abs(t_c - i_c));
    }
    vll cost1(n), cost2(n);
    forn(i, n) {
        cost1[i] = abs(s_l - i) + minFromS[i];
        cost2[i] = abs(t_l - i) + t_c;
    }
    forsn(i, 1, n) {
        cost1[i] = min(cost1[i], abs(s_l - i + 1) + l[i - 1] - minFromS[i - 1] + 1LL);
        cost2[i] = min(cost2[i], 1LL + abs(t_l - i + 1) + abs(minToT[i - 1] - t_c));
    }
    forn(t, 2) {
        ll best = INF;
        forn(i, n) {
            best = min(best, cost1[i] - i);
            ans = min(ans, best + cost2[i] + i);
        }
        swap(cost1, cost2);
    }
    cout << ans << '\n';
    
    return 0;
}

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