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

#include<cstring>

#include<iostream> 

#include<cmath>

#include<algorithm>

#include<stdlib.h>

using namespace std;



int main()

{

	string ans;

	string ppp;

	int n;

	cin>>n;

	cin>>ppp;

	

	if(ppp.length()>n)

	{

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

		{

			ans=ans+ppp[i];

		}

		ans.append(3,'.');

	}

	else

	{

		ans.assign(ppp);

	}

	cout<<ans<<endl;

return 0;

 }

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

#include <string.h>

int main(){

	int k;

	scanf("%d",&k);

	char s[100];

	scanf("%s",&s);

	int lol = strlen(s);

	s[k] = '\0';

	for(int i=0;s[i]!='\0';i++){

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

	}

	if(k<lol){

		printf("...");

	}

return 0;

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

using namespace std;

int main(){

	int n,k;cin>>n>>k;int ans=0;

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

		int a;cin>>a;if(a>=k)ans++;

	}

	cout<<ans<<endl;

}

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

int main()

{

	int a,n,k,h[100000],cnt=0;

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

	for(a=0;a<n;a++){

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

		if(h[a]>=k){

			cnt++;

		}

	}

	printf("%d",cnt);

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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

typedef bitset<20> MASK;

#define ll long long

#define PI 3.14159265359

//#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll a[17][17];

ll cost[1 << 17];

vector<vector<ll>> masks;

ll n;

ll dp[1 << 17];

ll OO = 1e15;

ll solve(MASK mask){

    if(mask.count() == n)

        return 0;



    ll &ret = dp[mask.to_ulong()];

    if(ret != -1)

        return ret;



    ret = -OO;

    for(int i = 0; i < masks[mask.to_ulong()].size(); i++){

        ll c = cost[masks[mask.to_ulong()][i]];

        MASK new_mask = mask.to_ulong() | masks[mask.to_ulong()][i];



        ret = max(ret, solve(new_mask) + c);

    }



    return ret;

}



int main(){

    cin.tie(0);

    cin.sync_with_stdio(0);



    clr(dp, -1);

    cin>>n;

    masks = vector<vector<ll>> (1 << (n + 1));

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

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

            cin>>a[i][j];



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

        MASK mask = i;

        ll ccost = 0;

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

            if(!mask[k]) continue;

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

                if(mask[j])

                    ccost+= a[k][j];

            }

        }



        cost[i] = ccost;

    }



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

        MASK mask = i;

        mask.flip();

        int maskCopy = mask.to_ulong() & ((1 << n) - 1);



        for(int sub = maskCopy; sub > 0; sub = (sub - 1) & maskCopy){

            masks[i].push_back(sub);

        }

    }



    cout<<solve(0);

}


// Faster C++ solution for the same problem (measured speedup: 1.376568939867994x):
// Author : Mohamed Sameh

#include <bits/stdc++.h>

typedef long long ll ;

#define pb push_back

#define f first

#define s second

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

#define rall(v) v.rbegin(),v.rend()

#define SZ(a) (int)a.size()

#define Flush fflush(stdout);

using namespace std ;

const int N = 16;

const ll MN = -1e9*N;

int n;

int a[N][N];

ll dp[(1<<N)];

ll value[(1<<N)];

int arr[N];

ll solve(int msk = (1<<n)-1)

{

  if (!msk)return 0;

  ll &ret = dp[msk];

  if (~ret)return ret;

  ret = MN;

  for (int cur_msk = msk; cur_msk; cur_msk=(cur_msk-1)&msk)

  {

    ret = max(ret, value[cur_msk] + solve(msk^cur_msk));

  }

  return ret;

}

ll get_cost(int sz)

{

  ll ret = 0;

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

    for (int j = i+1; j < sz; j++)

      ret += a[arr[i]][arr[j]];

  return ret;

}

int main()

{

  scanf("%d", &n);

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

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

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

  memset(dp, -1, sizeof dp);

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

  {

    int idx = 0;

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

    {

      if (i & (1<<j))arr[idx++] = j;

    }

    value[i] = get_cost(idx);

  }

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

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

#define lowbit(x) x&-x

using namespace std;



typedef long long ll;

static const int inf = 0x7fffffff;

static const int N = 1e5 + 10;

int n, a[N], cnt[N*10], pre[N*10];



void add (int x)

{

	for (int i = x; i <= N << 1; i += lowbit(i))

		++cnt[i];

}



ll query (int x)

{

	ll sum = 0;

	for (int i = x; i > 0; i -= lowbit(i))

		sum += cnt[i];

	return sum;

}



bool check (int x)

{

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

		cnt[i] = 0;

	pre[0] = 0;

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

		pre[i] = pre[i-1] + (a[i] >= x ? 1 : -1);

	ll sum = 0;

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

	{

		sum += query(pre[i] + N);

		add(pre[i]+N);

	}

	return sum >= 1ll * n * (n + 1) >> 2;

}



int main ()

{

	cin >> n;

	int l = 0, r = 0;

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

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

	int ans = 0;

	while (l <= r)

	{

		int mid = (l + r) >> 1;

		if (check(mid))

			l = mid + 1;

		else

			r = mid - 1;

	}

	cout << r;

	return 0;

}

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

//CLOCKS_PER_SEC

#define se second

#define fi first

#define ll long long

#define Pii pair<int,int>

#define Pli pair<ll,int>

#define ull unsigned long long

#define pb push_back

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

const int N=1e5+10;

const int INF=0x3f3f3f3f;

const int mod=1e9+7;

using namespace std;

int n,val[N<<1];

int a[N],b[N];

int sum[N];

void add(int x){

	while(x<N*2){

		val[x]+=1;

		x+=x&-x;

	}

}

ll get(int x){

	ll ans=0;

	while(x>0){

		ans+=val[x];x-=x&-x;

	}

	return ans;

}

bool check(int x){

	for(int i=1;i<=n;++i)sum[i]=sum[i-1]+(a[i]>=x?1:-1);

	ll tot=0;

	memset(val,0,sizeof(val));

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

		tot+=get(sum[i]+N);

		add(sum[i]+N);

	}

	return tot>=1LL*n*(n+1)/4;

}

int main(){

	scanf("%d",&n);

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

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

	}

	sort(b+1,b+1+n);

	int l=1,r=n;

	int ans=1;

	while(l<=r){

		int mid=(l+r)>>1;

		if(check(b[mid])){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	cout<<b[ans]<<endl;

	return 0;

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

using namespace std;

#define ll long long

#define ld long double





int main()

{

    ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

    ll cord,koita;

    cin >> koita >> cord; /// 3 7

    ll start = cord - koita + 1; /// 5

    for (int i=start; i<cord; i++){

        cout << i << " "; /// 5 6

    }

    cout << cord << " "; // 7

    ll en = cord + koita - 1; /// 9

    for (int i= cord + 1; i<=en; i++){

        cout << i << " ";

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.30033656194942x):
////sfef

#include<stdio.h>

int main(){



int k,x,i,p,q,r;

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

p=(x-(k-1));

q=(x+(k-2));

r=(x+(k-1));

if(k==1)

{

    printf("%d",x);

}

else{

    for(i=p;i<=q;i++)    

    {

        printf("%d ",i);

    }

    printf("%d",r);

}



return 0;

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

using namespace std;

string a;

int b[15],q;

int main()

{

    cin>>a;

    for(int i=0;i<a.size();i++)

    {

        if(a[i]=='0'){q++;b[q]=0;} 

        if(a[i]=='1'){q++;b[q]=1;}

        if(a[i]=='B'&&q>=1)q--;

    }    

    for(int i=1;i<=q;i++)cout<<b[i];

    cout<<endl;

    return 0;

}

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

#include<cstring>

using namespace std;

char s[20], S[20];

int main()

{

	scanf("%s", s);

	int len = strlen(s);

	int cnt = 0;

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

	{

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

		{

			S[cnt] = '1';

			cnt++;

		}

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

		{

			S[cnt] = '0';

			cnt++;

		}

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

		{

			if(cnt)cnt--;

			S[cnt] = '\0';

		}

	}

	printf("%s\n", S);

	return 0;

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

using namespace std;

#define MAX 100000

const int dx[8]={1,0,-1,0,1,-1,-1,1};

const int dy[8]={0,1,0,-1,1,1,-1,-1};



int main(){

    int s;

    cin>>s;

    int k[1000000]={};

    k[s]++;

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

        if(s%2==0){

            s/=2;

        }else{

            s=3*s+1;

        }

        k[s]++;

        if(k[s]==2){

            cout<<i<<endl;

            break;

        }

    }



    return 0;

}


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

using namespace std;

#define MAX 100000

const int dx[8]={1,0,-1,0,1,-1,-1,1};

const int dy[8]={0,1,0,-1,1,1,-1,-1};



int main(){

    int s;

    cin>>s;

    bool k[1000000]={};

    k[s]=1;

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

        if(s%2==0){

            s/=2;

        }else{

            s=3*s+1;

        }

        if(k[s]){

            cout<<i<<endl;

            break;

        }else{

            k[s]=1;

        }

    }



    return 0;

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



using namespace std;



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

typedef long long ll;



int main()

{

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

    ll k,x;

    cin >> k >> x;

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

    {

        cout << i << " ";

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.215014674069083x):
///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<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

char a[10000005];

int b[10000005],l;

int main()

{

	scanf("%s",a);

	int x=strlen(a);

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

	{

		if(a[i]=='0')b[++l]=0;

		else if(a[i]=='1')b[++l]=1;

		else if((a[i]=='B')&&(l))l--;

	}

	for(int i=1;i<=l;i++)printf("%d",b[i]);

	printf("\n");

	return 0;

}

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

#include <cstring>

using namespace std;

char s[10005],ans[10005];

int top=0;

int main(){

    scanf("%s",s);

    for(int i=0;i<strlen(s);i++)

        if(s[i]!='B'){

            top++;

            ans[top]=s[i];

        } else if(top>0) top--;

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

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

    return 0;

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

#include<cstdio>

#include<string>

using namespace std;



int main(){

	string s;

	int k;

	cin>>k>>s;

	if(s.size()<=k) cout<<s;

	else{

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

			cout<<s[i];

		}

		cout<<"...";

	}

	return 0;

} 

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

#include<string.h>



int main()

{

	int n;

	scanf("%d",&n);

	char str[102];

	scanf("%s",&str);

	int len=strlen(str);

	if(len>n)

	{

		str[n]='.';

		str[n+1]='.';

		str[n+2]='.';

		str[n+3]='\0';

	}

	printf("%s",str);

	return 0;

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

using namespace std;

#define INF 1000000000

int dp(int i);

int n,k;

int h[100009],memo[100009];



int main(){

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

  cin>>n>>k;

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

  cout<<dp(0)<<endl;

  return(0);

}



int dp(int i){

  int rec=INF;

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

  if(i==n-1)return 0;

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

    if(i+j<n)rec=min(rec,dp(i+j)+abs(h[i]-h[i+j]));

  }

  return memo[i]=rec;

}


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

using namespace std;

#define INF 1000000000

int dp[100009];



int main(){

  int n,k;

  int h[100009];

  cin>>n>>k;

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

    cin>>h[i];

    dp[i]=INF;

  }

  dp[0]=0;

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

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

      if(i-j>=0){

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

      }

    }

  }

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

  return(0);

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

#include <cmath>

#include <cstring>



using namespace std;



int pedras[100100];

long long dp[100100]; ///Guardo os valores da funcao frog;



int n,k;

const int inf = 1e9;



int frog2(int i,int j){



    if(dp[i] != -1){

        return dp[i];

    }



    int menor = inf;



    if(i>=j) return dp[i]=0;



    for(int x=1;x<=k;x++){ ///i=0; i=1;i=2;i=3;

        if(i+x <= j){      ///x=1, x=1;x=1;x=1;

            long long cost = (frog2(i+x,j)+ abs(pedras[i]-pedras[i+x]));



            if(cost < menor){

                menor = cost;

            }

        }

    }



    return dp[i] = menor;

}



int main(){



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



    cin >>n>>k;



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

        cin >> pedras[i];

    }



    cout<<frog2(0,n-1)<<endl;

}


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

#include <algorithm>

#include <cmath>

#include <cstring>



using namespace std;



int pedras[100100];

int dp[100100]; ///Guardo os valores da funcao frog;



int n,k;

const int inf =1000000/*1e9*/;



int main(){



    memset(dp,inf,sizeof(dp));

    cin >>n>>k;



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

        cin >> pedras[i];

    }



    ///Comeca aki a bagaca

    dp[n-1]=0;



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



        ///int menor=inf;



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

            if(i+j<=n-1){

                int cost = abs(pedras[i]-pedras[i+j]);

                dp[i]=min(dp[i],dp[i+j]+cost);

                /*menor = min(menor,dp[i+j]+cost);*/

            }

        }



        ///dp[i]=menor;

    }



    cout<<dp[0];



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

#include <algorithm>

using namespace std;

double arr[1000000];

int main(){

    int a,b,c,i,n;

    cin>>n>>a;

    cout<<a-n+1;

    for(i = 1;i < 2*n-1;i++){

        cout<<' '<<a-n+i+1;

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.212966275831585x):
////sfef

#include<stdio.h>

int main(){



int k,x,i,p,q,r;

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

p=(x-(k-1));

q=(x+(k-2));

r=(x+(k-1));

if(k==1)

{

    printf("%d",x);

}

else{

    for(i=p;i<=q;i++)    

    {

        printf("%d ",i);

    }

    printf("%d",r);

}



return 0;

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

using namespace std;



int main () {

  int n,k;

  cin>>n>>k;

  int a[n];

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

    cin>>a[i];

  }

  int dp[100101];

  long long p=100000000000;

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

    dp[i]=p;

  }

  dp[0]=0;

  if (n==2) {

    cout<<abs(a[1]-a[0])<<endl;

  }

  else {

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

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

        if (dp[i+j]>dp[i]+abs(a[i]-a[i+j])) {

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

        }

      }

    }

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

  }

}

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

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

using namespace std;

typedef long long ll;

int main() {

  int n,k;cin>>n>>k;

  

  vector<int> vec(n);

  

  rep(i,n) cin>>vec[i];

  

  vector<ll> dp(n+k+10);

  rep(i,n+k)dp[i]=100000000000;

  dp[0]=0;dp[1]=abs(vec[1]-vec[0]);

  

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

    

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

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

    }

    

  }

  

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

  

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

#include<numeric>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<climits>

#define fi first

#define se second

#define pb push_back

#define pii pair<int,int>

#define ll long long

#define pll pair<ll,ll>

#define rep(i,from,to) for(int i=from;i<to;i++)

#define repd(i,from,till) for(int i=from;i>=till;i--)

#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define inf 1000000001

#define mod 1e9+7

#define inf1 1e18+1

#define pie 3.14159265358979323846

#define N 100005



using namespace std;



int n,k;

ll a[100002];

ll dp[100002];



int rec(int i){

	if(i+k>=n)return abs(a[i]-a[n-1]);

	if(dp[i]!=inf)return dp[i];

	rep(j,0,k){

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

	}

	return dp[i];

}



int solve(){

	rep(i,0,100002)dp[i]=inf;

    cin>>n>>k;

	rep(i,0,n)cin>>a[i];

	cout<<rec(0)<<endl;

	return 0;

}

int main(){

    waste;

    int t;

    //cin>>t;

    t=1;

    while(t--){

       	solve();

    }

}


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

#include<vector>

#include<algorithm>

#define inf 1000000009

using namespace std;

int main(){

	int n,k;

	cin>>n>>k;

	vector<int> dp(n,inf);

	vector<int> a(n);

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

		cin>>a[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(a[i]-a[i+j]));

			}

		}

	}

	cout<<dp[n-1];

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

using namespace std;



#define INF 0x3f3f3f3f

#define ii pair<int,int >

#define MAXN 100005



int memo[MAXN], a[MAXN];

int n, k;



int f(int idx){



	if(idx == n) return 0;

	if(memo[idx] != -1) return memo[idx];

	int ans = INF;

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

		if(idx+i <= n) ans = min(f(idx+i) + abs(a[idx] - a[idx+i]), ans);

	}

	return memo[idx] = ans;

}



int main(){



	while(cin >> n >> k){

		//cout << n << endl;

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

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

		cout << f(1) << endl;

	}	



	return 0;

}

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

using namespace std;



#define ll long long

#define ii pair<int,int>

#define INF 1e9 + 7

#define vi vector<int>

#define add emplace_back





int main(){ios_base::sync_with_stdio(false);

    

    int n, k;

    cin >> n >> k;

    vi a(n);

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

    

    vi dp(n, INF);

    dp[0] = 0;

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

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

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

        }

    }

    

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



    return 0;

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

#include<cstring>

#include<cstdio>

using namespace std;

char s[105],ans[105];

int main()

{

	cin>>s;

	int len=strlen(s),tot=0;

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

	{

		if(s[i]=='0')	ans[++tot]='0';

		if(s[i]=='B'&&tot>0)	tot--;

		if(s[i]=='1')	ans[++tot]='1';

	}

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

	{

		cout<<ans[i];

	}

	return 0;

}

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

#include<string.h>



int main(){

	char str[15];

	scanf("%s",&str);

	char temp[15];

	int index=0,len=strlen(str);

	for(int i=0;str[i] != '\0';i++){

		if(str[i]=='0'){

			temp[index] = '0';

			//printf("index[%d] : %s\n",index,temp);

			index++;

		} 

		else if(str[i]=='1'){	

			temp[index] = '1';

			//printf("index[%d] : %s\n",index,temp);

			index++;

		} 				//01B0 temp =     --0

		else if(str[i]=='B'){

			//printf("index[%d] : %s\n",index,temp);

			if(index != 0) index--;

		}

	}

	//printf("%d\n",index);

	temp[index]='\0';

	printf("%s\n",&temp);

	

	

	

	return 0;

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

#define int long long int

#define pb push_back

#define inf 1e9

#define pp pop_back

#define pii pair<int,int>

#define vec vector<int>

#define mp make_pair

using namespace std;

int h[100001],dp[100001];

int ans(int n,int k)

{

  if(n==1)

    return 0;

  if(dp[n]!=-1)

    return dp[n];

  int res=inf;

  for(int i=1;i<=min(k,n-1);i++)

    res=min(res,abs(h[n]-h[n-i])+ans(n-i,k));

  return dp[n]=res;

}

int32_t main()

{

  ios_base::sync_with_stdio(false);

  cin.tie(NULL);

  cout.tie(NULL);

  int t=1;

  //cin>>t;

  while(t--)

  {

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

    int n,k;

    cin>>n>>k;

    int i;

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

        cin>>h[i];

    cout<<ans(n,k);

  }

}


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

#define int long long int

#define pb push_back

#define inf 1e9

#define pp pop_back

#define pii pair<int,int>

#define vec vector<int>

#define mp make_pair

using namespace std;

int32_t main()

{

  ios_base::sync_with_stdio(false);

  cin.tie(NULL);

  cout.tie(NULL);

  int t=1;

  //cin>>t;

  while(t--)

  {

    int n,k;

    cin>>n>>k;

    int i,h[n+1];

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

        cin>>h[i];

    int dp[n+1]={0};

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

    {

      int res=inf;

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

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

      dp[i]=res;

    }

    cout<<dp[n];

  }

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

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <algorithm>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <list>

#include <iterator>

#include <assert.h>

#pragma warning(disable:4996) 



typedef long long ll;

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

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

#define LINF 9223300000000000000

#define INF 2140000000

const long long MOD = 1000000007;

using namespace std;





ll a[16][16];



int main(int argc, char* argv[])

{

    int n;

    scanf("%d", &n);



    int i,j;

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

        for(j=0; j<n; j++) {

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

        }

    }



    vector<ll> dp(1<<n);

    int k;

    for(k=0; k<(1<<n); k++) {

        vector<int> z;

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

            if(k & (1<<i)) z.push_back(i); 

        }

        int siz=(int)z.size();



        dp[k]=0;

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

            for(j=i+1; j<siz; j++) {

                dp[k] += a[z[i]][z[j]];

            }

        }



        ll max=0;

        for(i=0; i<(1<<siz); i++) {

            int tmp0=0;

            for(j=0; j<siz; j++) {

                if(i & (1<<j)) tmp0 |= (1<<z[j]);

            }

            ll val = dp[tmp0]+dp[k^tmp0];

            max = MAX(max, val);

        }

        dp[k] = max;

    }

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



    return 0;

}


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

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <algorithm>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <list>

#include <iterator>

#include <assert.h>

#pragma warning(disable:4996) 



typedef long long ll;

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

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

#define LINF 9223300000000000000

#define INF 2140000000

const long long MOD = 1000000007;

using namespace std;





ll a[16][16];

ll dp[1<<16];



int main(int argc, char* argv[])

{

    int n;

    scanf("%d", &n);



    int i,j;

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

        for(j=0; j<n; j++) {

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

        }

    }



    int mm=(1<<n);

    int z[17];

    int k;

    for(k=0; k<mm; k++) {

        int siz=0;

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

            if(k & (1<<i)) z[siz++]=i;

        }



        dp[k]=0;

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

            for(j=i+1; j<siz; j++) {

                dp[k] += a[z[i]][z[j]];

            }

        }

    }



    for(k=0; k<mm; k++) {

        int siz=0;

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

            if(k & (1<<i)) z[siz++]=i;

        }

        ll max=0;

        int MM=(1<<siz);

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

            int tmp0=0;

            for(j=0; j<siz; j++) {

                if(i & (1<<j)) tmp0 |= (1<<z[j]);

            }

            ll val = dp[tmp0]+dp[k^tmp0];

            max = MAX(max, val);

        }

        dp[k] = max;

    }

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



    return 0;

}