Submission #261906

#	Time	Username	Problem	Language	Result	Execution time	Memory
261906		lyc	Climbers (RMI18_climbers)	C++14	0 / 100	122 ms	196520 KiB

climbers

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 5e3+5;
const int inf = 1e9+5;

int N, H[mxN];
int resL[mxN][mxN], resR[mxN][mxN];

inline bool inside(int x, int a, int b) {
	if (a > b) swap(a,b);
	return a <= x && x <= b;
}

int dpR(int i, int j);

int dpL(int i, int j) {
	if (i == j) return 0;
	if (~resL[i][j]) return resL[i][j];
	
	resL[i][j] = inf;
	int cost = 0;
	RFOR(k,j-1,i+1){
		if (inside(H[k],H[i],H[i+1])) {
			cost += abs(H[k] - (k+1 == j ? H[i] : H[k+1]));
			//~ TRACE("L" _ i _ j _ k _ cost);
			resL[i][j] = min(resL[i][j], dpL(i+(H[k]==H[i+1]),k)+cost);
		} else {
			//~ TRACE("L" _ i _ j _ k+1 _ cost);
			resL[i][j] = min(resL[i][j], dpR(i,k+1)+cost);
			break;
		}
	}
	//~ TRACE(i _ j _ resL[i][j]);
	return resL[i][j];
}

int dpR(int i, int j) {
	if (i == j) return 0;
	if (~resR[i][j]) return resR[i][j];
	
	resR[i][j] = inf;
	int cost = 0;
	FOR(k,i+1,j-1){
		if (inside(H[k],H[j],H[j-1])) {
			cost += abs(H[k] - (k-1 == i ? H[j] : H[k-1]));
			//~ TRACE("R" _ i _ j _ k _ cost);
			resR[i][j] = min(resR[i][j], dpR(k,j-(H[k]==H[j-1]))+cost);
		} else {
			//~ TRACE("R" _ i _ j _ k-1 _ cost);
			resR[i][j] = min(resR[i][j], dpL(k-1,j)+cost);
			break;
		}
	}
	//~ TRACE(i _ j _ resR[i][j]);
	return resR[i][j];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N;
    FOR(i,1,N){ cin >> H[i]; }
    
    memset(resL,-1,sizeof resL);
    memset(resR,-1,sizeof resR);
    int ans = min(dpL(1,N), dpR(1,N));
    if (ans == inf) cout << ans << '\n';
    else cout << ans << '\n';
}

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