Submission #6893436


Source Code Expand

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define rep(i, a) for (int i=0; i<(a); i++) 
#define ub        upper_bound            // first element >  val(itr)
#define lb        lower_bound            // first element >= val(itr)

#define mp make_pair
#define pb push_back
#define pi 3.141592653589793
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define bitcount(a) __builtin_popcount(a) // count set bits
#define all(x) (x).begin(),(x).end()

const ll MOD = 1e9 + 7;
const int inf = 1e9+9;
const long long INF = 1e18+3;

//to debug 
#define dbg(x) cout << "Line " << __LINE__ << " | " #x ": " << (x) << endl

template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template<typename T> T fast_power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

inline ll mod(ll x,ll n) {if (x < n) return x; if (x >= n) return x - n;}
string IntToString(ll a){ ostringstream temp; temp << a; return temp.str();}
ll findMMI_fermat(ll n,ll M) {ll ans= fast_power(n,M-2,M);return ans;}//i.e In (a/b)%M..it calculates MMI of b wrt M
ll add(ll a,ll b,ll M)  { return ( mod(a,M ) + mod(b,M ))%M;     }
ll sub(ll a, ll b,ll M) { return (mod(a,M ) + M - mod(b,M ))%M;   }
ll mult(ll a,ll b,ll M) { return  ( mod(a,M)*mod(b,M) ) %M ; }
bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 

  
               /* -------------------------------Main Code------------------------------- */



int main(){
	FAST;
	int n;cin>>n;
	vector <int> hgt(n);
	for(int i=0;i<n;i++) cin>>hgt[i];
	vector <int> dp(n); //where dp[i] represents min cost of frog reaching from beginning to i'th
	//Base cases
	dp[0] = hgt[0];
	dp[1] = abs(hgt[1] - dp[0]);
	dp[2] = 	min( abs(hgt[2] - hgt[2-2]) , abs(hgt[2] - hgt[2-1]) + dp[1]);
	
	//Rec Cases
	for(int i=3;i<n;i++){
		dp[i] = min(  abs(hgt[i] - hgt[i-2]) + dp[i-2 ], abs(hgt[i] - hgt[i-1]) + dp[i-1] );
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

	

Submission Info

Submission Time
Task A - Frog 1
User ritik_patel05
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2340 Byte
Status
Exec Time 9 ms
Memory 1024 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 8 ms 1024 KB
1_03 9 ms 1024 KB
1_04 9 ms 1024 KB
1_05 9 ms 1024 KB
1_06 9 ms 1024 KB
1_07 9 ms 1024 KB