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

public class Main {
	public static void main(String[] args) {
		Main main = new Main();

		Scanner sc = new Scanner(System.in);
		main.solve(sc);
		sc.close();
	}

	void solve(Scanner sc) {
		int s = sc.nextInt();
		int i = 1;
		Set<Integer> existed = new HashSet<>();

		while (true) {
			if (existed.contains(s)) {
				break;
			}
			existed.add(s);
			if (s % 2 == 0) {
				s = s / 2;
			} else {
				s = s * 3 + 1;
			}
			i++;
		}
		System.out.println(i);
	}
}


Measured memory_bytes: 25300
//Abhinav ---IIIT_A
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vpii vector<pair<int,int>> 
ld pie=3.141592653589793238462643383279;
int mod=1e9+7;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};


int dig(int a){
  int r=0;
  while(a!=0){
    int xp=a%10;
    a/=10; if(xp==1) ++r;
  }
  return r;
}

int fact[2000005];
int infact[2000005];

int inv(int a){
  int y=mod-2;
  int r=1;
  while(y!=0){
    if(y&1){
      r*=a; r%=mod;
    }
    y/=2; a*=a; a%=mod;
  }
  return r;
}

int po(int a,int y){
  int r=1;
  while(y!=0){
    if(y&1){
      r*=a; r%=mod;
    }
    y/=2; a*=a; a%=mod;
  }
  return r; 
}

void facto(){
  fact[0]=1;
  f(i,1,2000005) {fact[i]=i*fact[i-1]; fact[i]%=mod;}
  f(i,0,2000005) infact[i]=inv(fact[i]); 
}

int nck (int n,int k){
  if(k<0 || k>n) return 0;
  int ret=fact[n]; ret*=infact[k]; ret%=mod;
  ret*=infact[n-k]; ret%=mod;
  return ret;
}
void q1(){
  string s; cin>>s;
  if(s>="a" && s<="z") cout<<"a";
  else cout<<"A";
}
void q2(){
  int n,k; cin>>n>>k;
  int a[n]; f(i,0,n) cin>>a[i];
  sort(a,a+n);
  int s=0;
  f(i,0,k)s+=a[i];
  cout<<s;
}
void q3(){
  string ret="";
  int a; cin>>a;
  while(a!=0){
    a--;
    ret+=(a%26 +'a');
    a/=26;
  }
  reverse(ret.begin(),ret.end());
  cout<<ret;
}
void q4(){
  int n; cin>>n;
   int a[100005]={0};
   int s=0;
  f(i,0,n){
    int x; cin>>x;
    s+=x;
    a[x]++;
  }
  int q; cin>>q;
  while(q--){
    int b,c; cin>>b>>c;
    s-=a[b]*b;
    s+=a[b]*c;
    a[c]+=a[b];
    a[b]=0;
    cout<<s<<"\n";
  }
 
}
void q5(){
  int n; cin>>n;
  int x=0;
  int a[n]; f(i,0,n){
    cin>>a[i];
    x^=a[i];
  } 
   f(i,0,n) cout<<(x^a[i])<<" ";
}
int32_t main(){
#ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  facto();
  int k; cin>>k;
  string s; cin>>s;
  int l=k+s.size();
  int xp=s.size();
  // total = 26^l - those which do not contain subsequence
  // --- i= 0 to  xp-1 prefix present as subseqeunce and remaining have 25^(l-i)
  int ret=1;
  f(i,0,l){
    ret*=26; ret%=mod;
  }
  int sub=0;

  f(i,0,xp){
    // l choose i
    sub+= (nck(l,i)*po(25,l-i));
    sub%=mod; 
  }

  cout<<((ret-sub)%mod + mod) %mod <<"\n";
  return 0;
}


Measured memory_bytes: 35516
#include <bits/stdc++.h>
#define rep(i, a, b) for(int  i = a; i < b; i++)
#define rrep(i, a, b) for(int  i = b - 1; i >=  a; i--)
using namespace std;
typedef long long ll;

int main(){
    int N, M; cin >> N >> M;
    string S; cin >> S;
    reverse(S.begin(), S.end());
    vector<int> ans;
    int now = 0;
    while(now <= N){
        //cout << now << endl;
        bool flag = 1;
        rrep(i, 1, M + 1){
            if(now + i <= N &&  S[now + i] == '0'){
                ans.push_back(i);
                now += i;
                flag = 0;
                break;
            }
        }
        if(flag){
            cout << -1 << endl;
            return 0;
        }
        if(now == N){
            break;
        }
    }
    reverse(ans.begin(), ans.end());
    rep(i, 0, ans.size()){
        if(i != 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;
}

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

int gcd(int& a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	int W, H, C;
	cin >> W >> H >> C;
	cout << C * H * W / gcd(H, W) / gcd(H, W) << endl;
}


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

int main() {
  int X;
  cin >> X;

  for (int i = X;; i++) {
    bool is_prime = true;
    for (int j = 2; j < i; j++) {
      if (i % j == 0) {
        is_prime = false;
        break;
      }
    }
    if (is_prime) {
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
const int MAX = 1000005;
const ll MOD = 1000000007;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main(){
  int n,m;
  cin >> n >> m;
  ll a[n];
  priority_queue<ll> pq;
  rep(i,n){
    cin >> a[i];
    pq.push(a[i]);
  }
  rep(i,m){
    ll t = pq.top();
    pq.pop();
    t/=2;
    pq.push(t);
  }
  ll sum = 0;
  while(!pq.empty()){
    sum += pq.top();
    pq.pop();
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 2040
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); //個数
		int total = in.nextInt(); //許容量
		int[] v = new int[n];//価値
		int[] w = new int[n];//重さ
		for (int i = 0; i < n; i++) {
			v[i] = in.nextInt();
			w[i] = in.nextInt();
		}
		int[][] t = new int[n + 1][n * 100 + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n * 100 ; j++) {
				t[i][j]=total+1;
			}
		}
		t[0][0] = 0;
		t[0][v[0]] = w[0];
		int sum=v[0];
		for (int i = 1; i < n; i++) {//品物１こずつループ
			sum+=v[i];
			for (int j = 0; j <= sum; j++) {
				if (v[i] > j) {
					t[i][j] = Math.min(t[i - 1][j], w[i]);
				} else {
					if (t[i - 1][j - v[i]] + w[i] > total) {
						//許容量こえたとき
						t[i][j] = t[i - 1][j];
					} else {
						t[i][j] = Math.min(t[i - 1][j], t[i - 1][j - v[i]] + w[i]);
					}
				}
				//System.out.printf("t[%d][%d]=%d\n", i, j, t[i][j]);
			}
		}
		int rtn=0;
		for (int i = n * 100; i >= 0; i--) {
			if (t[n - 1][i] > 0 && t[n - 1][i] <= total) {
				rtn=i;
				break;
			}
		}
		System.out.println(rtn);
		in.close();
	}
}



Measured memory_bytes: 31784
from itertools import product
N, *ABC = map(int, input().split())
L = [int(input()) for _ in range(N)]
ans = float("inf")
for prod in product(range(4), repeat=N):
    abc = [0] * 3
    mp = -30
    for p, l in zip(prod, L):
        if p != 3:
            abc[p] += l
            mp += 10
    if abc[0] and abc[1] and abc[2]:
        mp += sum(map(lambda x,y: abs(x-y), ABC, abc))
        ans = min(ans, mp)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
 
  if (a % 2 == 0 || b % 2 == 0) {
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
  
}

Measured memory_bytes: 3608
import java.lang.*;
import java.io.*;
import java.util.*;

class Main{
	public static void main(String args[]) throws Exception{
		FScanner sc=new FScanner();
		//Scanner sc=new Scanner(System.in);
		int n=sc.readInt();
		int[] num=sc.readIntL();
		
		int[] ac=new int[100001];
		int[] bc=new int[100001];
		
		for(int i=0; i<num.length; i+=2){
			ac[num[i]]+=1;
		}
		for(int i=1; i<num.length; i+=2){
			bc[num[i]]+=1;
		}
		
		int am=0;
		int ax=0;
		int bm=0;
		int bx=0;
		
		for(int i=0; i<ac.length; i++){
			if(am<ac[i]){
				am=ac[i];
				ax=i;
			}
		}
		for(int i=0; i<bc.length; i++){
			if(bm<bc[i]){
				bm=bc[i];
				bx=i;
			}
		}
		
		if(ax!=bx){
				System.out.println((n/2-am)+(n/2-bm));
		}else if(ax==bx){
			if(am>bm){
				int bs=0;
				bm=0;
				for(int i=0; i<bc.length; i++){
					if(bm<bc[i] && i!=bx){
						bm=bc[i];
						bs=i;
					}
				}
				System.out.println((n/2-am)+(n/2-bm));
			}else if(am<bm){
				int as=0;
				am=0;
				for(int i=0; i<ac.length; i++){
					if(am<ac[i] && i!=ax){
						am=ac[i];
						as=i;
					}
				}
				System.out.println((n/2-am)+(n/2-bm));
			}else if(am==bm){
				int as=0;
				int ay=0;
				for(int i=0; i<ac.length; i++){
					if(ay<ac[i] && i!=ax){
						ay=ac[i];
						as=i;
					}
				}
				int bs=0;
				int by=0;
				for(int i=0; i<bc.length; i++){
					if(by<bc[i] && i!=bx){
						by=bc[i];
						bs=i;
					}
				}
				if(ay<=by){
					System.out.println((n/2-am)+(n/2-by));
				}else{
					System.out.println((n/2-ay)+(n/2-bm));
				}
			}
		}
	}
	
	static void solve(int cur, int nx, int en, int hld){}

	static void disp(int[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%d ",data[i]);
		}
			System.out.println();
	}
	
	static void disp(String[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%s ",data[i]);
		}
			System.out.println();
	}
	
	static void disp(long[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%d ",data[i]);
		}
			System.out.println();
	}
	
	static class FScanner{
		BufferedReader read=null;
		StringTokenizer tok=null;
		Scanner sc;
		FScanner() throws FileNotFoundException{
			sc=new Scanner(System.in);
		}
		boolean hasNextLine(){
			boolean has=true;
			if(!sc.hasNextLine()){
				has=false;
			}
			return has;
		}
		int readInt(){
			String buf=sc.nextLine();
			return Integer.parseInt(buf);
		}
		long readLong(){
			long i=Long.parseLong(sc.nextLine());
			return i;
		}
		int[] readIntL(){
			String[] buf=sc.nextLine().split(" ");
			int[] num=new int[buf.length];
			for(int i=0; i<buf.length; i++){
				num[i]=Integer.parseInt(buf[i]);
			}
			return num;
		}
		
		String readString(){
			return sc.nextLine();
		}
		String[] readStringL(String dlm){
			String[] s=sc.nextLine().split(dlm);
			return s;
		}
	}
}


Measured memory_bytes: 49692
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
long long int N, K;
bool check(long long int num) {
	for (int i = 0; i < N-1; ++i) {
		if ((num%K == 0)||num==0) {
			num++;
		}
		num-=num/K;
		num--;
	}
	if(num>=1)return false;
	else return true;
}

int main(){cin>>N>>K;
	long long int amin=0;
	long long int amax=2e18;

	while (amin + 1 != amax) {
		long long int amid((amin+amax)/2);

		if (check(amid)) {
			amin=amid;
		}
		else {
			amax=amid;
		}
	}
	cout<<amin<<endl;
	return 0;
}




Measured memory_bytes: 3120
import java.util.*;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int K=sc.nextInt();
        double p[];
        double sum[];
        p=new double[N];
        sum=new double[N+1];
        for(int i=0;i<N;i++) p[i]=sc.nextDouble();
        for(int i=0;i<N;i++) p[i]=(p[i]+1)/2;
        for(int i=0;i<N;i++) sum[i+1]=sum[i]+p[i];
        double ans=sum[K];
        for(int i=K+1;i<=N;i++) ans=Math.max(ans,sum[i]-sum[i-K]);
        System.out.printf("%.10f\n",ans);
    }
}

Measured memory_bytes: 67844
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<int, int>
#define debug(x) cout << #x << ": " << x << ", "
#define debugln(x) cout << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const int mod = 1e9+7;

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

  int h, w, k; cin >> h >> w >> k;
  long dp[h+1][w+1];

  int fib[w+1];

  rep(i, h+1) {
    rep(j, w+1) {
      dp[i][j] = 0;
    }
  }
  dp[0][1] = 1;
  
  fib[0] = 1;
  fib[1] = 2;
  for(int i=2; i<=w; i++) {
    fib[i] = fib[i-1] + fib[i-2];
  }

  for(int i=1; i<=h; i++) {
    for(int j=1; j<=w; j++) {
      long x = 1;
      if (w-j-1 >= 0) {
        x *= fib[w-j-1];
      }
      if (j-2 >= 0) {
        x *= fib[j-2];
      }
      //debugln(x);
      dp[i][j] += x * dp[i-1][j];
      dp[i][j] %= mod;
      x = 1;
      if (j>1) {
        if (w-j-1 >= 0) {
          x *= fib[w-j-1];
        }
        if (j-3 >= 0) {
          x *= fib[j-3];
        }
        dp[i][j] += x * dp[i-1][j-1];
        dp[i][j] %= mod;
      }
      x = 1;
      if (j<w) {
        if (w-j-2 >= 0) {
          x *= fib[w-j-2];
        }
        if (j-2 >= 0) {
          x *= fib[j-2];
        }
        dp[i][j] += x * dp[i-1][j+1];
        dp[i][j] %= mod;
      }
    }
  }
  cout << dp[h][k] << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define _CRT_SECURE_NO_WARNIGS
#pragma warning (disable:4996)
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

struct edge_t { int to, cap, rev; };
int maximum_flow_destructive(int s, int t, vector<vector<edge_t> > & g) { // ford fulkerson, O(EF)
	int n = g.size();
	vector<bool> used(n);
	function<int(int, int)> dfs = [&](int i, int f) {
		if (i == t) return f;
		used[i] = true;
		for (edge_t & e : g[i]) {
			if (used[e.to] or e.cap <= 0) continue;
			int nf = dfs(e.to, min(f, e.cap));
			if (nf > 0) {
				e.cap -= nf;
				g[e.to][e.rev].cap += nf;
				return nf;
			}
		}
		return 0;
	};
	int result = 0;
	while (true) {
		used.clear(); used.resize(n);
		int f = dfs(s, numeric_limits<int>::max());
		if (f == 0) break;
		result += f;
	}
	return result;
}
void add_edge(vector<vector<edge_t> > & g, int from, int to, int cap) {
	g[from].push_back(edge_t{ to, cap, int(g[to].size()) });
	g[to].push_back(edge_t { from, 0, int(g[from].size() - 1) });
}

int main() {
	// input
	int h, w; scanf("%d%d", &h, &w);
	int inf = 100000000;
	vector<vector<char> > f = vectors(h, w, char());
	repeat(y, h) repeat(x, w) scanf(" %c", &f[y][x]);
	// maximum flow
	const int src = 0;//S
	const int dst = 1;//T
	//f[y][x]に対応する　行　列を取得する関数
	auto node_y = [&](int y) { return 2 + y; };
	auto node_x = [&](int x) { return 2 + h + x; };
	vector<vector<edge_t> > g(2 + h + w);//頂点0がS　頂点番号1がT あとはH0 H1 H2....W0 W1 W2....
	repeat(y, h) repeat(x, w) {
		if (f[y][x] == 'S') {
			add_edge(g, src, node_y(y), inf);
			add_edge(g, src, node_x(x), inf);
		}
		else if (f[y][x] == 'T') {
			add_edge(g, node_y(y), dst, inf);
			add_edge(g, node_x(x), dst, inf);
		}
		if (f[y][x] == 'o') {
			add_edge(g, node_y(y), node_x(x), 1);
			add_edge(g, node_x(x), node_y(y), 1);
		}
	}
	int flow = maximum_flow_destructive(src, dst, g);
	// output
	if (flow >= inf) flow = -1;
	printf("%d\n", flow);
	return 0;
}

Measured memory_bytes: 896
'use strict'

function myXor(a,b){
	let sa = a.toString(2);
	let sb = b.toString(2);
	if(sa.length < sb.length){
		sa = ('0000000000000000000000000000000000000000000000000000000000000000'+sa).slice(-sb.length);
	}else if(sa.length > sb.length){
		sb = ('0000000000000000000000000000000000000000000000000000000000000000'+sb).slice(-sa.length);
	}
	let answer = 0;
	let bi = 1;
	for(let i=sa.length-1;i>=0;i--){
		if((sa[i]==="0"&&sb[i]==="1")||(sa[i]==="1"&&sb[i]==="0")){
			answer += bi;
		}
		bi *= 2;
	}
	return answer;
}

function myShift(b,n){
	for(let i=0;i<n;i++){
		b *= 2;
	}
	return b;
}

function count1(X,i){
	let n = X % myShift(1,i);
	//console.log("n:",X,myShift(1,i));
	if(n < myShift(1,(i-1))) return 0;
	
	//console.log("return:",(X+1)%2)
	return (X+1)%2;
}

function getXorNumber(X){
	//console.log("------",X);
	let answer = 0;

	//2進1桁目だけ別計算
	answer += Math.floor((X+1)/2)%2;

	//console.log("bit:",1,answer,answer);

	//2進2桁目以降
	let bit = 0;
	for(let i=2;i<52;i++){
		bit = 1;
		for(let j=1;j<i;j++) bit *= 2;
		if(bit > X) break;

		if(count1(X,i) === 1) answer += bit;	

		//console.log("bit:",i,bit,answer);
	}
	return answer;
}

function Main(input){
	let temp = input.trim().split(" ");
	let A = parseInt(temp[0]);
	let B = parseInt(temp[1]);

	if(A===B || A===0){
		console.log(B);
		return;
	}
	let u = getXorNumber(B);
	let l = getXorNumber(A-1);
	//console.log(u.toString(2));
	//console.log(l.toString(2));
	console.log(myXor(u,l));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.begin()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int dp[100010];

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

  int n; cin >> n;

  int h[100010];
  for (int i = 1; i <= n; ++i) {
    cin >> h[i];
  }

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

  cout << dp[n] << endl;

  return 0;
}



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

int main() {
  int n;
  while(cin >> n && n) {
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    int sum[n];
    sum[0]=a[0];
    int max=sum[0];
    for(int i=1; i<n; i++) {
      sum[i]=sum[i-1]+a[i];
      if(sum[i]>max) max=sum[i];
      for(int j=0; j<i; j++) {
	if(sum[i]-sum[j]>max) max=sum[i]-sum[j];
      }
    }
    cout << max << endl;
  }
  return 0;
}


Measured memory_bytes: 1180
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> p;
typedef unsigned long long int ull;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e18;
const ll MOD=1e9+7;

struct UnionFind{
    vector<int> par,rank;
    UnionFind(int n):par(n),rank(n,0){
        for(int i=0;i<n;++i) par[i]=i;
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry) return ;
        if(rank[rx]>rank[ry]) par[ry]=rx;
        else par[rx]=ry;
        if(rank[rx]==rank[ry]) rank[ry]++;
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    int cnt(int n){
        int res=0;
        for(int i=0;i<n;++i){
            if(root(i)==i) res++;
        }
        return res;
    }
};

int N,M;
vector<int> A,K;
int main(){
    cin>>N>>M;
    A.resize(M);
    K.resize(M);
    fill(K.begin(),K.end(),0);
    for(int i=0;i<M;++i){
        int B;cin>>A[i]>>B;
        for(int j=0;j<B;++j){
            int C;cin>>C;
            K[i]+=(1<<(C-1));
        }
    }
    ll dp[M+1][1<<N];
    for(int i=0;i<=M;++i){
        for(int j=0;j<(1<<N);++j){
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=0;i<M;++i){
        for(int j=0;j<(1<<N);++j){
            if(dp[i][j]==INF) continue;
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            dp[i+1][j|K[i]]=min(dp[i+1][j|K[i]],dp[i][j]+A[i]);
        }
    }
    if(dp[M][(1<<N)-1]==INF) cout<<-1<<endl;
    else cout<<dp[M][(1<<N)-1]<<endl;
    return 0;
}

Measured memory_bytes: 35476
def main():
  _map, _range, _int = map, range, int
  n, q = _map(_int, input().split())
  values = [0] * (n + 1)
  parents = [0] * (n + 1)
  for _ in _range(n - 1):
    a, b = _map(_int, input().split())
    parents[b] = a
  for _ in _range(q):
    p, x = _map(_int, input().split())
    values[p] += x
  for i in _range(1, n + 1):
    values[i] += values[parents[i]]
  print(*values[1:])
main()


Measured memory_bytes: 25852
#include<stdio.h>
int main(){
  int n;
  int a[100];
  int count=0;
  int i;
  int j;
  int tmp;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf(" %d",&a[i]);
  }

  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(a[j] < a[j-1]){
	tmp = a[j];
	a[j] = a[j-1];
	a[j-1] = tmp;
	count++;
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d",a[i]);
    if(i != n-1) printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    int n, a, b; cin>>n>>a>>b;
    cout << min(n*a, b) << endl;
}

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

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define MAXX 100005

#define PI 3.14159265358979323846264338327950

#define ll signed long long int
int main()
{
	int a,b=0,f=0,k=0,l;
	cin>>a;
	while (a>b)
	{
		cin>>l;
		if (l>=k)
		{
			f++;
			k=l;
		}
		b++;
	}
	cout<<f;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> mochi(N);
  for (int i = 0; i < N; i++) {
    cin >> mochi[i];
  }
  sort(mochi.begin(), mochi.end());
  int count = 1;
  for (int i = 0; i < N - 1; i++) {
    if (mochi[i] < mochi[i + 1]) {
      count++;
    }
  } 
  cout << count << endl;
}

Measured memory_bytes: 3564
import std.stdio, std.string, std.conv, std.range, std.algorithm;
void main() {
	long n, m, l;
	"%d %d %d\n".readf(&n, &m, &l);
	long[][] a, b;
	foreach (_n; 0..n) a ~= readln.split.to!(long[]);
	foreach (_m; 0..m) b ~= readln.split.to!(long[]);
	foreach (_a; a) {
		long[] c = [];
		foreach (_l; 0..l)
			c ~= iota(m).map!(_m => _a[_m] * b[_m][_l]).sum;
		c.to!(string[]).join(" ").writeln;
	}
}

Measured memory_bytes: 3704
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>

int main() {
  int a, b;
  char op;
  while (true) {
    std::cin >> a >> op >> b;
    int ret;
    switch (op) {
      case '+':
        ret = a + b;
        break;
      case '-':
        ret = a - b;
        break;
      case '*':
        ret = a * b;
        break;
      case '/':
        ret = a / b;
        break;
      default:
        return 0;
    }
    std::cout << ret << std::endl;
  }
}

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextInt64() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func main() {
    sc.Buffer(make([]byte, 200000*1+1), 200000)
	sc.Split(bufio.ScanWords)

	var n int
	var s string
	var ans int64

	mp := map[string]int{}

	n = nextInt()

	for i := 0; i < n; i++ {
		s = nextStr()
		slice := strings.Split(s, "")
		sort.Strings(slice)
		s = strings.Join(slice, "")
		ans += int64(mp[s])
		mp[s]++
	}

	fmt.Println(ans)
}

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

int main()
{
    string S;
    int m,h[110]={};

    while(1){
        cin>>S;
        if(S=="-")break;

        cin>>m;

        for(int i=0;i<m;i++){
            cin>>h[i];
            S=S.substr(h[i])+S.substr(0,h[i]);
        }
        cout<<S<<endl;

    }

    return 0;
}


Measured memory_bytes: 3216
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int N, H;
int a[100000], b[100000];

int main() {
  cin >> N >> H;
  for (int i = 0; i < N; i++) {
    cin >> a[i] >> b[i];
  }
  int a_max = 1;
  for (int i = 0; i < N; i++)
    if (a_max < a[i])
      a_max = a[i];
  sort(b, b + N, greater<int>());

  int b_idx = 0;
  int count = 0;
  while (H > 0) {
    if (b_idx < N && b[b_idx] > a_max)
      H -= b[b_idx++];
    else
      H -= a_max;
    count++;
  }
  cout << count << endl;

  return 0;
}


Measured memory_bytes: 4264
#include<bits/stdc++.h>
using namespace std;
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int As;
int Bs;
char A[103];
char B[103];
int solve(void){
  int i;
  if(As > Bs){
    return 1;
  }
  if(As < Bs){
    return -1;
  }
  for(i=0;i<As;i++){
    if(A[i] > B[i]){
      return 1;
    }
    if(A[i] < B[i]){
      return -1;
    }
  }
  return 0;
}
int main(){
  int res;
  As = rd(A);
  Bs = rd(B);
  res = solve();
  if(res==1){
    wt_L("GREATER");
    wt_L('\n');
  }
  else if(res==0){
    wt_L("EQUAL");
    wt_L('\n');
  }
  else{
    wt_L("LESS");
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20190721-1

// --- original code ---
// int As, Bs;
// char A[103], B[103];
// 
// int solve(void){
//   int i;
//   if(As > Bs) return 1;
//   if(As < Bs) return -1;
//   rep(i,As){
//     if(A[i] > B[i]) return 1;
//     if(A[i] < B[i]) return -1;
//   }
//   return 0;
// }
// 
// {
//   int res;
//   rd(A@As, B@Bs);
//   res = solve();
//   wt( if[res==1, "GREATER", res==0, "EQUAL", "LESS"] );
// }


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int A= 0,B = 0;
  cin >> A >> B;
  int a = 0,b = 0;
  for(int i = 1;i <= 1000;i++){
    a = i*0.08;
    b = i*0.1;
    if(a == A && b == B){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
char a[1000001];
int start,tmp=0;
int main()
{
	gets(a);
	int n=strlen(a); 
	for(int i=0;i<n;i++) 
	  if(a[i]=='C') {start=i;tmp=1;break;}
	if(tmp==1)
	for(int i=start;i<n;i++)
	  if(a[i]=='F') {cout<<"Yes";return 0;}
	cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s=("Sunny","Cloudy","Rainy"); cin>>s;
	if (s=="Sunny") cout<<"Cloudy";
	if (s=="Cloudy") cout<<"Rainy";
	if (s=="Rainy") cout<<"Sunny";
	else cout<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  string s; cin >> s;
  ll ans =0;
  ll b = 0;

  rep(i,s.size()){
    if(s.at(i)=='B'){
      b++;
    }else if(s.at(i)=='W'){
      ans+=b;
    }
  }

  cout << ans <<endl;
}


Measured memory_bytes: 640
// D - String Equivalence
// DFS version
#include <bits/stdc++.h>
using namespace std;

int N;

void dfs(string pre){
	if(pre.size() >= N){
		cout<< pre <<endl;
		return;
	}
	char mx = pre[max_element(pre.begin(), pre.end()) - pre.begin()];
	for(char c='a'; c<=mx+1; ++c) dfs(pre+c);
}

int main(){
	cin>>N;
	dfs("a");
}

Measured memory_bytes: 1536
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int n, a;
	cin >> n;
	vector<int> r(n);
	for (int i = 0; i < n - 1; ++i) {
		cin >> a;
		r[a - 1] += 1;
	}
	for (int i = 0; i < n; ++i) {
		cout << r[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define j1 j1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;



void Main(){

  int d,n; cin>>d>>n;

  if(n==100) ++n;

  cout<< (int)pow(100,d)*n <<"\n";

}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

// Loops
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define _rrep(i, n) rrepi(i, n, 0)
#define rrepi(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)

#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(xi, x) for (auto &&xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)

// typedef
template <class T> using vec = vector<T>;
using ll = long long;
using vi = vec<ll>;
using vvi = vec<vi>;
using vvvi = vec<vvi>;
using pii = pair<ll, ll>;

// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define mp make_pair

// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase(unique(all(v)), v.end())
#define perm(c)                                                                \
  sort(all(c));                                                                \
  for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))

template <class T> pair<T, size_t> max(vector<T> &x) {
  auto it = max_element(all(x));
  return mp(*it, it - x.begin());
}
template <class T> pair<T, size_t> min(vector<T> &x) {
  auto it = min_element(all(x));
  return mp(*it, it - x.begin());
}

template <class T> inline bool chmax(T &maxval, const T &newval) {
  if (maxval < newval) {
    maxval = newval;
    return 1;
  }
  return 0;
}
template <class T> inline bool chmin(T &minval, const T &newval) {
  if (minval > newval) {
    minval = newval;
    return 1;
  }
  return 0;
}

// Utilities
// Grid world utilities
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
#define inside(H, W, y, x) 0 <= (x) && (x) < (W) && 0 <= (y) && (y) < (H)

// Debug
#ifdef LOCAL
#include "dump.hpp"
#define debug(x) cerr << #x << ": " << x << '\n'
#else
#define dump(...)
#define debug(x)
#endif

// Yes or No
void yesno(bool ok, string yes = "Yes", string no = "No") {
  cout << (ok ? yes : no) << endl;
}

// Paste snippets here!!

//

void solve(long long N) {
  bool ok = false;
  while(N>0){
    if(N%4==0) ok = true;
    if(N%7==0) ok = true;
    N -= 7;
  }
  yesno(ok);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false); // Magic for faster cin
  cout.precision(12);
  long long N;
  std::cin >> N;
  solve(N);
  return 0;
}


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

long long int n;
long long int s;

long long int f(long long int N, long long int base){
	if (N == 0 || base <= 1LL){
		return -1;
	}
	long long int res = 0;
	while (N){
		res += N%base;
		N /= base;
	}
	return res;
}
#define MAX 1000000
int main(){
	scanf("%lld%lld", &n, &s);
	for (int i = 2; i < MAX; i++){
		if (f(n, i) == s){
			printf("%d\n", i);
			return 0;
		}
	}
	long long int mint = LLONG_MAX;
	for (long long int i = 1; i*i<=abs(n-s); i++){
		if (abs(n-s)%i == 0){
			long long int a = i;
			long long int b = abs(n-s) / i;
			if (f(n, a + 1LL)==s){
				mint = min(mint, a + 1LL);
			}
			if (f(n, b + 1LL) == s){
				mint = min(mint, b + 1LL);
			}
		}
	}
	if (n == s){
		mint = min(mint, n + 1LL);
	}
	if (mint == LLONG_MAX){
		mint = -1;
	}
	printf("%lld\n", mint);
	return 0;
}

Measured memory_bytes: 256
//list index out of rangeエラー表示用
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep1(i, n) for (int i = 0; i < (int)(n); i++)


int main(){
  int n,x,t;
  cin >> n >> x >> t;
  
  if(n % x == 0){
    cout << n / x * t;
  }
  else{
    cout << (n / x + 1) * t;
  }
}

Measured memory_bytes: 3608
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	stdin := bufio.NewReader(os.Stdin)

	num1str, err := stdin.ReadString(byte(' '))
	lastDigit1 := num1str[len(num1str)-2]
	if err != nil {
		panic(err)
	}
	num2str, err := stdin.ReadString(byte('\n'))
	lastDigit2 := num2str[len(num2str)-2]
	if err != nil {
		panic(err)
	}
	if ((lastDigit2 % 2) * (lastDigit1 % 2)) == 1 {
		fmt.Println("Odd")
	} else {
		fmt.Println("Even")
	}
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var S = ReadLine();

        var b = new int[N + 1];
        var w = new int[N + 1];
        for (int i = 0; i < N; i++)
        {
            b[i + 1] = b[i] + (S[i] == '#' ? 1 : 0);
        }
        for (int i = N - 1; i >= 0; i--)
        {
            w[i] = w[i + 1] + (S[i] == '.' ? 1 : 0);
        }

        var ans = int.MaxValue;
        for (int i = 0; i <= N; i++)
        {
            ans = Min(ans, b[i] + w[i]);
        }
        WriteLine(ans);
    }
}



Measured memory_bytes: 13280
#include <algorithm>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>

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

using namespace std;

typedef long long ll;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;

  int x;
  cin >> x;

  int dd = x % 100;
  int a[5] = {5, 4, 3, 2, 1};

  int cnt = 0;

  for (int i = 0; i < 5; i++) {
    if (dd == 0) { break; }
    cnt += (dd / a[i]);
    dd -= ((dd / a[i]) * a[i]);
  }

  if (cnt * 100 <= (x/100) * 100) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main(void) {

  char t[200001];
  int i = 0;



  scanf("%s", t);

  while (t[i]) {
    if (t[i]=='?') {
      if ((t[i+1]=='P')||(t[i+1]=='\0')||(t[i-1]=='P')) {
        t[i] = 'D';
      } else {
        t[i] = 'P';
      }
    } else if ((t[i]!='P')&&(t[i]!='D')&&(t[i]!='?')){
      printf("error\n");
      return -1;
    }
    i++;
  }

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

  return 0;
}


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

int main(){
  string s;
  int a, b;
  cin >> a >> s >> b;
  if(s[0] == '+')
    cout << a+b << endl;
  if(s[0] == '-')
    cout << a-b << endl;
  return 0;
}


Measured memory_bytes: 256
#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 
	{
		s.erase(K,s.size()-K);
		s=s+"...";
		cout<<s<<endl;
	}
	return 0;
}


Measured memory_bytes: 3636
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		if (x < y) {
			System.out.println("a < b");
		}else if(x > y){
			System.out.println("a > b");
		}else {
				System.out.println("a == b");
			}
		}
	}

Measured memory_bytes: 17176
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, S, E) for(int(X) = (S); (X) < (E); ++(X))
#define rrep(X, S, E) for(int(X) = (E)-1; (X) >= (S); --(X))
#define itrep(X, Y) for(auto(X) = (Y).begin(); (X) != (Y).end(); (X)++)
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef priority_queue<ll, vl> decendingQueue;              //降順
typedef priority_queue<ll, vl, greater<ll>> ascendingQueue; //昇順
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll INF = 9 * 1e18;
const ll MOD = 1e9 + 7;

void solve(long long X, long long A) {
    if(X < A) {
        print(0);
    } else {
        print(10);
    }
}

int main() {
    long long X;
    scanf("%lld", &X);
    long long A;
    scanf("%lld", &A);
    solve(X, A);
    return 0;
}


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

#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define sortv(v) sort(v.begin(),v.end());
#define sorta(a,n) sort(a,a+n);
#define arrayin(a,n) for(int i=0;i<n;i++) cin>>a[i];
#define arrayout(a,n) for(int i=0;i<n;i++) cout<<" ";cout<<"\n";
#define INF INT_MAX //Infinity
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define MOD 1000000007
#define fi first
#define se second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define vi64 vector<lli>
#define viii vector<tuple<int,int,int>>
#define prq priority_queue<int>
#define mii map<int,int>
#define msi multiset<int>
#define nl "\n"
#define sii set<int,int>

typedef long long int lli;
typedef unsigned long long int ulli;
typedef double ld;

using namespace std;

int main()
{
	fio;
	/*int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
	}*/
	int n,k;
	cin>>n>>k;
	int a[n];
	REP(i,n) cin>>a[i];
	sorta(a,n);
	int counter=0;
	int sum=0;
	FORD(i,n-1,0)
	{
		counter++;
		sum+=a[i];
		if(counter==k)
			break;
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
class solution {
private:
	int n, k;
	int dp[100005];
	int ar[100005];
	int abs(int x) {
		return x < 0 ? -x : x;
	}
	int min(int a, int b) {
		if (a < b) return a;
		return b;
	}
	int serc(int x) {
		if (x == n - 1) return 0;
		if (dp[x] != -1) return dp[x];
		dp[x] = abs(ar[x] - ar[x + 1]) + serc(x + 1);
		for (int i = 2; i <= k; i++) {
			if (x + i <= n - 1) dp[x] = min(dp[x], abs(ar[x] - ar[x + i]) + serc(x + i));
		}
		return dp[x];
	}
public:
	solution() {
		scanf("%d %d", &n, &k);
		for (int i = 0; i < n; i++) {
			scanf("%d", &ar[i]);
			dp[i] = -1;
		}
		printf("%d\n", serc(0));
	}
};

#ifndef L0C4L
int main() {
	solution();
	return 0;
}
#endif

Measured memory_bytes: 7168
#include<bits/stdc++.h>
#include<utility>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

#define pb push_back
#define PI acos(-1.0)
#define MAX 10000007 //1e7+7
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define __FastIO  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
ll arr[100005],brr[100005];
vector<ll>V,V1;
/*------------------------------------------------------*/
void solve(ll n){

}
int main(){
  __FastIO;
  ll N,i,j,Test,M,A,B,C,X,Y,Z;
  while(cin>>N){
    ll ans=((N)*(N+1)/(2))-(N);
    cout<<ans<<endl;
  }
  return 0;
}


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 2e5, inf = 0x3f3f3f3f;
bool vis[nsz + 5];
int n, a[nsz + 5], lst[nsz + 5], fst[nsz + 5], nxt[nsz + 5];
num k;
vector<int> c, ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    cont (i, n) {
        cin >> a[i];
        fst[a[i]] = fst[a[i]] ? fst[a[i]] : i;
    }
    for (int i = n; i >= 1; --i) {
        nxt[i] = lst[a[i]] ? lst[a[i]] : fst[a[i]];
        lst[a[i]] = i;
    }
    for (int p = 1; !vis[p]; p = nxt[p] + 1) {
        if (nxt[p] <= p) {
            vis[p] = 1;
            c.push_back(p);
        }
    }
    k = (k - 1) % c.size();
    for (int p = c[k]; p <= n;) {
        if (nxt[p] <= p) {
            ans.push_back(a[p]);
            ++p;
        } else {
            p = nxt[p] + 1;
        }
    }
    loop (i, ans.size()) {
        cout << ans[i] << ' ';
    }
    cout << ln;
}

Measured memory_bytes: 6516
/**
	Language: C++
	Author  : ebby21
**/

#include <bits/stdc++.h>

using namespace std;

#define fastio() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define debug(v) cerr << '\n' << #v << " :\t" << v << '\n'
#define loop(i, L, U) for (ll i = (L); i <= (U); ++i)
#define rloop(i, U, L) for (ll i = (U); i >= (L); --i)
#define foreach(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;

int main() {
	fastio();
	int n;
	cin >> n;
	vi w(n);
	loop(i, 0, n - 1) {
		cin >> w[i];
	}
	int md = INT_MAX;
	loop(i, 0, n - 1) {
		if (i + 1 < n && w[i + 1] == w[i]) continue;

		int s1 = 0, s2 = 0;
		loop(j, 0, i) {
			s1 += w[j];
		}
		loop(j, i + 1, n - 1) {
			s2 += w[j];
		}
		md = min(md, abs(s2 - s1));
	}
	cout << md << '\n';
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000//10^8

/////////////////////////////////



int main(){
    int n;cin>>n;
    int a[n],b[n],c[n];
    for(int i=0;i<=n-1;i++)cin>>a[i];
    for(int i=0;i<=n-1;i++)cin>>b[i];
    for(int i=0;i<=n-1;i++)cin>>c[i];
    sort(a,a+n);sort(b,b+n);sort(c,c+n);
    ll ans=0;
    for(int i=0;i<=n-1;i++){
        ll l=lower_bound(a,a+n,b[i])-a;
        ll r=(c+n)-upper_bound(c,c+n,b[i]);

        ans+=l*r;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1408
def main():
    from math import ceil
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()))
    A.reverse()
    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng != 1:
        x = (ok + ng) // 2
        cnt = 0
        for a, f in zip(A, F):
            if a * f > x:
                cnt += ceil(a - x / f)
            if cnt > k:
                ng = x
                break
        else:
            ok = x

    print(ok)

if __name__ == "__main__":
    main()

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

int main() {
    string s;
    cin>>s;
    long ans = 0;
    long BCnum = 0;
    long i=s.size()-1;
    while(i>=0){
        if(i>0){
            if(s[i-1]=='B' & s[i]=='C'){
                BCnum++;
                i -= 2;
            }
            else if(s[i]=='A'){
                ans+=BCnum;
                i--;
            }
            else{
                BCnum = 0;
                i--;
            }
        }
        else{
            if(s[i]=='A'){
                ans+=BCnum;
            }
            i--;
        }
    }
    cout<<ans<<endl;
}


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

using namespace std;

typedef long long ll;

int n, m;
int danger[155][1010];
vector<int> X[155];
ll dp[155][11][80];

const ll inf = 1LL << 55;

ll solve(int col, int row, int jump)
{
  if(col >= n-1) return 0;
  if(col >= n-2 && jump < m) return 0;
  if(jump > m) return inf;
  if(~dp[col][row][jump]) return dp[col][row][jump];
  ll ret = inf;
  for(int i = 0; i < X[col+1].size(); i++){
    ll D = (danger[col][X[col][row]] + danger[col+1][X[col+1][i]]) * abs(X[col][row] - X[col+1][i]);
    ret = min(ret, solve(col + 1, i, jump) + D);
  }
  if(jump < m && col < n-2){
    for(int i = 0; i < X[col+2].size(); i++){
      ll D = (danger[col][X[col][row]] + danger[col+2][X[col+2][i]]) * abs(X[col][row] - X[col+2][i]);
      ret = min(ret, solve(col + 2, i, jump + 1) + D);
    }
  }
  return dp[col][row][jump] = ret;
}

int main()
{
  while(cin >> n >> m, n || m){
    for(int i = 0; i < 155; i++) X[i].clear();
    for(int i = 0; i < 155; i++){
      for(int j = 0; j < 11; j++) danger[i][j] = -1;
    }
    for(int i = 0; i < n; i++){
      int k; cin >> k;
      for(int j = 0; j < k; j++){
	int x, d;
	cin >> x >> d;
	--x;
	danger[i][x] = d;
	X[i].push_back(x);
      }
    }

    memset(dp, -1, sizeof(dp));
    ll ans = inf;
    for(int i = 0; i < X[0].size(); i++){
      ans = min(ans, solve(0, i, 0));
    }
    if(m > 0 && n > 1){
      for(int i = 0; i < X[1].size(); i++){
	ans = min(ans, solve(1, i, 1));
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2920
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const ll MOD = 1000000007;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;
int dy[2] = {0, 0};
int dx[2] = {-1, 1};

ll n, k;
vl a;
vl s;
map<int, int> r;

int main(void) {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	//freopen("in.txt", "r", stdin);
	cin >> n >> k;
	a.resize(n+1);
	rep(i,1,n+1) {
		cin >> a[i];
	}
	s.resize(n+1);
	rep(i,1,n+1) {
		s[i] = s[i-1] + a[i];
	}
	rep(i,1,n+1) {
		s[i] = (s[i] - i + k) % k;
	}
	s.pb(-1);

	for(int i=0; i<k-1; ++i) {
		if(i > n) break;
		if(r.find(s[i]) != r.end()) {
			r[s[i]]++;
		} else {
			r[s[i]] = 1;
		}
	}

	ll ret = 0;
	for(int i=0; i<n; ++i) {
		r[s[i]]--;
		int j = min(i + k - 1, n + 1);
		if(r.find(s[j]) != r.end()) {
			r[s[j]]++;
		} else {
			r[s[j]] = 1;
		}
		
		ret += r[s[i]];
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 13796
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char s;
  cin >> s;
  if( s == 'a'|| s=='i'||s=='u'||s=='e'||s=='o'){
    cout << "vowel";
  }
  else{
    cout << "consonant";
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<cstdio>

using namespace std;

using Int= long long;

int main(){
    int n, k;
    cin >> n >> k;
    vector<Int> t(n);
    Int ans=10000000010;
    for(int i=0;i<n;i++) cin>>t[i];
    sort(t.begin(),t.end());
    for(int i=0;i<n-k+1;i++) ans=min(ans,t[i+k-1]-t[i]);
    cout << ans <<endl;
}


Measured memory_bytes: 1024