Submission #1079484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079484		huutuan	Text editor (CEOI24_editor)	C++14	5 / 100	77 ms	20968 KiB

Main

#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;
   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;
   ++n;
   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){
      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;
}

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