stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main()

{

    string s;

    vector<char> ch;

    while(cin>>s)

    {

        int len1=s.size();

        for(int i=0;i<len1;i++)

        {

            if(s[i]=='0')

            {

                ch.push_back('0');

            }

            else if(s[i]=='1')

            {

                ch.push_back('1');

            }

            else if(!ch.empty())

            {

                ch.pop_back();

            }

        }

        int len2=ch.size();

        for(int i=0;i<len2;i++)

        {

            cout<<ch[i];

        }

        cout<<endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.342113223726206x):
#include <stdio.h>

#include <string.h>



void hekerman(char x[105]);



int main() {



    char x[105];



    scanf("%s", x);



    hekerman(x);



    return 0;

}



void hekerman(char x[105]) {



    int i, cnt = 0;

    char y[105];

    

    for(i = 0; i < strlen(x); i++) {

        if(x[i] == 'B') {

            cnt--;

        } else {

            y[cnt++] = x[i];

        }



        if(cnt < 0) {

            cnt = 0;

        }

    }



    for(i=0; i<cnt; i++) {

        printf("%c", y[i]);

    }

    printf("\n");



}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#define inl inline

#define re register

#define LL long long

#define MAXN 10100

using namespace std;

struct con

{

	int p;LL sum;

}hh[100100];

LL read()

{

    LL f=1,p=0;

    char c=getchar();

    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

    return f*p;

}

void write(LL x)

{

    if(x<0)putchar('-'),x=-x;

    if(x/10)write(x/10);

    putchar(x%10+'0');

}

LL n,a[100100];

LL l=1000000000l,r,mid,ans,f[100100];

LL sum[100100];

inl LL lowbit(LL x){return x&(-x);}

inl bool cmp(const con&a,const con &b)

{

	if(a.sum==b.sum)return a.p<b.p;

	return a.sum<b.sum;

}

void add(int b){for(int i=b;i<=n;i+=lowbit(i))f[i]++;}

LL find(int a)

{

	LL u=0;

	for(int i=a;i>0;i-=lowbit(i))u+=f[i];

	return u;

}

bool check()

{

	ans=0;

	for(int i=1;i<=n;i++)

	{

		if(a[i]<mid)hh[i].sum=-1;

		else hh[i].sum=1;

	}

	for(int i=1;i<=n;i++)

		hh[i].sum+=hh[i-1].sum;

	for(int i=1;i<=n;i++)hh[i].p=i;

	sort(hh+1,hh+n+1,cmp);

	memset(f,0,sizeof(f));

	for(int i=1;i<=n;i++)

	{

		add(hh[i].p);

		ans+=find(hh[i].p-1);

		if(hh[i].sum>=0)ans++; 

	}

	return 4*ans<n*(n+1);

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

	{

		a[i]=read();

		l=min(l,a[i]);

		r=max(r,a[i]);

	}

	while(l<r)

	{

		mid=(l+r+1)/2;

		if(check()) r=mid-1;

		else l=mid;

	}

	write(l);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 9.257383289923533x):
#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define INF 1000000000;

int a[100005],sum[100005],save[100005];

typedef long long ll;

ll to,to1;

int n;int maxl,minl;

void sortl(int left,int right)

{

    if(left==right)

        return ;

    int mid=(right+left)/2;

    sortl(left,mid);

    sortl(mid+1,right);

    int l=left,l2=mid+1,r=left;

    while(l<=mid&&l2<=right)

    {

        if(sum[l]<sum[l2])

            save[r++]=sum[l++];

        else

        {

            to1+=l-left;

            save[r++]=sum[l2++];

        }

    }

    while(l<=mid)

        save[r++]=sum[l++];

    while(l2<=right)

    {

        to1+=l-left;

        save[r++]=sum[l2++];

    }

    for(int i=left;i<=right;i++)

        sum[i]=save[i];

}

bool ck(int x)

{

    to1=0;

    for(int i=1;i<=n;++i)

        sum[i]=(a[i]<=x?1:-1);

    for(int i=1;i<=n;++i)

        sum[i]+=sum[i-1];

    sortl(0,n);

    return to1>=to/2+1;

}

int main()

{

    maxl=-INF;minl=INF

    scanf("%d",&n);

    to=0;

    for(int i=1;i<=n;++i)

    {

        scanf("%d",&a[i]);

        minl=min(minl,a[i]);

        maxl=max(maxl,a[i]);

        to+=i;

    }

    while(minl<maxl)

    {

        int mid=(minl+maxl)/2;

        if(ck(mid))

            maxl=mid;

        else

            minl=mid+1;

    }

    printf("%d\n",maxl);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

const int mx =1e6;

bool vis[mx];

int n,a[mx],dp[mx];

int solve(int i,int k)

{

    //cout<<"now in "<<a[i]<<endl;

    if(i>=n-1)

        return 0;

   // if(i==n-2)

     //   return abs(a[n-1]-a[n-2]);

    if(vis[i])

        return dp[i];

    int ans=1e9;

    for(int j=1;j<=k;j++)

    {

      if(i+j<n)

        ans=min (ans,abs(a[i]-a[i+j]) + solve(i+j,k));

    }



    vis[i]=1;

    return dp[i]=ans;

}

int main()

{

    memset(dp,0,sizeof dp);

    int k;

    cin>>n>>k;

    for(int i=0;i<n;i++)

        cin>>a[i];

    cout<<solve(0,k)<<endl;

    return 0;



}




// Faster C++ solution for the same problem (measured speedup: 5.08684635972236x):
#include<bits/stdc++.h>

using namespace std;

const int inf=1e9;

int main()

{

int n,i,j,k;

cin>>n>>k;

int a[n],ans[n];

for(i=0;i<n;i++)

    {cin>>a[i];}



memset(ans,127,sizeof ans);

ans[n-1]=0;



for(i=n-2;i>=0;i--)

{

    for(j=i+1;j-i<=k&&j<n;j++)

    {

        ans[i]=min(ans[i],abs(a[i]-a[j])+ans[j]);

    }

}

cout<<ans[0]<<endl;



return 0;}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int k,x,a,b;

	cin>>k>>x;

	if(k>0)

	{

		 a=x-(k-1);

		b=x+(k-1);

	}

	else

	{

		a=x;

		b=x;

	}

	for(int i=a;i<=b;i++)

	{

		if(i!=b)

		cout<<i<<" ";

		else

		cout<<i<<endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.221288494928726x):
///d. one clue

#include <stdio.h>

#include <math.h>



int main()

{

    int k,x;

    scanf("%d %d",&k, &x);



    for(int i=x-k+1;i<=x+k-1;i++){

        printf("%d ",i);

    }

    return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<math.h>

#define maxn 11000

#define oo 0xfffffff

using namespace std;

int father[maxn], n, m;



struct node

{

    int u, v;

    double w;



} s[maxn*100];///数?大小



struct point

{

    int x, y;

} a[maxn];



double Len(int p, int q)

{

    double d = sqrt((a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y));

    return d;

}



int Find(int x)

{

   while(x!=father[x])

     x=father[x];



     return x;

}



int cmp(node p, node q)

{

    return p.w>q.w;

}



double solve()

{

    double ans = 0;



    for(int i=0; i<m; i++)

    {

        int ru = Find(s[i].u);

        int rv = Find(s[i].v);



        if(ru != rv)

        {

            father[ru] = rv;

            ans += s[i].w;

        }



    }



    return ans;

}





int main()

{

    int u, v;



    while(scanf("%d %d",&n, &m)!=EOF)

    {

        double sum = 0;



        for(int i=1; i<=n; i++)

            scanf("%d %d", &a[i].x, &a[i].y);



        for(int i=1; i<=n; i++)

            father[i] = i;



        for(int i=0; i<m; i++)

        {

            scanf("%d %d", &u, &v);

            s[i].u = u;

            s[i].v = v;

            s[i].w = Len(u, v);



            sum += s[i].w;

        }



        sort(s, s+m, cmp);



        double l = solve();



        printf("%.3f\n", sum-l);

    }



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.519704609625553x):
#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

#define N 10000+10

int per[N];

struct Point

{

	double x,y;

}p[N];

struct Edge

{

	int s,e;

	double w;

}a[N*N];

double ma(Point a,Point b)

{

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

bool cmp(Edge a,Edge b)

{

	return a.w>b.w;

}

int Find(int x)

{

	while(x!=per[x])

		x=per[x];

	return x;

}

int Judge(int x,int y)

{

	int fx=Find(x);

	int fy=Find(y);

	if(fx!=fy)

	{

		per[fx]=fy;

		return 1;

	}

	return 0;

}

int main()

{

	int i,n,m,x,y;

	while(~scanf("%d%d",&n,&m))

	{

		for(i=1;i<=n;i++)

		{

			per[i]=i;

			scanf("%lf%lf",&p[i].x,&p[i].y);

		}

		double sum=0;

		for(i=0;i<m;i++)

		{

			scanf("%d%d",&x,&y);

			a[i].s=x;a[i].e=y;

			a[i].w=ma(p[x],p[y]);

			sum+=a[i].w;

		}

		sort(a,a+m,cmp);

		double tmp=0;

		for(i=0;i<m;i++)

		{

			if(Judge(a[i].s,a[i].e))

				tmp+=a[i].w;

		}

		printf("%.3lf\n",sum-tmp);

	}

	return 0;

}
// Slower C++ solution:
/*

 It's better to sleep happy and tired rather than disappointed and frustrated

 There's only 1 thing that's impossible and that is defeating a man who doesn't give up

*/

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pb push_back

#define mx2 102

#define mx3 1003

#define mx4 10004

#define mx5 100005

#define mx6 1000006

#define mod 1000000007

#define PI 3.14159265

#define deb(x) cout << #x << " " << x << endl;

#define fo(i,n) for(int i=0 ; i<n ; i++)

#define Fo(i,k,n) for(int i=k ; i<n ; i++)

 

typedef long long int ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

typedef pair<pair<int,int>,int> piii;



const int inf=0x3f3f3f3f;

int n ,k, ans , sum , a , b ,arr[mx5],dp[mx5];

string str;



int solve(int i)

{

	if(i==n-1)

	{

		return 0;

	}

	if(i>n)

	{

		return inf;

	}

	if(dp[i]!=-1)

	{

		return dp[i];

	}

	int tmp=inf;

	Fo(j,1,k+1)

	{

		if(i+j<n)

			tmp=min(tmp,solve(i+j)+abs(arr[i]-arr[i+j]));

	}

	return dp[i]=tmp;

}

 

int main() {

	ios::sync_with_stdio(false);

	//int t;cin>>t;while(t--)

	{

		cin>>n>>k;

		fo(i,n)cin>>arr[i];

		memset(dp,-1,sizeof(dp));

		cout<<solve(0);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3960407774037489x):
/*

 It's better to sleep happy and tired rather than disappointed and frustrated

 There's only 1 thing that's impossible and that is defeating a man who doesn't give up

*/

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pb push_back

#define mx2 102

#define mx3 1003

#define mx4 10004

#define mx5 100005

#define mx6 1000006

#define mod 1000000007

#define PI 3.14159265

#define deb(x) cout << #x << " " << x << endl;

#define fo(i,n) for(int i=0 ; i<n ; i++)

#define Fo(i,k,n) for(int i=k ; i<n ; i++)

 

typedef long long int ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

typedef pair<pair<int,int>,int> piii;



const int inf=0x3f3f3f3f;

int n ,k, ans , sum , a , b ,arr[mx5],dp[mx5];

string str;



 

int main() {

	ios::sync_with_stdio(false);

	//int t;cin>>t;while(t--)

	{

		cin>>n>>k;

		fo(i,n)cin>>arr[i];

		for(int i=n-2 ; i>=0 ; i--)

		{

			int t=inf;

			Fo(j,1,k+1)

			{

				if(i+j<n)

				{

					t=min(t,dp[i+j]+abs(arr[i]-arr[i+j]));

				}

			}

			dp[i]=t;

		}

		cout<<dp[0];

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define int long long int



int n; //number of stones

int k; //farthest the frog can jump

vector<int> h; //height of the stones

vector<int> dp; //memorize heck



int jump(int stone){

	if(dp[stone]==-1){

		if(stone == n-1){

			return 0;

		}

		else{

			dp[stone] = INT_MAX;

			for(int i=1; i<=k && stone+i<n; i++){

				dp[stone] = min(dp[stone], jump(stone+i) + abs(h[stone]-h[stone+i]));

			}

			return dp[stone];

		}

	}

	else{

		return dp[stone];

	}

}



main(){

	cin >> n >> k;

	

	dp.assign(n, -1);

	for(int i=0; i<n; i++){

		int x;

		cin >> x;

		h.push_back(x);

	}



	cout << jump(0) << "\n";

}

// Faster C++ solution for the same problem (measured speedup: 5.246388069058275x):
#include <stdio.h>

using namespace std;

#define MAX(a,b) (a>b?a:b)

#define MOD(a) (a>0?a:-(a))

#define custoate(i)

int main(){

  int npedras, maxpulo;

  scanf("%d %d",&npedras,&maxpulo);

  int hpedra[npedras],custoate[npedras];

  for (size_t i = 0; i < npedras; i++)

    scanf("%d", &hpedra[i]);

  custoate[0] = 0;

  int tempcost = 2147483647,k,tempcost2;

  for (size_t i = 1; i < npedras; i++,tempcost = 2147483647) {

    // printf("i = %d, tempcost = %d\n", i,tempcost);

    for (k= (maxpulo>i ? i : maxpulo); k > 0; k--) {

      // printf("k = %d ",k);

      tempcost2 = custoate[i-k] + MOD(hpedra[i-k]-hpedra[i]);

      if (tempcost > tempcost2)

        tempcost = tempcost2;

    }

    // printf("custo[%d] = %d",i,tempcost);

    custoate[i] = tempcost;

    // printf("\n\n");

  }

  printf("%d\n", custoate[npedras-1]);



}
// Slower C++ solution:
#include <bits/stdc++.h>                                           

 

//#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define forev(i, b, a) for(int i = (b); i >= (a); --i)

#define forn(i, a, b) for(int i = (a); i <= (b); ++i)

#define all(x) x.begin(), x.end()

#define sz(s) (int)s.size()

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb; 

typedef long long ll;  

typedef double db;                         

 

 

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;

const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);

const int inf = 1e9, N = 2e5 + 48, mod = 1e9 + 7;

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, k, h[N], dp[N];



main () {

	cin >> n >> k;

	forn (i, 1, n)

		cin >> h[i];	

	forn (i, 2, n) {

		dp[i] = inf;

		forn (j, max(1, i - k), i - 1)

			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));				

	}



	cout << dp[n];

} 

// Faster C++ solution for the same problem (measured speedup: 5.214932459827083x):
#include<cstdio>

#include<algorithm>

using namespace std;



#define ll long long 



#define file_io 0



ll i,t,j;

ll n,k,h[100005],dp[100005];



int main(){

	if (file_io){

		freopen(".in","r",stdin);

		freopen(".out","w",stdout);

	}

	

	scanf("%lld%lld",&n,&k);

	

	for (i=1; i<=n; ++i){

		scanf("%lld",&h[i]);

	}

	

	dp[1]=0;

	for (i=2; i<=n; ++i){

		dp[i]=2e9;

		for (t=max(1ll,i-k); t<i; ++t){

			dp[i]=min(dp[t]+abs(h[i]-h[t]),dp[i]);

		}

	}

	

	printf("%lld\n",dp[n]);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



vector<int> vec;

vector<int> dp(100001,-1);



int back(int i,int k){

    for(int j=1;j<=k;j++){

        if(i+j==vec.size()-1) return abs(vec[i+j]-vec[i]);

    }

    // if(i+2==vec.size()-1) return abs(vec[i+2]-vec[i]);

    if(dp[i]!=-1) return dp[i];

    

    int ans=INT_MAX;

    for(int j=1;j<=k;j++){

        if(i+j<vec.size()){

            ans= min(ans, abs(vec[i+j]-vec[i]) + back(i+j,k));

        }

    }



    dp[i]=ans;

    return dp[i];

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n,k;

    cin>>n>>k;

    

    for(int i=0;i<n;i++){

        int a;

        cin>>a;

        vec.push_back(a);

    }

    cout<<back(0,k);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4192941057623196x):
#include <bits/stdc++.h>

using namespace std;



int main() {

    int n,K;    cin>>n>>K;

    int a[n];

    long long dp[n];

    for(int i=0;i<n;i++)        cin>>a[i];

    

    dp[0]=0;

    

    for(int i=1;i<n;i++){

        long long add=1e9;

        for(int k=1;k<=K;k++)if(i-k>=0){

            add=min(add, dp[i-k] + abs(a[i]-a[i-k]));

        }

        dp[i]= add; 

        

    }

    cout<<dp[n-1]<<endl;    

    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

int n,s,spn;

void sp(int ne,int ns,bool* flag)

{

	if (ne > n) return;

	if (ne == n && ns == s) spn++;

    for(int i=0;i<10;++i){

        if(!flag[i]){

            flag[i]=true;

            sp(ne+1,ns+i,flag);

			flag[i] = false;

		}

    }

}



int perm(int n)

{

	return (n ? n * perm(n - 1) : 1);

}



int main()

{

    while(1)

    {

        cin>>n>>s;if(!n)return 0;

        spn=0;

        bool flag[10]={false};

        sp(0,0,flag);

        spn /= perm(n);

        cout<<spn<<endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.316467783925203x):
#include <bits/stdc++.h>



using namespace std;



int ct(int x, int n, int s)

{

	if (x == 10){

		return (s == 0 && n == 0);

	}

	

	return (ct(x + 1, n - 1, s - x) + ct(x + 1, n, s));

}



int main()

{

	int n, s;

	

	while (scanf("%d %d", &n, &s) && n){

		printf("%d\n", ct(0, n, s));

	}

	

	return (0);

}
// Slower C++ solution:
#include <bits/stdc++.h> 

#include <vector>

using namespace std;

int main(){

	int n,k;

	cin>>n>>k;

	vector <int> h(n),dp(n,INT_MAX);

	for(int i=0;i<n;i++) cin>>h[i];

	dp[0]=0;

	for(int i=0;i<n;i++){

		for(int j=1;j<=k;j++){

			if(i+j<n){

			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]));

			}

		}

	}

	cout<<dp[n-1];

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 4.350410534603618x):
#include<cstdio>

#include<algorithm>



int main(){

  int s,k;

  long long st[100001],p[100001];

  scanf("%d%d",&s,&k);

  for(int i=1;i<=s;i++){

    scanf("%lld",&st[i]);

  }

  p[0]=0;

  p[1]=0;

  p[2]=(st[2]-st[1] < 0) ? st[1]-st[2] : st[2]-st[1];

  for(int i=3;i<=s;i++){

    p[i] = 1000000001;

  }

  for(int i=3;i<=s;i++){

    for(int j=1;j<=k;j++){

      if(i-j>=1){

	long long tmp;

	tmp = (st[i]-st[i-j] < 0) ? st[i-j]-st[i] : st[i]-st[i-j];

	if(p[i] > p[i-j]+tmp){

	  p[i] = p[i-j]+tmp;

	}

	if(tmp == 0) break;

      }else{

	break;

      }

    }

  }

  printf("%lld\n",p[s]);

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define int long long

#define ll long long

#define ld long double

#define mod ((ll)1e9+7)

#define maxx ((ll)1e6+5)

#define pb push_back

#define ins insert

#define usefile freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define test ll t; cin>>t; while(t--)

ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}

ll expo(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x%mod)%mod; x=(x*x)%mod; y/=2; } return res;}

/*int sv[1000000]={0};

ll fact[1000007]={0};

void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}

void sve() {sv[0]=1;sv[1]=1;for(int i=2;i*i<=maxx;i++){if(!sv[i]){for(int j=2*i;j<=maxx;j+=i)sv[j]=1;}}}//0 hai to prime

ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expo(fact[r],mod-2)))%mod; res=(res*(expo(fact[n-r],mod-2)))%mod; return res;}

ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expo(fact[n-r],mod-2)))%mod; return res;}*/

int a[3][100003];

using namespace std;

signed main()

{

    int n,k,i,j;

    cin >> n >> k;

    int a[n],d[n] = {0};

    for(i=0 ; i<n ; i++)

    	cin >> a[i];

    for(i=1 ; i<n ; i++)

    {

    	int p = 1e17;

    	for(j=i-1 ; j>=i-k && j>=0 ; j--)

    		p = min(p, d[j]+abs(a[j]-a[i]));

    	d[i] = p;

    }

    cout << d[n-1] <<"\n";

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2247200117209x):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int n,dp[100005],a[100005],k; 

int main(){

	scanf("%d%d",&n,&k);

	for (int i=1;i<=n;i++){

		scanf("%d",&a[i]);

	}

	for (int i=2;i<=n;i++){

		dp[i]=dp[i-1]+abs(a[i]-a[i-1]);

		for (int j=max(1,i-k);j<i;j++){

			dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j])); 

		}

	}

	printf("%d\n",dp[n]);

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cmath>



using namespace std;



int get_head(int a){

    return a / int(pow(10, int(log10(a))));

}



int num( int a, int b, int N){

    int ans = 0;

    for(int i=1; i<=N; i++){

        if(get_head(i) == a && i%10 == b) {

            ans ++;

            i+= 9;

        }

    }

    return ans;

}



int main(){

    int N;

    cin >> N;

    int d[100];

    for(int i=1; i<10; i++){

        for(int j=1; j<10; j++){

            d[i*10 + j] = num(i, j, N);

        }

    }

    long ans = 0;

    for(int i=1; i<10; i++){

        for(int j=1; j<10; j++){

            ans += long(d[i*10 + j]) * long(d[j*10 + i]);

        }

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.4006400045403202x):
#include <iostream>

#include <cmath>



using namespace std;



int get_head(int a){

    return a / int(pow(10, int(log10(a))));

}



int num( int a, int b, int N){

    int ans = 0;

    for(int i=1; i<=N; i++){

        if(get_head(i) == a && i%10 == b) {

            ans ++;

            i+= 9;

        }

    }

    return ans;

}



int main(){

    int N;

    cin >> N;

    int d[100];

    for(int i=1; i<10; i++){

        for(int j=1; j<10; j++){

            d[i*10 + j] = 0;

        }

    }

    for(int i=1; i<=N; i++){

        d[10 * get_head(i) + i%10]++;

    }

    long ans = 0;

    for(int i=1; i<10; i++){

        for(int j=1; j<10; j++){

            ans += long(d[i*10 + j]) * long(d[j*10 + i]);

        }

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define PI 3.1415926535897932384626433832795l

#define MAX_NUM 1000000000

using namespace std;

template <typename T> inline T __lcm(T a,T b)

{

    return (a*b)/__gcd(a,b);

}



ll h[1000000];

ll dp[1000000];

ll n,k;

ll fun(ll i)

{

    if(i>=n)

    {

        return MAX_NUM;

    }

    if(i==n-1)

    {

        return 0;

    }

    if(dp[i]!=-1)

    {

        return dp[i];

    }

    //return dp[i]=min(fabs(h[i]-h[i+1])+fun(i+1),fabs(h[i]-h[i+2])+fun(i+2));

    ll minimum=MAX_NUM;

    for(int j=1;j<=k;j++)

    {

        ll temp=fabs(h[i]-h[i+j])+fun(i+j);

        minimum=min(minimum,temp);

    }

    return dp[i]=minimum;

}



int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++)

    {

        cin>>h[i];

    }

    memset(dp,-1,sizeof(dp[0])*1000000);

    ll ans=fun(0);

    printf("%lld\n",ans);

}


// Faster C++ solution for the same problem (measured speedup: 9.264001924662246x):
#include<bits/stdc++.h>

using namespace std;







int main() {

    ios_base::sync_with_stdio(false);



    long long int a,b,c,d,i,j,k,n,m;

    cin>>n>>k;

    long long int ar[n+1],dp[n+1];

    for(i=0;i<n;i++)

        cin>>ar[i];

     dp[0]=0;

     for(i=1;i<n;i++)

        dp[i]=INT_MAX;

    //dp[1]=abs(ar[1]-ar[0]);

    for(i=0;i<n;i++)

    {

        //a=INT_MAX;

        for(j=1;j<=k && i+j<n;j++)

        {

           c=i+j;

           dp[c]=min(dp[c],(dp[i]+abs(ar[i]-ar[c])));

           //cout<<i<<" "<<c<<" "<<dp[0]<<" "<<dp[c]<<"\n";

        }





    }

    cout<<dp[n-1]<<"\n";

    return 0;

}