akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			int count = 0;
			for (int j = 0; j < n; j++) {
				while (a[j] % 2 == 0) {
					count ++;
					a[j] /= 2;
				}
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 34220
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var a = cin.ArrayLong(n-1);

            var ans = new int[n+1];
            for (int i = 0; i < n-1; i++)
            {
                var aa = a[i];
                ans[a[i]-1]++;
            }

            for (int i = 0; i < n; i++)
            {
                Console.WriteLine(ans[i]);
            }
            
            
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 43728
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn= new Scanner(System.in);
		int l =scn.nextInt();
		int r =scn.nextInt();
		int d = scn.nextInt();
	     int val = l/d;
	     if(l%d!=0){
	    	 val++;
	     }
	     int count=0;
	     while(val*d<=r){
	    	 val++;
	    	 count++;
	     }
		
		System.out.println(count);

	}

}

Measured memory_bytes: 35584
#include<stdio.h>
#include<math.h>
int primality(int x);
int main(void){
    int n,i,x,cnt=0;
    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%d", &x);
        if(primality(x)){
            cnt++;
        }
    }
    printf("%d\n",cnt);

    return 0;
}

int primality(int x){
    int i;
    if(x == 2){
        return 1;
    }
    if(x < 2 || x % 2 == 0){
        return 0;
    }
    i = 3;
    while(i <= sqrt(x)){
        if(x % i == 0){
            return 0;
        }
        i = i + 2;
    }

    return 1;
}


Measured memory_bytes: 2040
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int Max = 30;
const int NIL = -1;
int n, id, r, l, p, root;
struct Node
{
    int parent, right, left;
};
Node T[Max];
int D[Max], H[Max];
void setDepth(int u, int d)
{
    if(u==NIL) return;
    D[u] = d;
    setDepth(T[u].left, d+1);
    setDepth(T[u].right, d+1);
}
int setHeight(int u)
{
    int h1 = 0, h2 = 0;
    if(T[u].left!=NIL)
        h1 = setHeight(T[u].left)+1;
    if(T[u].right!=NIL)
        h2 = setHeight(T[u].right)+1;
    return H[u] = max(h1, h2);
}
int getSibling(int u)
{
    int p = T[u].parent;
    if(p==NIL)
        return NIL;
    if(T[p].left!=u && T[p].left!=NIL)
        return T[p].left;
    else if(T[p].right!=u && T[p].right!=NIL)
        return T[p].right;
    return NIL;
}
void print(int u)
{
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", getSibling(u));
    int deg = 0;
    if(T[u].left!=NIL) deg++;
    if(T[u].right!=NIL) deg++;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);
    if(T[u].parent==NIL)
        printf("root\n");
    else if(T[u].left==NIL && T[u].right==NIL)
        printf("leaf\n");
    else
        printf("internal node\n");
}
int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        T[i].right = T[i].left = T[i].parent = NIL;
    }
    for(int i=0; i<n; i++)
    {
        cin >> id >> l >> r;
        T[id].left = l;
        T[id].right = r;
        if(l!=-1)
        {
            T[l].parent = id;
        }
        if(r!=-1)
        {
            T[r].parent = id;
        }
    }
    for(int i=0; i<n; i++)
    {
        if(T[i].parent==NIL)
        {
            root = i;
            break;
        }
    }
    setDepth(root, 0);
    setHeight(root);
    for(int i=0; i<n; i++)
        print(i);
    return 0;
}



Measured memory_bytes: 3232
#include<iostream>
using namespace std;
int main(){
    int a=0, b=0;
    cin >> a >> b;
    
    if(a>b){
        cout << "a > b" << endl;
    }else if(a<b){
        cout << "a < b" << endl;
    }else{
        cout << "a == b" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
//#define Fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>PII;
typedef vector<PII>Vll;
typedef vector<pair<int,pair<int,int> > >Vlll;
typedef priority_queue<int>PQL;
typedef map<int,int>M;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n
#define pl(n) cout<<n
const int mod=1e9+7;
const int sze=1e4+2;
const int inf = 0x3f3f3f3f;
int dp[sze];
void solve(){
  int n;
  sl(n);
  int a[n+1];
  ms(a,0);
  for(int i=1,k=i;i<=n;k=++i){
	  for(int j=2;j<=(k);j++){
		  while(k%j==0){
			  a[j]++;
			  k=k/j;
		  }
	  }
  }
  int ans=1;
  for(int i=2;i<=n;i++)ans=ans*(a[i]+1)%(mod);
  cout<<ans<<endl;
  
}

signed main(){
   int test=1;
   //sl(test);
   while(test--){
      solve();

   }
  return 0;
}


Measured memory_bytes: 256
#include <utility> // pair make_pair
using std::swap; // c++11
using std::pair;
using std::make_pair;
#include <tuple> // tuple(c++11) make_tuple(c++11)
using std::tuple; // get<address>(variable)
using std::make_tuple;
#include <string> // string stoi(c++11) stoll(c++11) to_string(c++11)
using std::string;
using std::stoi;
using std::stoll;
using std::to_string;
#include <queue> // queue priority_queue
using std::queue;
using std::priority_queue;
#include <stack> // stack
using std::stack;
#include <vector> // vector
using std::vector;
#include <map> // map
using std::map;
#include <set> // set
using std::set; // insert erase find count
#include <algorithm> // min max
using std::sort;
using std::lower_bound; // iterator,  >=
using std::upper_bound; // iterator,  >
using std::min;
using std::max;
using std::min_element; // iterator
using std::max_element; // iterator
#include <complex> // complex
using std::complex; // real imag
#include <iostream> // cin cout
using std::cin;
using std::cout;
using std::endl;
#include <iomanip> // setprecision fixed(manipulator)
using std::setprecision;
using std::fixed;
#include <cmath>
#include <cstdio>

#define lli long long int
#define INF (int)1e09
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define EFOR(i, m, n) for (int i = m; i <= n; i++)
#define RFOR(i, m, n) for (int i = m; i > n; i--)
#define REFOR(i, m, n) for (int i = m; i >= n; i--)
#define VSORT(v) sort((v).begin(), (v).end()) // sort vector
typedef pair<int, int> PI;
typedef tuple<int, int, int> TI;
template <typename T> using Vec = vector<T>; // c++11

int main(void) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a + b > c + d) {
        cout << "Left" << endl;
    } else if (a + b == c + d) {
        cout << "Balanced" << endl;
    } else {
        cout << "Right" << endl;

    }
    return 0;
}


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

bool query(vector<int> vec){
    cout<<"? ";
    for (auto c:vec){
        cout<<c<<" ";
    }
    cout<<endl;
    string s;
    cin>>s;
    return (s[0]=='R');
}

int ans[207],n; //-1 blue 1 red

bool check(vector<int> tmp){
    cout<<"? ";
    for (auto c:tmp){
        cout<<c<<" ";
    }
    cout<<endl;
    string s;
    cin>>s;
    return (s=="Red");
}

int mid_search(int l,int r,int val){
    if (l>=r-1) {return r;}
    int md=(l+r)>>1;
    vector<int> tmp;
    tmp.clear();
    for (int i=1;i<=n;++i){
        tmp.push_back(i+n*(i<=md));
    }
    if (check(tmp)!=val) return mid_search(l,md,val);
    else return mid_search(md,r,val);
}

int main(){
    cin>>n;
    vector<int> tmp;
    tmp.clear();
    for (int i=1;i<=n;++i) tmp.push_back(i);
    int u=check(tmp);
    int k=mid_search(0,n,u);
    int ans[207];
    for (int i=1;i<=2*n;++i){
        if (i<k||i>=n+k){
            vector<int> tmp;
            tmp.clear();
            for (int i=1;i<=n;++i){
                if (i==k) continue;
                tmp.push_back(i+n*(i<=k));
            }
            tmp.push_back(i);
            ans[i]=query(tmp);
        }
        else{
            vector<int> tmp;
            tmp.clear();
            for (int i=1;i<=n;++i){
                if (i==k) continue;
                tmp.push_back(i+n*(i>k));
            }
            tmp.push_back(i);
            ans[i]=query(tmp);
        }
    }
    cout<<"! ";
    for (int i=1;i<=2*n;++i){
        if (ans[i]) cout<<"R";
        else cout<<"B";
    }
    return 0; 
}

Measured memory_bytes: 724
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n,m=map(int,input().split())
h=list(map(int,input().split()))
w=list(map(int,input().split()))
tate=0
yoko=0
p=10**9+7
for i in range(n-1):
    weight=((i+1)*(n-1-i))%p
    tate=(tate+weight*((h[i+1]-h[i])%p))%p
for i in range(m-1):
    weight=((i+1)*(m-1-i))%p
    yoko=(yoko+weight*((w[i+1]-w[i])%p))%p
print((tate*yoko)%p)


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

typedef pair<int, int> P;

int bitCount(int bits) {
    int cnt = 0;
    for (; bits != 0; bits >>= 1) {
        cnt += bits & 1;
    }
    return cnt;
}

int main() {
    int N;
    cin >> N;
    vector<vector<P>> A(N);
    rep(i, N) {
        int a, x, y;
        cin >> a;
        rep(j, a) {
            cin >> x >> y;
            x--;
            A[i].push_back({x, y});
        }
    }

    int ans = 0;
    for (int i = (1 << N) - 1; i > 0; i--) {
//        cout << "------" << i << "------" << endl;
        bool isOk = true;
        rep(j, N) {
            if (i >> j & 1) {
//                cout << "honest:" << j << endl;
                for (int k = 0; k < A[j].size(); k++) {
//                    cout << "(" << A[j][k].first << "," << A[j][k].second << ")" << (i >> A[j][k].first & 1) << ":" << A[j][k].second << endl;
                    if ((i >> A[j][k].first & 1) != A[j][k].second) isOk = false;
                }
            }
        }
        if (isOk) {
            chmax(ans, bitCount(i));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=500010;
int p[N][2],n,ntot;
typedef pair<int,int> pii;
#define mp make_pair
pii a[N];
int front[N],cnt,dfn[N],low[N],in[N],sta[N],top,scc,bl[N],Time,id[N];
struct node{int to,nxt;}e[N<<1];
void Add(int u,int v){e[++cnt]=(node){v,front[u]};front[u]=cnt;}
void Tarjan(int u){
	dfn[u]=low[u]=++Time;in[u]=1;sta[++top]=u;
	for(int i=front[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int v;scc++;
		do{
			v=sta[top--];in[v]=0;
			bl[v]=scc;
		}while(v!=u);
	}
}
void build(int o,int l,int r){
	if(l==r){id[o]=a[l].second;return;}
	int mid=(l+r)>>1;id[o]=++ntot;
	build(o<<1,l,mid);build(o<<1|1,mid+1,r);
	Add(id[o],id[o<<1]);Add(id[o],id[o<<1|1]);
}
void link(int o,int l,int r,int posl,int posr,int u){
	if(posl>posr)return;
	if(posl<=l && r<=posr){Add(u,id[o]);return;}
	int mid=(l+r)>>1;
	if(posl<=mid)link(o<<1,l,mid,posl,posr,u);
	if(mid<posr)link(o<<1|1,mid+1,r,posl,posr,u);
}
bool check(int d){
	memset(front,0,sizeof(front));cnt=0;
	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(bl,0,sizeof(bl));memset(in,0,sizeof(in));scc=Time=top=0;
	ntot=n<<1;build(1,1,n<<1);
	for(int i=1;i<=n;i++)
		for(int j=0;j<2;j++){
			int l=lower_bound(a+1,a+n+n+1,mp(p[i][j]-d+1,0))-a;
			int r=upper_bound(a+1,a+n+n+1,mp(p[i][j]+d-1,n<<1|1))-a-1;
			int m=lower_bound(a+1,a+n+n+1,mp(p[i][j],i+(j^1)*n))-a;
			link(1,1,n<<1,l,m-1,i+j*n);link(1,1,n<<1,m+1,r,i+j*n);
		}
	for(int i=1;i<=ntot;i++)if(!dfn[i])Tarjan(i);
	for(int i=1;i<=n;i++)if(bl[i]==bl[i+n])return false;
	return true;
}
int main(){
	n=gi();
	for(int i=1;i<=n;i++){
		p[i][0]=gi();p[i][1]=gi();
		a[i]=mp(p[i][0],i+n);a[i+n]=mp(p[i][1],i);
	}
	sort(a+1,a+2*n+1);
	int l=0,r=1e9,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){l=mid+1;ans=mid;}
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 26240
a = input().split()
lst = []
N = len(a)

for _ in range(N):
    v = a.pop(0)
    if v.isdigit():
        lst.append(int(v))
       
    else:
        y = int(lst.pop(-1))
        x = int(lst.pop(-1))

        if v == '+':
            lst.append(x + y)
        elif v == '*':
            lst.append(x * y)
        elif v == '-':
            lst.append(x - y)
print(*lst)




Measured memory_bytes: 5596
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

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

double lengths(double x1,double x2,double y1,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main() {
	int n=1,i=0;
	double x[25]={},y[25]={},lengthA[25],lengthB[25],lengthC,S=0,z;
	while(1){
		if(scanf("%lf,%lf\n",&x[i],&y[i])==EOF){
			n--;
			break;
		} 
		i++;
		n++;
	}
	rep(0,n-1){
		lengthA[i] = lengths(x[0],x[i+1],y[0],y[i+1]);
//		printf("%.6f\n",lengthA[i]);
	}
	rep(0,n-2)	lengthB[i] = lengths(x[i+1],x[i+2],y[i+1],y[i+2]);
		
	rep(0,n-2){ //３辺を用いた面積計算
		lengthC = lengthA[i+1];
		z = (lengthA[i]+lengthB[i]+lengthC)/2.0;
		S += sqrt(z*(z-lengthA[i])*(z-lengthB[i])*(z-lengthC));
	}
	printf("%.7f\n",S);
	return 0;
}


Measured memory_bytes: 3208
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	Solver() {
		ios::sync_with_stdio( false );
	}

	void solve() {
		long H, W;
		cin >> H >> W;

		if( H == 1 || W == 1 ) {
			cout << 1 << endl;
		}
		else {
			cout << (H*W+1)/2 << endl;
		}
	}
};

int main() {
	Solver().solve();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

void ok(){
    cout << "Yes" << endl;
    exit(0);
}

void ng(){
    cout <<  "Impossible" << endl;
    exit(0);
}


int n;
int a[1 << 8];

vector<int> loops;

void entangle(int x){
    vector<int> loop;
    for(int i = n-1;i >= 0;i--){
        if((x >> i) % 2 == 0)continue;
        if(loop.empty()){
            loop.push_back(i+1);
            loop.push_back(-i-1);
        }
        else{
            vector<int> tmp;
            tmp.push_back(i+1);
            for(auto it = loop.begin();it != loop.end();it++)tmp.push_back(*it);
            tmp.push_back(i+1);
            tmp.push_back(-i-1);
            for(auto it = loop.rbegin();it != loop.rend();it++)tmp.push_back(*it);
            tmp.push_back(-i-1);
            loop = tmp;
        }
    }
    loop.push_back(INF);
    for(auto elem:loop)loops.push_back(elem);
}

void show(){
    cout << "Possible" << endl;
    vector<P> ps;
    ps.push_back(P(0,0));
    int nowx = 0, nowy = 0;
    for(int x:loops){
        if(x == INF){
            while(nowx > 0){
                ps.push_back(P(--nowx, nowy));
            }
            continue;
        }
        if(x > 0){
            while(nowx > x){
                ps.push_back(P(--nowx, nowy));
            }
            while(nowx < x-1){
                ps.push_back(P(++nowx, nowy));
            }
            ps.push_back(P(nowx,++nowy));
            if(nowx == x)ps.push_back(P(--nowx, nowy));
            else ps.push_back(P(++nowx, nowy));
            ps.push_back(P(nowx,--nowy));
        }
        if(x < 0){
            x = x * -1;
            while(nowx > x){
                ps.push_back(P(--nowx, nowy));
            }
            while(nowx < x-1){
                ps.push_back(P(++nowx, nowy));
            }
            if(nowx == x)ps.push_back(P(--nowx, nowy));
            else ps.push_back(P(++nowx, nowy));
        }
    }
    cout << ps.size() - 1 << endl;
    for(auto p:ps){
        cout << p.first << " " << p.second << endl;
    }
}

int main(){
    cin >> n;
    for(int i = 0;i < (1<<n);i++){
        scanf("%1d", a+i);
        bool bad=false;
        if(a[i] == 0)bad = true;
        for(int j = 0;j < i;j++){
            if((j & i) != j)continue;
            if(a[i] == 1 && a[j] == 0){
                ng();                    
            }
            if(a[j] == 0)bad = false;
        }
        if(bad){
            entangle(i);
        }
    }
    show();
    return 0;
}

Measured memory_bytes: 672
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
int main(){
    ll n,k,ans=0,counta=0,countb=0,countc=0;
    cin >> n >> k;

    if(k%2==1){
        for(ll i=k;i < n+1;i+=k)
        {
            counta++;
        }
        ans=pow(counta,3);
    }else{
        for(ll j=k/2;j < n+1;j+=k/2)
        {
            if(j%k==0)
                countb++;
            else{
                countc++;
            }
        }
        ans= pow(countb,3)+pow(countc,3);
    }

    cout << ans << endl;
    
}
//チームでやったやつ

Measured memory_bytes: 256
#include <stdio.h>
struct Node {
  int parent;
  int left;
  int right;
};
int n;
void Preorder(int);
void Inorder(int);
void Postorder(int);
struct Node tree[30];
int dipth[30],height[30];
int main(){
  int i,id,left,right,root;
  scanf("%d",&n);
  for(i=0;i<n;i++)tree[i].parent=tree[i].left=tree[i].right=-1;
  for(i=0;i<n;i++){
    scanf("%d %d %d",&id,&left,&right);
    tree[id].left=left;
    tree[id].right=right;
    if(left!=-1)tree[left].parent=id;
    if(right!=-1)tree[right].parent=id;
  }
  for(i=0;i<n;i++){
    if(tree[i].parent==-1)root=i;
  }
  printf("Preorder\n");
  Preorder(root);
  printf("\nInorder\n");
  Inorder(root);
  printf("\nPostorder\n");
  Postorder(root);
  printf("\n");
  return 0;
}
void Preorder(int u){
  if(u==-1)return;
  printf(" %d",u);
  Preorder(tree[u].left);
  Preorder(tree[u].right);
}
void Inorder(int u){
  if(u==-1)return;
  Inorder(tree[u].left);
  printf(" %d",u);
  Inorder(tree[u].right);
}
void Postorder(int u){
  if(u==-1)return;
  Postorder(tree[u].left);
  Postorder(tree[u].right);
  printf(" %d",u);
}





Measured memory_bytes: 2104
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,b,n) for(int i=b;i<n;i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int N,M,S;
const int MOD =100000;
ll dp[3010][51];
int main(){
	while(cin>>N>>M>>S,N||M||S){
		memset(dp,0,sizeof(dp));
		dp[0][0] = 1;
		for(int i =1;i <=M;i++){
			for(int j =N*N;j >=1;j--){
				for(int k = 1;k <=S;k++){
					if(k-i>=0){
						dp[k][j]=(dp[k][j]+dp[k-i][j-1])%MOD;
					}
				}
			}
		}
		cout <<dp[S][N*N]<<endl;
	}
	return 0;
}

Measured memory_bytes: 2364
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N=intput()
if N==1:
    print(0)
    exit()
color=[-1]*(N+1)
cost=[-1]*(N+1)
node=[list() for _ in range(N+1)]
for _ in range(N-1):
    u,v,w=mint()
    node[u].append([v,w])
    node[v].append([u,w])
color[1]=0
cost[1]=0
q=deque([1])
while q:
    u=q.popleft()
    for v,w in node[u]:
        if color[v]<0:
            cost[v]=cost[u]+w
            color[v]=cost[v]%2
            q.append(v)
lprint(color[1:])

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int>a(m);
  vector<int>b(m);
  rep(i, m) {
     cin >> a[i] >> b[i];    
  }
  UnionFind tree(n);
  rep(i, m) {
    tree.unite(a[i]-1, b[i]-1);
  }
  int ans=0;
  rep(i, n) {
    if (tree.root(i) == i) ans++;
  }
  cout << ans-1 << endl;
}

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

using namespace std;

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

    int n;
    cin >> n;
    int h[n], dp[n];
    for(int i = 0; i < n; i++) cin >> h[i];
    
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        dp[i] = abs(h[i] - h[i - 1]) + dp[i - 1];
        if(i > 1) dp[i] = min(dp[i], abs(h[i] - h[i - 2]) + dp[i - 2]);
    }

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


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>  //setprecision(桁)
using namespace std;
#define pb push_back
#define ll long long int
#define rep(i,n) for(int i = 0;i < (n);i++)
ll INF = 1000000010; 
const ll MOD = 1000000007;


int main(){ 
    int n,m,ans = 0; cin >> n >> m;
    vector<int> v(n);
    rep(i,n) v[i] = i;
    vector<vector<int>> g(n,vector<int> (n));
    rep(i,m){
        int a, b; cin >> a >> b;
        a--; b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    do{
        bool ok = true;
        if(!v[0]){
            rep(i,n-1){
                if(!g[v[i]][v[i+1]]) ok = false;
            }
        }else continue;
        if(ok) ans++;
    }while(next_permutation(v.begin(),v.end()));

    cout << ans << endl;
} 

Measured memory_bytes: 256
from statistics import median
import itertools
N = int(input())
L = list(map(int, input().split()))
L = list(itertools.combinations(L,3))
c = len(L)
for l in L:
  l = list(l)
  m = max(l)
  if len(set(l)) < 3:
    c -= 1
  elif m >= (median(l) + min(l)):
    c -= 1

print(c)

Measured memory_bytes: 22376
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>

#pragma region _define

#define int LL
#define f(i,a,b) for(LL i=a;i<b;i++)
#define rep(i,n) for(LL i=0;i<n;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n,option) f(i,0,n)cout<<v[i]<<option;
#define all(a) a.begin(),a.end()
#define size(s) ((int)s.size())
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl
#define INT_INF 1<<29
#define LL_INF 1LL<<60
#define MOD 10000007

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vc = vector<char>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using qi = queue<int>;
using qc = queue<char>;
using qs = queue<st>;
using si = stack<LL>;
using sc = stack<char>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using mll = map<LL, LL>;
using vpi = vector<pi>;

#pragma endregion


//素数判定
bool is_prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0) {
			return false;
		}
	}
	return true;
}

void y_n(bool p) {
	if (p)_y();
	else _n();
}

void Y_N(bool p) {
	if (p) _Y();
	else _N();
}

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b)*b);
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		//ret %= 1000000007;
	}
	return ret;
}

#pragma endregion

/************************************************************************/
signed main(void) {
	cin.tie(0); ios::sync_with_stdio(false);

	st s;
	cin >> s;
	int n = size(s);
	int ans = 0;
	for (int bit = 0; bit < (1 << n-1); bit++) {
		int tmp = 0;
		for (int i = 0; i < n ; i++) {
			tmp = tmp * 10 + s[i] - '0';
			if (bit&(1 << i)) {
				ans += tmp;
				tmp = 0;
			}
		}
		ans += tmp;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, mx, ans, b;
int a[maxn];
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		mx = max(mx, a[i]);
	}
	for(int i = 1; i <= n; ++i) {
		int tmp = min(a[i], mx - a[i]);
		if(a[i] == mx) {
			continue;
		}
		if(tmp >= b) {
			b = tmp;
			ans = a[i];
		}
	}
	printf("%d %d\n", mx, ans);
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define maxn 500005
#define int long long
using namespace std;
inline int read()
{
	char x = getchar();
	int lin = 0, f = 1;
	while(x < '0' || x > '9')
	{
		if(x == '-') f = -1;
		x = getchar();
	}
    while(x >= '0' && x <= '9')
	{
		lin = lin * 10 + x - '0';
		x = getchar();
	}
	return lin * f;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
int n,k,s[maxn],pos;
signed main(){
	n = read(); k = read();
	for(int i = 1; i <= n; i++)
		s[i] = read();
	for(int i = 1; i < n; i++)
		if(s[i] + s[i + 1] >= k)
		{
			pos = i;
			break;
		}
	if(!pos)
	{
		printf("Impossible");
		return 0;
	}
	printf("Possible\n");
	for(int i = 1; i < pos; i++)
		printf("%d\n",i);
	for(int i = n - 1; i >= pos; i--)
		printf("%d\n",i);
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const ll INF = 1000000000000000000;
int n;
ll ans, t;

ll f(ll a, ll b)
{
    ll tmp;
    if(a > b)
    {
        tmp = a;
        a = b;
        b = tmp;
    }
    ll c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    cin >> n >> t;
    ans = t;
    for(int i = 1; i < n; i++)
    {
        cin >> t;
        ll r = f(t, ans);
        ans = t * (ans / r);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#define ll long long 
#define ull unsigned long long 
#define ld long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(v) v.begin(),v.end()
#define BP(n) __builtin_popcount(n)
#define bs(v,x) binary_search(all(v),x)
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(j,n) for (j=i+1;j<n;j++)
#define Unique(v) vector<int>::iterator it; sort(all(v)); it= unique(all(v)); v.resize(distance(v.begin(),it))
#define mod 1000000007
#define PI acos(-1.0)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL) 
using namespace std;
void input(vector<ll>& v,ll n){ ll i,io; rep(i,n) { cin>>io; v.pb(io);} }
void output(vector<char> v) { int i; rep(i,v.size()) cout<<v.at(i)<<" "; }
/*map<char,int>  frequency(string v){ ll i; map<char,int> m; rep (i,v.length()) {  if (m.find(v[i])==m.end()) m.insert({v.at(i),1}); else m[v.at(i)]++; } return m; }
bool perfsq(ll n){ return (ceil(sqrt(n))==floor(sqrt(n))); }
bool ispower2(int n) { if (n&(n-1)==0) return true; else return false; }
bool binary_pred(int a,int b){ return a==b; }*/
int main() {
	fastio;
	//freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
	int a,b,c,k,k1 = 0,k2 = 0;
	cin>>a>>b>>c;
	cin>>k;
	while (true) {
		if (b<=a){
			b = b*2;
			k1++;
		}
		else 
			break;
	}
	while (true) {
		if (c<=b){
			c = c*2;
			k2++;
		}
		else 
			break;
	}
	if (k1+k2<=k)
		cout<<"Yes"<<endl;
	else 	
		cout<<"No"<<endl;
}


Measured memory_bytes: 3648
import sys
inout = sys.stdin.readline


def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)


def LCM(a, b):
    return a * b // GCD(a, b)


n, m = map(int, input().split())
a = list(map(int, input().split()))

lcm = 1
for i in a:
    i = i // 2
    lcm = LCM(i, lcm)

for i in a:
    i = i // 2
    if (lcm // i) % 2 == 0:
        print(0)
        sys.exit(0)

ans = ((m // lcm)+1) // 2
print(ans)


Measured memory_bytes: 14948
#include<bits/stdc++.h>
using namespace std;
long long a[100010];
int main()
{
	long long n,ba=1;
	cin>>n;
	for(int t=0;t<n;t++)
	{
		cin>>a[t];
		if(a[t]==0)
		{
			cout<<0;
			return 0;
		}
	}
	for(int t=0;t<n;t++)
	{
		if(ba>1000000000000000000/a[t])
		{
			cout<<"-1";
			return 0;
		}

		ba*=a[t];
	}
	cout<<ba;
	return 0;
}

Measured memory_bytes: 4412
#include <iostream>
#include <algorithm>
#include<stdio.h>
#include<string>
using namespace std;

const int INF = 1 << 28;

int N;
int t[16][17];
int dp[1 << 16];



int main(){
	while (cin >> N && N) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N + 1; j++){
				cin >> t[i][j];
			}

		for (int i = 0; i < (1 << N); i++) dp[i] = INF;
		dp[0] = 0;
		for (int b = 0; b < (1 << N);b++) {
			for (int i = 0; i < N;i++) {

				
				if (b & 1 << i) continue;

				int cost = t[i][0];

				for (int j = 0; j < N; j++){

					if (!(b & 1 << j) && i != j)
						cost = min(cost, t[i][j + 1]);

				}

				int no = b | 1 << i;

				dp[no] = min(dp[no], dp[b] + cost);
			}
		}
		cout << dp[(1 << N) - 1] << endl;
	}
}

Measured memory_bytes: 1416
import collections
n = int(input())
words = []
[words.append(input()) for i in range(n)]
c = collections.Counter(words)
cc = c.most_common()
max_w = []
for i in cc:
  if i[1]==cc[0][1]:
    max_w.append(i[0])
max_w.sort()
[print(j) for j in max_w]

Measured memory_bytes: 48872
import sys

N = int(raw_input())
T = map(int, raw_input().split())
A = map(int, raw_input().split())

ma = [T[0]]
mi = [T[0]]

for i in range(1, N):
    if T[i] != T[i - 1]:
        ma.append(T[i])
        mi.append(T[i])
    else:
        ma.append(T[i])
        mi.append(1)

if mi[N - 1] > A[N - 1] or ma[N - 1] < A[N - 1]:
    print 0
    sys.exit()

ma[N - 1] = min(ma[N - 1], A[N - 1])
mi[N - 1] = max(mi[N - 1], A[N - 1])

for i in range(N - 2, -1, -1):
    if A[i] != A[i + 1]:
        if mi[i] > A[i] or ma[i] < A[i]:
            print 0
            sys.exit()
        ma[i] = min(ma[i], A[i])
        mi[i] = max(mi[i], A[i])
    else:
        ma[i] = min(ma[i], A[i])
        mi[i] = max(mi[i], 1)

cnt = 1
for i in range(N):
    cnt *= (ma[i] - mi[i]) + 1
    cnt %= 10 ** 9 + 7
print cnt

Measured memory_bytes: 15520
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K; cin >> K;
  string S; cin >> S;
  if (S.size()<=K)  cout << S << endl;
  else {
    string R;
    for (int i=0;i<K;i++) {
      R += S.at(i);
    }
    cout << R << "..." << endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef int64_t lint;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;

int main() {
	int N, W;
	cin >> N >> W;
	vector<int> w(N);
	vector<int> v(N);
	rep(i, N) {
		cin >> w.at(i) >> v.at(i);
	}

	int a=1000*100+1, b=0, c=0, x, y, z;
	vector<vector<lint>> dp(N+1, vector<lint>(a));
	rep(i, N+1) fill(all(dp[i]), LINF);
	dp[0][0] = 0;
	rep(i, N) {
		rep(j, a) {
			if (j-v.at(i) >= 0) chmin(dp[i+1][j], dp[i][j-v.at(i)] + w.at(i));
			chmin(dp[i+1][j], dp[i][j]);
		}
	}
	rep(i, a) {
		if (dp[N][i] <= W) b = i;
	}
	cout << b << '\n';
}


Measured memory_bytes: 83228
#include <iostream>

using namespace std;

int main()
{
    int H_1, M_1;
    int H_2, M_2;
    int K;

    cin >> H_1 >> M_1 >> H_2 >> M_2 >> K;

    int delta_H = H_2 - H_1;
    int delta_M = M_2 - M_1;

    int delta_T = (delta_H * 60) + delta_M;
    int start = delta_T - K;
    cout << start;

    return 0;
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC126
{
    class E
    {
        static void Main(string[] args)
        {
            List<int> list = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
            int N = list[0], M = list[1];
            UnionFind uf = new UnionFind(N);
            for(int i = 0; i < M; i++)
            {
                int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
                uf.Unite(a[0]-1, a[1]-1);
            }

            SortedSet<int> boss = new SortedSet<int>();
            for(int i = 0; i < N; i++)
            {
                boss.Add(uf.Root(i));
            }
            int r = boss.Count;

            Console.WriteLine(r);
        }

    }

    class UnionFind
    {
        private int N;
        public int[] parents; //親の番号を格納. 親の場合は-(メンバサイズ)

        public UnionFind(int n)
        {
            parents = new int[n];
            for (int i = 0; i < n; i++) parents[i] = -1;
            N = n;
        }

        //グループのボスを取得
        public int Root(int x)
        {
            if (parents[x] < 0) return x;
            parents[x] = Root(parents[x]); //次からはボスに直結するように構造を変える
            return parents[x];
        }

        //グループのメンバ数
        public int Size(int x)
        {
            int r = Root(x);
            return -parents[r];
        }

        public bool Unite(int x, int y)
        {
            x = Root(x);
            y = Root(y);
            if (x == y) return false;
            //メンバサイズが大きい方をボスとして合併
            if (Size(x) < Size(y))
            {
                parents[y] += parents[x];
                parents[x] = y;
            }
            else
            {
                parents[x] += parents[y];
                parents[y] = x;
            }
            return true;
        }
    }

}




Measured memory_bytes: 18096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  
  int cnt = 0;
  int inc = 0;
  int dec = 0;
  for(int i=0; i<N; i++){
    if(i == N-1){
      cnt++;
      break;
    }
    if(vec.at(i) < vec.at(i+1)){
      dec++;
      if(inc > 0){
        inc = 0;
        dec = 0;
        cnt++;
      }
    }
    if(vec.at(i) > vec.at(i+1)){
      inc++;
      if(dec > 0){
        dec = 0;
        inc = 0;
        cnt++;
      }
    }
  }  
  cout << cnt << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> h(N + 200, 0);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &h[i]);
  }

  vector<ll> dp(N + 200, INF);
  dp[0] = 0;
  for (int i = 0; i < N; ++i)
  {
    for (int j = 1; j <= K; ++j)
    {
      dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
    }
  }
  cout << dp[N - 1] << endl;

  return 0;
}


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

#define println(msg) cout << msg << endl
#define yes_or_no(flag) if (flag) { println("Yes"); } else { println("No"); }

int main() {
  // 入力
  int N;
  cin >> N;
  
  vector<int> L(N);
  for (int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  
  // 計算
  int count = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        if (i == j || j == k || k == i) continue; // 同じ辺は選べない
        if (i > j || j > k) continue; // 重複カウントを防ぐ
        
        if (L[i] != L[j] && L[j] != L[k] && L[k] != L[i]) {
          vector<int> v = { L[i], L[j], L[k] };
          sort(v.begin(), v.end());
          if ((v.at(0) + v.at(1)) > v.at(2)) {
            count++;
          }
        }
      }
    }
  }
  
  // 出力
  println(count);
}

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

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

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

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  sort(all(s));
  if (s[0] == s[1] and s[2] == s[3] and s[1] != s[2]) cout << "Yes\n";
  else cout << "No\n";
  return (0);
}

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

using namespace std;

typedef long long ll;

#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define bit(n) (1<<(n))

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

int main(){
	int n, k;
	double au = 0; // ぶんし
	double ad = 0; // ぶんぼ

	cin >> n >> k;

	repp(i, n) {
		int u = 0;
		int d = 1;
		int ct = i;

		if (i > k) {
			au += (n - i + 1) * ad;
			break;
		}
		while (ct < k) {
			ct *= 2;
			d *= 2;
		}
		if (i == 1) ad = d;

		au += ad / d;

		cerr << "d:" << d << " u:" << ad / d << " ad:" << ad << endl;
	}

	cerr << au << " " << ad << endl;

	// cout << au / (3.0 * ad) << endl;
	printf("%.16f\n", au / (n * ad));

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P =pair<int,int>;

int main(){
    int n;
    cin >> n;
    vector <int> a(n);
    vector <vector <int>> x(n, vector <int> (n));
    vector <vector <int>> y(n, vector <int> (n));
    vector <int> syou(n,0);
    vector <int> nise;
    int k;
    k=0;
    int ans,m;
    ans=0;
    

    rep(i,n){
        cin >> a[i];
        rep(j,a[i]){
            cin >> x[i][j] >> y[i][j];
            
        }
    }

    rep(i,pow(2,n)){
        k=0;
        m=0;
        rep(j,n){
            syou[j]=-1;
        }
        rep(j,n){
            if((i>>j)&1==1){
                syou[j]=1;
              }
            }
              
              
        rep(j,n){  
                
                if(syou[j]==1){
                    ++m;
                    rep(l,a[j]){
                            if (y[j][l]==0){
                                if (syou[x[j][l]-1]==1){
                                    k=1;
                                
                                    break;
                             }
                                else{
                                    syou[x[j][l]-1]=-1;
                             }
                             }
                            else{
                            
                                if (syou[x[j][l]-1]==-1 or syou[x[j][l]-1]==0){
                                    k=3;
                                
                                    break;
                                     }
                                 else{
                                    syou[x[j][l]-1]==1;
                                        }
                                }
                            }
                }
            }

            
        
        if(k==0 and m>ans){
            
            
           
                ans=m;
            }
    }

    
    cout << ans << endl;
    
    

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define LF '\n'
#define ALL(x) x.begin(), x.end()
#define iostreamBooster() { cin.tie(nullptr); ios_base::sync_with_stdio(false); }
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
template<class Itr> void dump(Itr begin, Itr end) { for (;begin != end; ++begin) clog << *begin << LF; }

signed main()
{
  priority_queue< int , vector<int>, greater<int> > pq;
  int cnt[128] {};
  string s;

  cin >> s;

  for (char c : s) {
    ++cnt[c];
  }

  for (char i = 'a'; i <= 'z'; ++i) {
    if (cnt[i] > 0) pq.push(cnt[i]);
  }

  int ans = 0;
  if (pq.size() <= 1) pq.push(0);

  while(pq.size() > 1) {
    int l = pq.top(); pq.pop();
    int r = pq.top(); pq.pop();

    ans += l+r;
    pq.push(l+r);
  }

  cout << ans << LF;

  return 0;
}




Measured memory_bytes: 3300
import math
n, k = map(int, input().split())  # 複数数値入力
ans = 0
num = int(math.log2(k)+1)    # 目が1の時に連続して表にならなくてはいけない数

for i in range(1, n+1):
    if i>=k:
        ans += 1
    else:
    #  print(max(math.ceil(math.log2(k/i)), 1))
        ans += 1/(2 ** max(math.ceil(math.log2(k/i)), 1) )

print(ans/n)

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


int main(){
  long long int D, N;
  cin >> D >> N;
  long long int ans = 1;
  for(int ii=0; ii<D; ii++){
    ans *= 100;
  }
  if(N==100){
    ans *= (N+1);
  }else{
    ans *= N;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=100002;
int top,i,st[N],l;
char s[N];
int main(){
	scanf("%s",s),l=strlen(s);
	for (i=0;i<l;i++){
		if (top && s[i]!=st[top]) top--;
		else st[++top]=s[i];
	}
	printf("%d",l-top);
}

Measured memory_bytes: 768
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    println(problem067a(a, b))
}

fun problem067a(a: Int, b: Int): String {
    return if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) "Possible" else "Impossible"
}

Measured memory_bytes: 31268
K = int(input())


xs = [str(x) for x in range(1,10)]

def get_lunlun(xs):
    ret = []
    for x in xs:
        last = x[-1]
        if last ==  "0":
            ret.append(x+"0")
            ret.append(x+"1")
        elif last == "9":
            ret.append(x+"8")
            ret.append(x+"9")
        else:
            ret.append(x+ str(int(last)-1))
            ret.append(x+ str(int(last)))
            ret.append(x+ str(int(last)+1))
    return ret

while K > len(xs):
    K = K -  len(xs)
    xs = get_lunlun(xs)
print(xs[K-1])
    


Measured memory_bytes: 15636