Submission #660401

#	Time	Username	Problem	Language	Result	Execution time	Memory
660401		NekoRolly	Climbers (RMI18_climbers)	C++17	45 / 100	1099 ms	155780 KiB

climbers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3+4;
const int K = 1e5+1;
const ll inf = 1e18;

struct node{
	int a,b;
	ll w;
};

bool operator<(node a,node b){
	return a.w > b.w;
}

int n1,n,up_l,up_r;
int p[N],a[N*N];
priority_queue<node> d;
vector<int> b;
map<pair<int,int>,ll> dis;

void go(int u,int v,int x,int y,ll w){
	if (min(u, v) < 0 || max(u, v) >= n) return;
	if (a[u] != a[v]) return;
	ll new_w = w + abs(a[u] - a[x]);
	if (!dis.count({u, v}) || dis[{u, v}] > new_w)
		d.push({u, v, dis[{u, v}] = new_w});
}

bool valid(int x,int y){
	if (min(x, y) < 0 || max(x, y) >= n) return 0;
	return a[x] == a[y] && (x != up_l || y != up_r);
}

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

	cin >> n;

	for (; n--; ){ cin >> p[n1++];
		if (n1 >= 2 && p[n1-1] == p[n1-2]) n1--;
		if (n1 >= 3 && p[n1-1] > p[n1-2] && p[n1-2] > p[n1-3])
			p[n1-2] = p[n1-1], n1--;
		if (n1 >= 3 && p[n1-1] < p[n1-2] && p[n1-2] < p[n1-3])
			p[n1-2] = p[n1-1], n1--;
		b.push_back(p[n1-1]);
	}

	// cout << "p[] = "; for (int i=0; i<n1; i++) cout << p[i] << " "; cout << "\n";

	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());

	// cout << "b[] = "; for (int x : b) cout << x << " "; cout << "\n";

	a[0] = 0, n = 1;
	for (int i=1; i<n1; i++){
		if (p[i-1] < p[i]) for (int x : b){
			if (p[i-1] < x && x <= p[i]) a[n++] = x;
		}
		else for (int j=b.size()-1; j>=0; j--)
			if (p[i-1] > b[j] && b[j] >= p[i]) a[n++] = b[j];
	}

	if (b.size() == n1){ ll ans = 0;
		int l = 0,r = n-1; up_l = -1,up_r = -1;
		for (; l != r; ){ 
			if (valid(l+1, r-1)){ ans += abs(a[l+1] - a[l]);
				 up_l = l++, up_r = r--; continue;
			}
			if (valid(l-1, r-1)){ ans += abs(a[l-1] - a[l]);
				 up_l = l--, up_r = r--; continue;
			}
			if (valid(l+1, r+1)){ ans += abs(a[l+1] - a[l]);
				 up_l = l++, up_r = r++; continue;
			}
			if (valid(l-1, r+1)){ ans += abs(a[l-1] - a[l]);
				 up_l = l--, up_r = r++; continue;
			}
		}

		cout << ans << "\n";
		return 0;
	}

	// cout << "a[] = "; for (int i=0; i<n; i++) cout << a[i] << " "; cout << "\n";

	d.push({0, n-1, dis[{0, n-1}] = 0});
	for (; d.size(); ){ auto [x, y, w] = d.top(); d.pop();
		if (x == y){ cout << w << "\n"; return 0;}
		if (dis[{x, y}] != w) continue;
		go(x+1, y+1, x, y, w), go(x-1, y+1, x, y, w);
		go(x+1, y-1, x, y, w), go(x-1, y-1, x, y, w);
	}

	cout << "NO\n";

	return 0;
}

Compilation message (stderr)

climbers.cpp: In function 'int main()':
climbers.cpp:67:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |  if (b.size() == n1){ ll ans = 0;
      |      ~~~~~~~~~^~~~~

• Subtask 1: 10 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 50