제출 #1290044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290044		loom	Text editor (CEOI24_editor)	C++20	100 / 100	100 ms	31740 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

void solve(){
   int n, sx, sy, ex, ey;
   cin>>n>>sx>>sy>>ex>>ey;
   sx--, sy--, ex--, ey--;

   int l[n];
   for(int i = 0; i < n; i++) cin>>l[i];

   int sm[n], em[n];
   sm[sx] = l[sx];
   em[ex] = l[ex];

   for(int i = sx+1; i < n; i++) sm[i] = min(sm[i-1], l[i]);
   for(int i = sx-1; i >= 0; i--) sm[i] = min(sm[i+1], l[i]);
   for(int i = ex+1; i < n; i++) em[i] = min(em[i-1], l[i]);
   for(int i = ex-1; i >= 0; i--) em[i] = min(em[i+1], l[i]);

   auto dis = [&](int x1, int y1, int x2, int y2){
      return abs(x1 - x2) + abs(y2 - min(y1, x1 == sx ? sm[x2] : em[x1]));
   };

   int ans = dis(sx, sy, ex, ey);

   for(int i = 0; i < n; i++){
      ans = min(ans, dis(sx, sy, i, l[i]) + dis(i, l[i], ex, ey));
   }

   int d[n];
   for(int i = 0; i < n; i++){
      d[i] = dis(sx, sy, i, 0);
      
      if(i > 0){
         d[i] = min({d[i], d[i-1] + 1, dis(sx, sy, i-1, l[i-1]) + 1});
      }
   }

   for(int i = n-1; i >= 0; i--){
      if(i+1 < n) d[i] = min(d[i], d[i+1] + 1);

      ans = min(ans, d[i] + dis(i, 0, ex, ey));
   }

   for(int i = 1; i < n; i++){
      ans = min(ans, d[i] + 1 + dis(i-1, l[i-1], ex, ey));
   }

   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   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