Submission #1064577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064577		Dan4Life	Text editor (CEOI24_editor)	C++17	19 / 100	524 ms	56764 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using ar4 = array<int,4>;
const int INF = (int)2e9;
const int mxN = (int)1e6+10;
vi v, dis[mxN];
int n, m, xs, ys, xd, yd, nx, ny, L[mxN];
priority_queue<ar3,vector<ar3>,greater<ar3>> pq;

void relax(int x, int y, int w){
	if(dis[nx][ny] > dis[x][y]+w){
		dis[nx][ny] = dis[x][y]+w;
		pq.push({dis[nx][ny],nx,ny});
	}
}

void conv(int &x){ x = lower_bound(all(v),x)-begin(v); }

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> xs >> ys >> xd >> yd;
	L[n+1]=1; v.pb(1); v.pb(ys), v.pb(yd);
	for(int i = 1; i <= n; i++){
		cin >> L[i], L[i]++, v.pb(L[i]);
	}
	for(int i = 1; i <= n+1; i++){
		for(int k = 1; k <= 1000; k++){
			if(L[i]>k) v.pb(L[i]-k);
			v.pb(L[i]+k);
		}
	}
	sort(all(v)); v.erase(unique(all(v)), end(v));
	int m = sz(v);
	for(int i = 0; i <= n+1; i++)
		dis[i].clear(), dis[i].resize(m+1,INF);
	conv(ys); conv(yd); 
	for(int i = 1; i <= n+1; i++) conv(L[i]);
	pq.push({0,xs,ys}); dis[xs][ys]=0;
	while(sz(pq)){
		auto [D,x,y] = pq.top(); pq.pop();
		if(D!=dis[x][y]) continue;
		if(x==xd and y==yd){ cout << D << "\n"; return 0; }
		if(x){
			// go up
			nx = x, ny = y;
			nx--, ny=min(ny,L[nx]), relax(x,y,1);
			// go left
			nx = x, ny = y;
			if(!ny) nx--, ny = L[nx], relax(x,y,1);
		}
		
		if(x!=n+1){ 
			// go down
			nx = x, ny = y;
			nx++, ny=min(ny,L[nx]), relax(x,y,1);
			
			
			// go right
			nx = x, ny = y;
			if(ny==L[nx]) nx++, ny = 0, relax(x,y,1);
		}
		nx = x, ny = y;
		if(y) ny--, relax(x,y,abs(v[ny]-v[y]));
		
		nx = x, ny = y;
		if(ny<L[nx]) ny++, relax(x,y,abs(v[ny]-v[y]));
	}
}

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