oj.uz

Submission #261906

# Submission time Handle Problem Language Result Execution time Memory
261906 2020-08-12T07:37:46 Z lyc Climbers (RMI18_climbers) C++14
0 / 100
 122 ms 196520 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 196472 KB Output isn't correct
2 Incorrect 108 ms 196472 KB Output isn't correct
3 Incorrect 120 ms 196472 KB Output isn't correct
4 Incorrect 104 ms 196472 KB Output isn't correct
5 Incorrect 113 ms 196520 KB Output isn't correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 196472 KB Output isn't correct
2 Incorrect 112 ms 196472 KB Output isn't correct
3 Incorrect 109 ms 196348 KB Output isn't correct
4 Incorrect 107 ms 196356 KB Output isn't correct
5 Incorrect 106 ms 196472 KB Output isn't correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 196472 KB Output isn't correct
2 Incorrect 108 ms 196472 KB Output isn't correct
3 Incorrect 107 ms 196472 KB Output isn't correct
4 Incorrect 122 ms 196472 KB Output isn't correct
5 Incorrect 121 ms 196472 KB Output isn't correct
6 Incorrect 108 ms 196472 KB Output isn't correct
7 Incorrect 112 ms 196448 KB Output isn't correct
8 Incorrect 108 ms 196472 KB Output isn't correct
9 Incorrect 110 ms 196472 KB Output isn't correct
10 Incorrect 108 ms 196472 KB Output isn't correct