oj.uz

Submission #660388

# Submission time Handle Problem Language Result Execution time Memory
660388 2022-11-21T18:28:23 Z NekoRolly Climbers (RMI18_climbers) C++17
45 / 100
 800 ms 166124 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 116 ms 16484 KB Output is correct
3 Execution timed out 1102 ms 155584 KB Time limit exceeded
4 Execution timed out 1102 ms 160456 KB Time limit exceeded
5 Execution timed out 1096 ms 166124 KB Time limit exceeded

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 9 ms 1620 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 40 ms 4192 KB Output is correct

Subtask #3
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 17 ms 2516 KB Output is correct
3 Execution timed out 1096 ms 67976 KB Time limit exceeded
4 Execution timed out 1087 ms 90828 KB Time limit exceeded
5 Execution timed out 1099 ms 111964 KB Time limit exceeded
6 Execution timed out 1090 ms 74692 KB Time limit exceeded
7 Execution timed out 1091 ms 90356 KB Time limit exceeded
8 Execution timed out 1091 ms 110208 KB Time limit exceeded
9 Execution timed out 1089 ms 92604 KB Time limit exceeded
10 Execution timed out 1090 ms 86900 KB Time limit exceeded