Submission #660388

#	Time	Username	Problem	Language	Result	Execution time	Memory
660388		NekoRolly	Climbers (RMI18_climbers)	C++17	45 / 100	1102 ms	166124 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;
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});
}

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];
	}

	// 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;
}

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