제출 #1134420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134420		Nurislam	Text editor (CEOI24_editor)	C++17	56 / 100	866 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

const int inf = 1e10;
void solve(){
	int n;
	cin >> n;
	int s, s2;
	cin >> s >> s2;s--;
	int f, f2;
	cin >> f >> f2;f--;
	
	vector<int> len(n);
	for(int &i:len){cin >> i;i++;}
	
	vector<int> dif;
	dif.pb(s2);dif.pb(f2);
	for(int i:len)dif.pb(i);
	
	sort(all(dif));
	dif.erase(unique(dif.begin(), dif.end()), dif.end());
	
	vector<vector<int>> dp(n,vector<int>(dif.size()+2, inf));
	
	int lw = lower_bound(all(dif), s2)-dif.begin();
	dp[s][lw] = 0;
	int otuvet = lower_bound(all(dif), f2) - dif.begin();
	
	vector<int> line_bnd(n);
	for(int i = 0; i < n; i++){
		line_bnd[i] = lower_bound(all(dif), len[i]) - dif.begin();
	}
	
	priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>> > q;
	q.push({0, s, lw});
	
	int ans = LLONG_MAX;
	
	while(q.size()){
		auto [vale, line, pos] = q.top();
		q.pop();
		//cout << line + 1 << ' ' << dif[pos] << ' ' << vale << '\n';
		if(line == f)chmin(ans, abs(f2 - dif[pos]) + vale);
		// go left
		if(pos - 1 >= 0){
			int df = dif[pos] - dif[pos-1];
			if(chmin(dp[line][pos-1], vale + df))q.push({vale+df, line, pos-1});
		}else if(line-1 >= 0)
			if(chmin(dp[line-1][line_bnd[line-1]], vale+1))q.push({vale+1, line-1, line_bnd[line-1]});
		
		
		// go right
		if(pos + 1 <= line_bnd[line]){
			int df = dif[pos+1] - dif[pos];
			if(chmin(dp[line][pos+1], vale + df))q.push({vale+df, line, pos+1});
		}else if(line + 1 < n)
			if(chmin(dp[line+1][0], vale+1))q.push({vale+1, line+1, 0});
		
		// go up
		if(line -1 >= 0){
			int nextline = line - 1;
			int nextpos = min(line_bnd[nextline], pos);
			if(chmin(dp[nextline][nextpos], vale + 1)) q.push({vale + 1, nextline, nextpos});
		}
		// go down
		if(line + 1 < n){
			int nextline = line + 1;
			int nextpos = min(line_bnd[nextline], pos);
			if(chmin(dp[nextline][nextpos], vale + 1)) q.push({vale + 1, nextline, nextpos});
		}
	}
	chmin(ans, dp[f][otuvet]);
	
	//for(int i = 0; i < n; i++){
		//for(int j = 0; j <= line_bnd[i]; j++)cout << dp[i][j] << ' ';
		//cout << '\n';
	//}
	cout << ans << '\n';
}
/*
 13
 12 6
 1 7
 6 5 3 1 0 1 2 3 4 5 5 5 0
  
 */

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    };
}

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