Submission #1079508

#TimeUsernameProblemLanguageResultExecution timeMemory
1079508huutuanText editor (CEOI24_editor)C++14
45 / 100
4043 ms145276 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N=1e6+10, LG=20; int n, sl, sc, el, ec, a[N], st[LG][N]; int get(int l, int r){ if (l>r) swap(l, r); int lg=__lg(r-l+1); return min(st[lg][l], st[lg][r-(1<<lg)+1]); } int move(int &x, int &y, int z, int t){ if (x+1==z && y==a[x]+1 && t==1){ x=z, y=t; return 1; } if (z+1==x && t==a[z]+1 && y==1){ x=z, y=t; return 1; } int ans=abs(x-z); y=min(get(x, z), y); x=z; if (t==-1) return ans; ans+=abs(y-t); y=t; return ans; } int calc(int x, int y, vector<pair<int, int>> path){ int ans=0; for (auto &i:path){ ans+=move(x, y, i.first, i.second); } return ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> sl >> sc >> el >> ec; for (int i=1; i<=n; ++i) cin >> a[i], st[0][i]=a[i]+1; for (int i=1; i<LG; ++i) for (int j=1; j+(1<<i)-1<=n; ++j) st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]); int tl=sl, tc=sc; int ans=move(tl, tc, el, ec); for (int i=1; i<=n; ++i){ ans=min(ans, calc(sl, sc, {{i, -1}, {el, ec}})); if (i<n) ans=min(ans, calc(sl, sc, {{i, a[i]+1}, {i+1, 1}, {el, ec}})); for (int j=2; j<=n; ++j){ ans=min(ans, calc(sl, sc, {{i, 1}, {j, 1}, {j-1, a[j-1]+1}, {el, ec}})); if (i<n) ans=min(ans, calc(sl, sc, {{i, a[i]+1}, {i+1, 1}, {j, 1}, {j-1, a[j-1]+1}, {el, ec}})); } } cout << ans << '\n'; return 0; }
#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...