akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define NIL (-1)
char ans[1046527][14];
int o=1046527;
int getChar(char i)
{
    switch(i)
    {
        case 'A':return 1;
        case 'C':return 2;
        case 'G':return 3;
        case 'T':return 4;
    }
    /*if(i=='A') return 1;
    else if(i=='C') return 2;
    else if(i=='G') return 3;
    else if(i=='T') return 4;
    else return 0;*/
}
long long getKey(char a[])
{
    long long sum=0,p=1;
    for(long long i=0;i<strlen(a);i++)
    {
        sum+=p*(getChar(a[i]));
        p*=5;
    }
    return sum;
}
int h1(int key) {return key%o;}
int h2(int key) {return 1+(key%(o-1));}
int find(char a[])
{
    long long key=getKey(a),h,i;
    for( i=0;;i++)
    {
        h=(h1(key)+i*h2(key))%o;
        if(strcmp(ans[h],a)==0) return 1;
        else if(strlen(ans[h])==0) return 0;
    }
    return 0;
}
int cs(char a[])
{

    long long key=getKey(a);
    for(long long i=0;;i++)
    {
        long long h=(h1(key)+i*h2(key))%o;
        if(strcmp(ans[h],a)==0) return 1;
        else if(strlen(ans[h])==0)
         {
             strcpy(ans[h],a);return 0;
         }
    }
    return 0;
}
int main()
{
    for(int i=0;i<o;i++) ans[i][0]='\0';
    int n;
    char k[14],l[9];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s %s",l, k);
        if(l[0]=='i') cs(k);
        else
        {
            if(find(k))
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 17420
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
As = []
for n in range(N):
    As.append(int(input()))

first_win = False
for a in As:
    if a % 2 == 1:
        first_win = True
if first_win:
    print("first")
else:
    print("second")


Measured memory_bytes: 9552
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int n; cin >> n;

    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            ans += d[i] * d[j];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int hDisp[] = new int[h];
        int wDisp[] = new int[w];
        char table[][] = new char[h][w];
        
        for(int i=0; i<h; i++){
            hDisp[i] = 0;
        }
        for(int j=0; j<w; j++){
            wDisp[j] = 0;
        }
        
        for(int i=0; i<h; i++){
            String line = sc.next();
            for(int j=0; j<w; j++){
                table[i][j] = line.charAt(j);
                if('.' == table[i][j]){
                    hDisp[i]++;
                    wDisp[j]++;
                }
            }
        }
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(!(hDisp[i] == w || wDisp[j] == h)){
                    System.out.print(table[i][j]);
                }
            }
            if(hDisp[i] != w){
                System.out.println();
            }
        }
    }
}


Measured memory_bytes: 26808
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<ll>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

struct UnionFind {
    vector<int> par; // 親を指すvector,-par[親]は木のサイズ
    UnionFind(int n):par(n, -1) {} // uniteで親を埋め込んでいく必要あり
    int root(int x) { // 親をたどる&データの整理
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    bool unite(int x, int y) { // データの結合
        x = root(x);
        y = root(y);
        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) {return root(x) == root(y);} // 所属判定
    int size(int x) {return -par[root(x)];} // 木のサイズ
}uft(100000);

struct edge{
    int from, to;
    edge(int a=0, int b=0):from(a), to(b) {}
};

// サイズ,辺の情報,初期化の必要あり
vector<edge> es;


int main() {
    ll n, m;
    cin >> n >> m;
    es.resize(m);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        es[i] = edge(a-1, b-1);
    }

    vi ans(m);

    reverse(all(es));
    rep(i, m-1) {
        edge e = es[i];
        ans[i+1] = ans[i];
        if(uft.same(e.from, e.to)) continue;
        ll now = uft.size(e.from);
        now *= uft.size(e.to);
        ans[i+1] += now;
        uft.unite(e.from, e.to);
    }

    reverse(all(ans));

    rep(i, m) {
        cout << n*(n-1)/2 - ans[i] << endl;
    }
}  

Measured memory_bytes: 3328
import sys
n, a, b = map(int, input().split())
x = b - a
if x % 2 == 0:
    print(int(x//2))
else:
    y = a-1
    z = n-b
    w = min(y, z)
    print(int((x+2*w+1)//2))

    




        



Measured memory_bytes: 2940
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>p(n);
  for(int i = 0; i < n; i++){
    cin >> p[i];
  }
  
  int ans = 0;
  int min = n + 1;
  for(int i = 0; i < n; i++){
    if(min >= p[i]){
      ans++;
      min = p[i];
    }
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
	long N;
	cin>>N;
	if(N<1200){
		cout<<"ABC";
	}else if(N<2800){
		cout<<"ARC";
	}else{
		cout<<"AGC";
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int MOD=1e9+7;
ll INF=1e18;

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

int main(){
    string s; cin>>s;
    int n=s.size();

    if(s[0] == '0' || s[n-1] == '1'){
        cout << -1 << endl;
        return 0;
    }

    for(int i=0; i<n-1; i++){
        if(s[i] != s[n-i-2]){
            cout << -1 << endl;
            return 0;
        }
    }

    int num=1, i=0, cur=1;
    while(i<n-1){
        bool first=true;
        while(s[i] == '1' && i<n-1){
            if(!first) cur=num;
            if(first) first=false;
            num++;
            cout << cur << " " << num << endl;
            i++;
        }

        first=true;
        while(s[i] == '0' && i<n-1){
            if(first){
                first=false;
                cur=num;
            }
            num++;
            cout << cur << " " << num << endl;
            i++;
        }
    }
}

Measured memory_bytes: 1664
num = int(input())
a = [int(e) for e in input().split()]
cnt = 0   
cnt2 = 0
while 1:
  cnt = 0
  for i in range(num):
    if a[i]%2 != 0:
      cnt += 1
  if cnt != 0:
    break
  for i in range(num):
    a[i] = int(a[i]/2)
  cnt2 += 1
  
print(cnt2)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(){
	long long int A, B;
	long long int K, div;
	cin >> A >> B >> K;


	div = K;
	for(int i = 0; i < K; i++){
		if(A >= 1){
			if(A >= K){
				A-=K;
				break;
			}else{
				i+=(A-1);
				div-=A;
				A-=A;
			}
		}else if(B >= 1){
			if(B >= div){
				B-=div;
				break;
			}else{
				B-=B;
				break;
			}
		}else{
			break;
		}
	}

	cout << A << " " << B << endl;

	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
      
      int A = sc.nextInt();
      int B = sc.nextInt();
      
      if(A+B==3){
      System.out.println(3);
      }else if(A+B==4){
      System.out.println(2);
      }else{
      System.out.println(1);
      }
    }
}

Measured memory_bytes: 20820
using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

class Program
{
	//Main
	static void Main(string[] args)
	{
		//読み込む
		int N = int.Parse(Console.ReadLine());

		//約数の個数のバケツ
		long[] fn = new long[N+1];
		//1で初期化
		for(int i=0; i<N+1; i++){
			fn[i] = 1;
		}

		//バケツを埋めていく
		for(int i=2; i<N+1; i++){
			for(int j=i; j<N+1; j+=i){
				fn[j] ++;
			}
		}

		//答えを求める
		long ans = 0;
		for(int i=1; i<N+1; i++){
			ans += (long)i*(long)fn[i];
		}

		Console.WriteLine(ans);
	}
}



Measured memory_bytes: 94956
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string a;
long long o = 0;
int main() {
	cin>>a;
	int siz = a.size();
	for(int i = 0; i < siz; i++){
		int b = a[i] - 48;
		o += b;
	}
	if(o % 9 == 0) {
		printf("Yes");
	}
	else{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 3796
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]

idle_max=10**18+1

dist=[idle_max for i in range(N+1)]
dist[1]=0


for loop in range(N-1):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])

value=dist[N]
for loop in range(N):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])
if value!=dist[N]:
    print("inf")
else:
    print(-value)


Measured memory_bytes: 72276
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool f(bool* b, int index) {
	if (index >= 101 || index <= 0) {
		cout << index << endl;
		return true;
	}
	if (!b[index]) {
		cout << index << endl;
		return true;
	}
	return false;
}

int main() {
	int x, n;
	{
		string s;
		getline(cin, s);
		sscanf(s.c_str(), "%d %d", &x, &n);
	}

	bool p[101] = { false };

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

	if (!p[x]) {
		cout << x << endl;
		return 0;
	}

	int index = 1;
	while (true) {
		bool b = f(p, x - index);
		if (!b)
			b = f(p, x + index);
		if (b)
			break;
		index++;
	}

	return 0;
}

Measured memory_bytes: 3296
#include <bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define int long long
using namespace std;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int l) { uniform_int_distribution<int> uid(0, l - 1); return uid(rang); }
int a[20][20];

int d[1 << 20];

int n;

int dp(int mask) {
	if (d[mask] != -1) return d[mask];
	if ((mask & (mask - 1)) == 0) return (d[mask] = 0);
	d[mask] = 0;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			d[mask] += ((mask & (1 << i)) && (mask & (1 << j)) ? a[i][j] : 0);
	for (int i = (mask - 1) & mask; i > 0; i = (i - 1) & mask)
		d[mask] = max(d[mask], dp(i) + dp(mask ^ i));
	return d[mask];
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10); srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];
	memset(d, -1, sizeof(d));
	cout << dp((1 << n) - 1) << "\n";
}

Measured memory_bytes: 8448
import java.util.*;
 
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] s = new String[N];
        int[] t = new int[N];
        for (int i = 0; i < N; i++) {
            s[i] = sc.next();
            t[i] = sc.nextInt();
        }
        String X = sc.next();

        int from = 0;
        for (int i = 0; i < N; i++) {
            if (s[i].equals(X)) {
                from = i+1;
            }
        }

        int ans = 0;
        for (int i = from; i < N; i++) {
            ans += t[i];
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 21972
#include <iostream>
#include <math.h>

using namespace std;

int main(){
	int N;
	cin >> N;
	if(N <= 10)
		cout << N << endl;
	else if(N%10 == 0)
		cout << 10 << endl;
	else{
		int sum = 0;
		int element[5];
		element[0] = N % 10;
		element[1] = (N % 100 - element[0])/10;
		element[2] = (N % 1000 - element[1]*10 - element[0])/100;
		element[3] = (N % 10000 - element[2]*100 - element[1]*10 - element[0])/1000;
		element[4] = (N % 100000 -  element[3]*1000 - element[2]*100 - element[1]*10 - element[0])/10000;
		/*
		for(int i = 1; i < 5; ++i)
			if(N > pow(10,i)){
				if(N%(int)pow(10,i) == 0)
					++sum;
				else
					sum += N%(int)pow(10,i);
			}
		*/
		for(int i = 0; i < 5; ++i){
			if(element[i] < 0)
				element[i] = 0;
			//cout << element[i] << endl;
		}
		
		sum = element[0] + element[1] + element[2] + element[3] + element[4];
		cout << sum << endl;		
	}
	
	return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY[1:]:
    if B[-1] < y:
        bl = B.pop()
        uf.unite(bl, y)
        while B and B[-1] < y:
            uf.unite(bl, B.pop())
        B.append(bl)
    else:
        B.append(y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))


Measured memory_bytes: 70752
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define rlp(i,a,b) for(int i=a;i>b;i--)
#define ft first
#define sd second
#define pii pair<int,int>
#define all(vect) vect.begin(),vect.end()
#define rall(vect) vect.rbegin(),rend() 
const int num = 200001;
typedef long long ll;
int main()
{
	string s,t;
	cin >> s >> t;
	int m = s.size();
	int n = t.size();
	int dp[m+1][n+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(s[i-1] == t[j-1])
				dp[i][j] = dp[i-1][j-1]+1;
			else 
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}	
	}
	string ans="";
	int i = m;
	int j = n;
	while(i>0 && j>0)
	{
		if(dp[i][j-1] == dp[i][j])
			j--;
		else if(dp[i-1][j] == dp[i][j])
			i--;
		else
			ans+=(s[i-1]),j--,i--;
	}
	reverse(ans.begin(),ans.end());
	cout << ans << "\n";




	return 0;
}

Measured memory_bytes: 38736
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#ifndef debug_on
#define debug_on 0
#endif

#define dbg \
    if(debug_on) cerr << "DEBUG:"
#define ast(cond)           \
    do {                    \
        if((cond) == false) \
        {                   \
            if(debug_on)    \
            cerr << "ASSERT" << #cond " failed at line:" << __LINE__ << endl;   \
            exit(1);        \
        }                   \
    }while(0)

vector<uint64_t> A;
vector<uint64_t> XORs;
uint64_t Combine(uint64_t a, uint64_t b)
{
    return (a << 32) | b;
}
int main(int, char *[])
{
    int N;
    cin >> N;
    XORs.push_back(0);
    for(int i = 0; i < N; ++i)
    {
        uint64_t v;
        cin >> v;
        A.push_back(v);
        XORs.push_back(v ^ XORs.back());
    }

    uint64_t num_pat = 0, xsum = 0, sum = 0;
    for(size_t l = 0, r = 0; l < A.size(); )
    {
        while(r < A.size())
        {
            if((xsum ^ A[r]) != (sum + A[r])) break;
            xsum ^= A[r];
            sum += A[r];
            dbg << "r:" << r << " xsum:" << xsum << " sum:" << sum << endl;
            ++r;
        }
        dbg << "L:" << l << " R:" << r << endl;
        xsum ^= A[l];
        sum -= A[l];
        num_pat += r - l;
        dbg << "r:" << r << " xsum:" << xsum << " sum:" << sum << " pat:" << num_pat << endl;
        ++l;
    }
    cout << num_pat << endl;

    return 0;
}


Measured memory_bytes: 3564
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

long long len(long long n) {
    if (n == 0) return 1;
    return 3 + 2 * len(n - 1);
}

long long pati(long long n) {
    if (n == 0) return 1;
    return 1 + 2 * pati(n - 1);
}

long long f(long long n, long long x) {
    if (x <= 0) return 0;
    if (n == 0) return x == 1;
    if (x == 1) return 0;
    if (x == 1 + len(n - 1) + 1 + len(n - 1) + 1) return pati(n);
    if (x == 1 + len(n - 1) + 1) return pati(n - 1) + 1;
    if (x <= 1 + len(n - 1)) return f(n - 1, x - 1);
    if (x <= 1 + len(n - 1) + 1 + len(n - 1)) return pati(n - 1) + 1 + f(n - 1, x - 1 - len(n - 1) - 1);
    return 0;
}

int main() {
    long long n, x;
    cin >> n >> x;
    cout << f(n, x) << endl;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define RG register
#define IL inline
#define LL long long
#define inf 2147483640
#define pi acos(-1.0)
using namespace std;
IL int gi()
{
	RG char ch;RG int s=1,res=0;
	for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
	if(ch=='-') s=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) res=10*res+ch-48;
	return res*s;
}
int h,w,n;
int a[10005]={0},mat[105][105]={0},s[10005]={0};
int main()
{
	//freopen("d.in","r",stdin);
	//freopen("d.out","w",stdout);
	h=gi(),w=gi(),n=gi();
	for(RG int i=1;i<=n;++i) a[i]=gi();
	for(RG int i=1,pos=1;i<=n;++i)
		{
			for(RG int j=pos;j<=pos+a[i]-1;++j)
				s[j]=i;
			pos=pos+a[i];
		}
	for(RG int i=1,pos=1;i<=h;++i)
		{
			if(i&1)
				{
					for(RG int j=1;j<=w;++j)
						mat[i][j]=s[pos],pos+=1;
				}
			else
				{
					for(RG int j=w;j>=1;--j)
						mat[i][j]=s[pos],pos+=1;
				}
		}
	for(RG int i=1;i<=h;++i)
		{
			for(RG int j=1;j<=w;++j)
			printf("%d ",mat[i][j]);
			printf("\n");
		}
	//fclose(stdin);fclose(stdout);
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

long long dp[10][1001];

int main(){
  dp[0][0] = 1;
  for(int k = 0; k <= 100; ++k){
    for(int j = 1000; j >= 0; --j){
      for(int i = 9; i > 0; --i){
	if( (j - k) < 0) break;
	dp[i][j] += dp[i-1][j-k];
      }
    }
  }

 
  int n, s;
  while(scanf("%d%d", &n, &s) && n+s)
    printf("%lld\n", dp[n][s]);

  return 0;
}

Measured memory_bytes: 1260
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1e6 + 4;
const int Mod = 1e9 + 7;
LL f[N][4];

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    f[1][2] = f[1][1] = 1;
    f[1][0] = 8;
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[i - 1][0] * 8 % Mod;
        f[i][1] = (f[i - 1][1] * 9 % Mod + f[i - 1][0]) % Mod;
        f[i][2] = (f[i - 1][2] * 9 % Mod + f[i - 1][0]) % Mod;
        f[i][3] = (f[i - 1][3] * 10 % Mod + (f[i - 1][1] + f[i - 1][2])% Mod) % Mod;        
        // cerr << f[i][0] << ' ' << f[i][1] << ' ' << f[i][2] << ' ' << f[i][3] << endl;
    }



    cout << f[n][3] << endl;
    return 0;
}

Measured memory_bytes: 34844
#![allow(unused_imports)]
#![allow(unused_macros)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;


//
// Macro debug!
//

#[cfg(debug_assertions)]
include!{"./procon/debug.rs"}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}


//
// Macro input!
//

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


//
// IteratorExt
//

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}


//
// Main
//

fn main() {
    input! {
        n: usize,
        xs: [usize; n],
    }

    let count = xs.iter().enumerate().filter(|&(i, &x)| i + 1 != x).count();
    let ans = if (count == 0) || (count == 2) { "YES" } else { "NO" };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b;
    c=a+b;
    if((a%3==0)||(b%3==0)||(c%3==0))
    {
        cout<<"Possible";
    }
    else
    {
        cout<<"Impossible";
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,a[N],b[N],ans[N];
vector<int> v[N];
void dfs(int x) {
	int cnt=0;
	for(int i=0;i<v[x].size();i++) {
		cnt++;
		if(cnt==ans[x]) cnt++;
		ans[v[x][i]]=cnt;
		dfs(v[x][i]);
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		scanf("%d%d",&a[i],&b[i]);
		v[a[i]].push_back(b[i]);
	}
	ans[1]=0;dfs(1);
	int cnt=0;
	for(int i=1;i<=n;i++)
		cnt=max(cnt,ans[i]);
	printf("%d\n",cnt);
	for(int i=1;i<n;i++) {
		printf("%d\n",ans[b[i]]);
	}
	return 0;
}

Measured memory_bytes: 7936
from decimal import *
import math
#exp = Decimal(10**23)
#rint((Decimal(11)*exp)/Decimal(10))

## coding: UTF-8
s = input().split()
t = [int(p) for p in s]
#print(t)

a = t[0]
b = t[1]
x = t[2]
if(a != 0):
    print(b // x - (a-1) // x)
else:
    print(b // x + 1)
'''
n = math.floor(Decimal(b-a+1) / Decimal(x))

p = (b-a+1) % x
if(p > 0):
    l = a % x
    if(l <= p-1):
        n += 1
print(n)
'''

'''
start = a
goal = b
while True:
    if(start % x == 0):
        break
    else:
        start += 1
#print(start)
while True:
    if(goal % x == 0):
        break
    else:
        goal -= 1
#start = Decimal(3)
#goal = Decimal(999999999999999999)

#print(Decimal(goal))
print(Decimal(Decimal(Decimal(goal) - Decimal(start)) / Decimal(x)) + Decimal(1)  ) 
#answer = ((goal - start) / x ) + 1
#print('{}'.format(int(answer)))
'''
'''
#AC code
def count_even(t, x):
    return int( Decimal(t)/ Decimal(x) )

if( a == 0):
    answer = count_even(b, x) + 1
else:
    answer = count_even(b, x) - count_even(a-1, x)
print(answer)
'''

Measured memory_bytes: 5076
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int a,b,c,x,y;cin>>a>>b>>c>>x>>y;
  int ans=1e9;
  rep(i,2*max(x,y)){
    int cnt=2*i*c+max(x-i,0)*a+max(y-i,0)*b;
    ans=min(ans,cnt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
#define pb push_back
#define vi vector<ll>
#define all(_x) _x.begin(), _x.end()
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define lb(_x, _a) (lower_bound(all(_x), _a) - _x.begin())
#define ub(_x, _a) (upper_bound(all(_x), _a) - _x.begin())

int main()
{
  	// ll is int now
    string s; cin>>s;
    if(s[2]==s[3] and s[4]==s[5]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

#define rep(inc, bgn, end) for (int inc = bgn; inc < end; ++inc)
#define repe(inc, bgn, end) for (int inc = bgn; inc <= end; ++inc)

using ll = long long;
using namespace std;

int main() {
    int x;
    cin >> x;
    vector<int> prime(1, 2);
    if (x == 2) {
        cout << x << endl;
        return 0;
    }
    // xまでの素数
    repe(y, 3, x) {
        // printf("%d\n", y);
        rep(i, 0, prime.size()) {
            if (y % prime[i] == 0) {
                break;
            }
            if (i == prime.size() - 1) {
                if (x == y) {
                    cout << x << endl;
                    return 0;
                }
                prime.push_back(y);
            }
        }
    }

    int ans = x + 1;
    while (true) {
        // while (ans < 1000) {
        // printf("%d: ", ans);
        rep(i, 0, prime.size()) {
            // printf(" %d", prime[i]);
            if (ans % prime[i] == 0) {
                break;
            }
            if (i == prime.size() - 1) {
                cout << ans << endl;
                return 0;
            }
        }
        // printf("\n");
        ans++;
    }

    return 0;
}

Measured memory_bytes: 384
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

N,M = map(int,input().split())

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False,overwrite=True).astype(int)

answer = 0
for a,b,c in edge:
  if c != dist[a-1,b-1]:
    answer += 1
print(answer)


Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    string s = "ACL";
    string sns = "";
    for (int i = 0; i < n; i++)
    {
        sns += s;
    }

    cout << sns << endl;

    return 0;
}

Measured memory_bytes: 3524
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
s = input()

tmp = ''
ans = 0
for st in s:
    l = [tmp, st]
    tmp = ''.join(l)
    if(tmp == 'ABC'):
        ans += 1
    if(len(tmp) >= 3):
        tmp = tmp[1:]
print(ans)


Measured memory_bytes: 74736
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long H = sc.nextLong();

        System.out.println(solve(H));
    }

    private static long solve(long H) {
        long sum = 0;
        long count = 1;

        for (; H>0; H/=2) {
            if (H == 1) {
                sum += count;
                continue;
            }

            sum += count;
            count *= 2;
        }

        return sum;
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<stack>
#include<utility>
#include<cassert>
#include <stdlib.h>

using namespace std;

const int MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    string s;
    stack<int> st;
    while (cin >> s) {
        if (s[0] == '+') {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            st.push(b + a);
        } else if (s[0] == '-') {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            st.push(b - a);
        } else if (s[0] == '*') {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            st.push(b * a);
        } else {
            st.push(atoi(s.c_str()));
        }
        if(getchar()=='\n'){
            break;
        }
    }
    cout << st.top() << endl;
}




Measured memory_bytes: 3168
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int count = 0;
		int mid = k / 2;

		for(int i = 0; i < n; i++){
			int x = scanner.nextInt();
			count += Math.min(x, Math.abs(x-k));
		}
		System.out.println(count*2);

	}
}

Measured memory_bytes: 21844
import sys
import math
#from queue import *
import random
#sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline
 
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input()))
def inara():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
################################################################
############ ---- THE ACTUAL CODE STARTS BELOW ---- ############

n=inp()
print("ACL"*n)


Measured memory_bytes: 9388
import sys

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

# Extended GCD
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return(lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv, q

def main():
    a, b = li_input()
    x, y = modinv(a, b)
    print(x, y)


main()



Measured memory_bytes: 5608
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
const int MOD = 1e9+7;
const int MOOD = 998244353;
typedef long long ll;
#define PI 3.14159265359
using namespace std;


int main(){
	ll n;
	cin >> n;
	vector<ll> a(n), diff(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n-1; i++){
		if (a[i] <= a[i+1]) diff[i] = 1;
		else diff[i] = 0;
	}
	ll kabu = 0;
	ll money = 1000;
	for (int i = 0; i < n-1; i++){
		if (diff[i] == 0){
			money += kabu*a[i];
			kabu = 0;
		}else{
			kabu += money/a[i];
			money %= a[i];
		}
	}
	money += kabu*a[n-1];
	cout << money << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>

using namespace std;
#define int long long int
const int N = 1e2 + 4 , M = 200005 , MOD = 1e9 + 7;
int n , k;
int arr[M] , cache[N][M];
int dp(int pos, int val)
{
     if (val > k)
          return 0;
     if (pos == n)
          return val == k;

     int &ans = cache[pos][val];
     if (ans != -1)
          return ans;

     ans = dp(pos, val + 1) + dp(pos + 1, val) - dp(pos + 1, val + arr[pos] + 1) + 2 * MOD;
     ans %= MOD;
     return ans;
}
//int solve(int idx , int candies){
//    if(candies < 0)
//        return 0;
//     if(idx == n){
//        return (candies == 0);
//     }
//     int &ret = mem[idx][candies];
//     if(~ret)
//        return ret;
//    ret = solve(idx , candies -1) + solve(idx + 1 , candies) - solve(idx + 1 , candies - arr[idx] -1 ) + 2 * MOD;
//    ret%= MOD;
//    return ret;
//}
 main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(cache , -1 , sizeof cache);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i){
        cin >> arr[i];
    }
    cout << dp(0 , 0) % MOD;



}


Measured memory_bytes: 168832
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG

int main()
{
    int64_t N, K;
    cin >> N >> K;
    map<int64_t, int64_t> A;
    for (int64_t i = 0; i < N; i++)
    {
        int64_t a, b;
        cin >> a >> b;
        A[a] += b;
    }
    int64_t total = 0;
    for (auto x : A)
    {
        int64_t num = x.second;
        total += num;
        if (total >= K)
        {
            cout << x.first << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 4224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;
typedef pair<int, int> P;
const vector<int> di = {-1, 0, 1, 0};
const vector<int> dj = { 0, 1, 0, -1 };

int main() {

	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a.at(i);
	ll num = 1;
	rep(i, n / 2) {
		num = num * 2 % mod;
	}
	sort(a.begin(), a.end());

	if (n % 2 == 0) {
		bool cheak = true;
		rep(i, n / 2) {
			if (a.at(i * 2) != a.at(i * 2 + 1)) {
				cheak = false;
				break;
			}
		}
		if (cheak == false) {
			cout << 0 << endl;
		}
		else {
			ll ans = num;
			cout << ans << endl;
		}
	}
	else {
		bool cheak = true;
		if (a.at(0) != 0) {
			cheak = false;
		}
		rep(i, n / 2) {
			if (a.at(i * 2 + 1) != a.at(i * 2 + 2)) {
				cheak = false;
				break;
			}
		}
		if (cheak == false) {
			cout << 0 << endl;
		}
		else {
			ll ans = num;
			cout << ans << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
	int a, h, m, s;
	
	scanf("%d", &a);
	
	h = a / 3600;
	a %= 3600;
	m = a / 60;
	s = a % 60;
	
	printf("%d:%d:%d\n", h, m, s);
	
	return(0);
}

Measured memory_bytes: 592
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

int main(void)
{
    int N, K;
    cin >> N >> K;

    vector<int> H(N);
    for (int i = 0; i < N; i++)
        cin >> H[i];

    sort(H.rbegin(), H.rend());

    if (K >= N)
        cout << 0 << endl;
    else {
        long long ans = 0;
        for (int i = K; i < N; i++)
            ans += H[i];

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 1024
import math
lst = list(map(int, input().split()))
lst.sort()
cnt = 0
cnt += lst[2] - lst[1]
x = math.ceil((lst[2] - lst[0] - cnt)/2)
if (lst[2] - lst[0] - cnt)%2 == 1:
  print(cnt + x + 1)
else:
  print(cnt + x)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

ll binary_search(
    ll lo, ll hi, function<bool(ll)> is_ok,
    bool maximize
){
    while(lo < hi){
        if(maximize){
            const ll mid = (lo + hi + 1) / 2;
            if(is_ok(mid)){
                lo = mid;
            }else{
                hi = mid - 1;
            }
        }else{
            ll mid = (lo + hi) / 2;
            if(mid == hi){ mid--; }
            if(is_ok(mid)){
                hi = mid;
            }else{
                lo = mid + 1;
            }
        }
    }
    return lo;
}

ll ceildiv(ll x, ll y){
    if(x >= 0 && y > 0){
        return (x + y - 1) / y;
    }else if(x >= 0 && y < 0){
        return - x / abs(y);
    }else if(x < 0 && y > 0){
        return - abs(x) / y;
    }else{
        assert(x < 0 && y < 0);
        return (abs(x) + abs(y) - 1) / abs(y);
    }
}

ll floordiv(ll x, ll y){
    if(x >= 0 && y > 0){
        return x / y;
    }else if(x >= 0 && y < 0){
        return - (x + abs(y) - 1) / abs(y);
    }else if(x < 0 && y > 0){
        return - (abs(x) + y - 1) / y;
    }else{
        assert(x < 0 && y < 0);
        return abs(x) / abs(y);
    }
}

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    REP(i, n){
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    const ll maxval = ll(1e18) + 1;
    const ll minval = - maxval;

    ll ans = ::binary_search(
        minval, maxval,
        [&](ll x){
            ll count = 0;
            REP(i, n){
                ll tmp = 0;
                if(a.at(i) == 0){
                    if(x > 0){
                        tmp = n - 1 - i;
                    }
                }else if(a.at(i) > 0){
                    const ll y = ceildiv(x, a.at(i));
                    const auto it_start = a.begin() + i + 1;
                    tmp = lower_bound(it_start, a.end(), y) - it_start;
                }else{
                    assert(a.at(i) < 0);
                    const ll y = floordiv(x, a.at(i));
                    const auto it_start = a.begin() + i + 1;
                    tmp = a.end() - upper_bound(it_start, a.end(), y);
                }
                count += tmp;
            }
            return count < k;
        },
        true
    );
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
I = input()
A, B, C, D = int(I[0]), int(I[1]), int(I[2]), int(I[3])
if A + B + C + D == 7:
    print("{}+{}+{}+{}=7".format(A, B, C, D))
elif A + B + C - D == 7:
    print("{}+{}+{}-{}=7".format(A, B, C, D))
elif A + B - C + D == 7:
    print("{}+{}-{}+{}=7".format(A, B, C, D))
elif A + B - C - D == 7:
    print("{}+{}-{}-{}=7".format(A, B, C, D))
elif A - B + C + D == 7:
    print("{}-{}+{}+{}=7".format(A, B, C, D))
elif A - B + C - D == 7:
    print("{}-{}+{}-{}=7".format(A, B, C, D))
elif A - B - C + D == 7:
    print("{}-{}-{}+{}=7".format(A, B, C, D))
elif A - B - C - D == 7:
    print("{}-{}-{}-{}=7".format(A, B, C, D))


Measured memory_bytes: 3064
// C - Energy Drink Collector

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

pair<ll, ll> P[100000];

int main() {
	int N, M;
	cin >> N >> M;

	for (int i=0; i<N; i++) {
		ll A, B;
		cin >> A >> B;
		P[i] = make_pair(A, B);
	}

	sort(P, P+N);

	ll ans = 0;
	ll m = 0;
	for (int i=0; i<N; i++) {
		ll A = P[i].first;
		ll B = P[i].second;
		if (m + B < M) {
			ans += A*B;
			m += B;
		} else {
			while (m < M) {
				ans += A;
				m += 1;
			}
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5208
#include<bits/stdc++.h>

using namespace std;

int main()
{
  while(1)
  {
    int N,A,B,C,X;
    cin>>N>>A>>B>>C>>X;
    if(N == 0 && A == 0 && B == 0 && C == 0 && X == 0){
      break;
    }

    vector<int> n;
    for(int i = 0;i < N;++i){
      int j;
      cin>>j;
      n.push_back(j);
    }

    int flame = 0;

    int check = 0;
    for(int e : n){
      if(check == 0){
        check = 1;
        if(e == X){
          continue;
        }
        else{
          while(1){
            ++flame;
            if(flame > 10000){
              break;
            }

            int x = (A * X + B) % C;
            X = x;

            if(x == e){
              break;
            }
          }
        }
      }
      else{
        while(1){
          ++flame;
          if(flame > 10000){
            break;
          }

          int x = (A * X + B) % C;
          X = x;

          if(x == e){
            break;
          }
        }
      }
    }

    if(flame > 10000){
      cout<<-1<<endl;
    }
    else{
      cout<<flame<<endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,c,d,e,f,g,h;
cin>>a>>b>>c;
if(b-c>=0)
{

cout<<"delicious";
}
else
{
d=abs(b-c);
if(d<=a)
cout<<"safe";
else
cout<<"dangerous";


}



}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

lli cache[N];
lli a[N], n, k;

lli dp(lli idx) {

    if(idx > n)
        return inf;

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

    lli &ans = cache[idx];

    if(ans != -1) {
        return ans;
    }

    for(int i = 1; i <= k; i ++) {
        if(ans == -1) {
            ans = dp(idx + i) + abs(a[idx] - a[idx + i]);
        }
        else
            ans = min(ans, dp(idx + i) + abs(a[idx] - a[idx + i]));
    }
    return ans;

}

void solve()
{

    memset(cache, -1, sizeof cache);
    cin>>n>>k;
    for(int i = 0; i < n; i ++) {
        cin>>a[i];
    }

    lli ans = dp(0);

    cout<<ans;

    cout<<'\n';
    return ;
}

/*
*/

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 6784
#include<iostream>
using namespace std;

main(){
  int a, b, c, cnt;
    while( cin >> a >> b >> c ){
	cnt = 0;
	for ( int i = 1; i <= 10; i++ ){
	    if ( i == a || i == b || i == c ) continue;
	    if ( a + b + i <= 20 ) cnt++;
	}
	cout << (cnt >= 4  ? "YES" : "NO") << endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll a,b;
  cin >>a  >> b;
  cout << b*2-a << endl;

  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define INF 2000000000
#define PI 3.1415926535897932384626
const ll MOD=1e9+7;
vector<int> prime;
bool isPrime[200000];
void init(){
        F(i,0,200000) isPrime[i]=1;
        F(i,2,200000) if(isPrime[i]) for(int j=i*2;j<200000;j+=i) isPrime[j]=0;
        F(i,2,200000) if(isPrime[i]) prime.pb(i);
}
int main(){
        init();
        VgetI(x);
        F(i,0,prime.size()) if(prime[i]>=x){
                printf("%d\n",prime[i]);
                break;
        }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;

int main()
{
    int n;
    int d[100000];
    int i,j;
    int ans=0;
    
    cin >> n;
    for(i=0;i<n;i++){
        cin >> d[i];
    }

    sort(d,d+n);
  
  /*for(i=0;i<n;i++){
        cout << d[i] << endl;
    }*/

    int k=n/2;

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

    ans=d[k]-d[k-1];

   // printf("%d %d\n",d[k],d[k-1]);

    cout << abs(ans) << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> &to, vector<vector<int>> &edge_id, vector<int> &ans, int v, int parent, int parent_color){
//	printf("(v, parent, parent_color) = (%d, %d, %d)\n", v, parent, parent_color);
	int i, c;
	for(i = 0, c = 0; i < to[v].size(); i++){
		if(to[v][i] != parent){
//			printf("to[%d][%d] = %d\n", v, i, to[v][i]);
			if(c == parent_color){
				c++;
			}
//			printf("c = %d\n", c);
			ans[edge_id[v][i]] = c;
			dfs(to, edge_id, ans, to[v][i], v, c);
			c++;
		}
	}
}

int main(){
	int N, a, b, i;
	scanf("%d", &N);
	vector<vector<int>> to(N, vector<int>(0)), edge_id(N, vector<int>(0));
	vector<int> ans(N - 1, -1), count(N, 0);
	for(i = 0; i < N - 1; i++){
		scanf("%d%d", &a, &b);
		a--;
		b--;
		to[a].push_back(b);
		edge_id[a].push_back(i);
		count[a]++;
		to[b].push_back(a);
		edge_id[b].push_back(i);
		count[b]++;
	}
	int K = 0;
	for(i = 0; i < N; i++){
		K = max(K, count[i]);
	}
	dfs(to, edge_id, ans, 0, -1, -1);
	printf("%d\n", K);
	for(i = 0; i < N - 1; i++){
		printf("%d\n", ans[i] + 1);
	}
	return 0;
}

Measured memory_bytes: 12416
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

struct Node{
	int p;
	int l;
	int r;
};
const int MAXN = 1e5+10;
const int NIL = -1;

Node T[MAXN];
int n,D[MAXN];

void print(int u){
	int i,c;
	cout << "node "<<u<<": ";
	cout << "parent = "<< T[u].p<<", ";
	cout << "depth = " << D[u]<<", ";
	
	if(T[u].p==NIL)	cout<<"root, ";
	else if(T[u].l==NIL)	cout<<"leaf, ";
	else	cout<<"internal node, ";
	
	cout << "[";
	
	for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
		if(i)	cout<<", ";
		cout << c;
	}
	cout <<"]"<<endl;
}

int rec(int u, int p){
	D[u] = p;
	if(T[u].r!=NIL)	rec(T[u].r,p);
	if(T[u].l!=NIL)	rec(T[u].l,p+1);
}

int main(){
	int i,j,d,v,c,l,r;
	cin>>n;
	for(i=0;i<n;i++){
		T[i].p = T[i].l = T[i].r=NIL;
	}
	
	for(i=0;i<n;i++){
		cin>>v>>d;
		for(j=0;j<d;j++){
			cin >>c;
			if(j==0)	T[v].l=c;
			else T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}
	for(i=0;i<n;i++){
		if(T[i].p==NIL)	r = i;
	}

	rec(r,0);

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

	return 0;
}




Measured memory_bytes: 7624