akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<fstream>
#include<string>
using namespace std;

struct tBar{
	unsigned int rdis, bdis, r, b;
	unsigned int w;
};
tBar bar[101];
int N;

unsigned int euclid( int a, int b ){
	while( a != b ){
		if( a>b )	a -= b;
		else		b -= a;
	}
	return a;
}

unsigned int calcWeight( int n ){
	tBar &bn = bar[n];
	unsigned int rw=0, bw=0;
	if( bn.r==0 && bn.b==0 ){
		rw = bn.bdis;
		bw = bn.rdis;
	}else if( bn.r!=0 && bn.b==0 ){
			rw = calcWeight( bn.r );
			if( bn.rdis*rw % bn.bdis == 0 ){
				bw = bn.rdis * rw / bn.bdis;
			}else{
				unsigned int e = euclid( bn.rdis*rw, bn.bdis );
				bw = bn.rdis*rw / e;
				rw *= bn.bdis / e;
			}
	}else if( bn.r==0 && bn.b!=0 ){
			bw = calcWeight( bn.b );
			if( bn.bdis*bw % bn.rdis == 0 ){
				rw = bn.bdis * bw / bn.rdis;
			}else{
				unsigned int e = euclid( bn.bdis*bw, bn.rdis );
				rw = bn.bdis*bw / e;
				bw *= bn.rdis / e;
			}
	}else{
		rw = calcWeight( bn.r );
		bw = calcWeight( bn.b );
	}
	
	while( rw*bn.rdis != bw*bn.bdis ){
		if( rw*bn.rdis > bw*bn.bdis ){
			bw += bn.b==0 ? bn.rdis : bar[bn.b].w;
		}else{
			rw += bn.r==0 ? bn.bdis : bar[bn.r].w;
		}
	}
	bn.w = rw+bw;
	return bn.w;
}

int findRoot( int n ){
	for( int i=1; i<=N; i++ ){
		if( bar[i].r==n || bar[i].b==n ){
			n = i;
			i = 0;
		}
	}
	return n;
}

int main(){
	int n;
	string str;
	while(1){
		getline( cin, str );
		sscanf( str.c_str(), "%d", &n );
		if( n == 0 )	break;
		N = n;
		for( int i=1; i<=n; i++ ){
			getline( cin, str );
			int p,q,r,b;
			sscanf(str.c_str(), "%d %d %d %d", &p, &q, &r, &b);
			int e = euclid( p, q );
			bar[i].rdis = p / e;
			bar[i].bdis = q / e;
			bar[i].r = r;
			bar[i].b = b;
			bar[i].w = 0;
		}
		int root = findRoot(1);
		int sum = calcWeight(root);
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 0
public class Main {

  private static void solve() {
    int n = ni();
    int k = ni();

    int ret = 0;
    while (n > 0) {
      n /= k;
      ret++;
    }
    System.out.println(ret);

  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 23124
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 2000+10;

int mat[maxn][maxn]; 
int up[maxn], left[maxn], right[maxn];
int org[maxn][maxn];
int H, W;

////////////辅助函数////////////
inline bool check(int x, int y) {
  return (org[x-1][y-1]^org[x-1][y]^org[x][y-1]^org[x][y]);
}

////////////主要函数////////////
void init() {
  scanf("%d%d", &H, &W);
  for (int i=0; i<H; i++) 
    for (int j=0; j<W; j++) {
      int ch = getchar();
      while (ch!='#' && ch!='.') ch = getchar();
      org[i][j] = (ch == '#' ? 1 : 0);
    }
  for (int i=1; i<H; i++)
    for (int j=1; j<W; j++)
      if (check(i, j)) mat[i][j] = 1;
}

void solve() {
  int ans = 0;
  for (int j=0; j<=W; j++) up[j]=0, left[j]=0, right[j]=W;
  for (int i=1; i<=H; i++) {
    int lo = 0, ro = W;
    for (int j=0; j<=W; j++) 
      if (mat[i-1][j]) up[j]=1, left[j]=0, lo=j;
      else {
	up[j] = up[j] + 1;
	left[j] = max(left[j], lo);
      }
    for (int j=W; j>=0; j--) {
      if (mat[i-1][j]) right[j] = W, ro = j;
      else right[j] = min(right[j], ro);
      ans = max(ans, up[j] * (right[j] - left[j]));      
    }
  }
  printf("%d\n", ans);
}

int main() {
  init();
  solve();
  return 0;
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define cout(d) cout<<d<<endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

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; }

// ABC141 E - Who Says a Pun?
// 解説: https://www.youtube.com/watch?v=fHZhDUzhzN0

int dp[6000][6000];

int main(){
  int n;
  string s;
  cin >> n >> s;
  
  rrep(i, n){
    rrep(j, n){
      if(s[i] == s[j]) dp[i][j] = dp[i+1][j+1] + 1;
      else dp[i][j] = 0;                        // int型のグローバル配列は0初期化されるので無くてもよい
    }
  }
  
  int ans=0;
  rep(i, n) rep(j, n){
    if(i >= j) continue;
    int now = min(dp[i][j], j-i);             // j-iはjとiの距離. dpテーブルの数はiとjが重なる部分に対しても数えるが、重ならない部分の最大値はj-iとなる
    chmax(ans, now);
  }
  
  cout<<ans<<endl;
}

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

using namespace std;

#define MAX 300
int A[MAX][MAX];
bool edge[MAX][MAX];

int main(){
    int N, i, j, k;
    long long ans = 0;
    cin >> N;
    for(i = 0; i < N; i++) 
        for(j = 0; j < N; j++) {
            cin >> A[i][j];
            edge[i][j] = true;
            ans += A[i][j];
    }

    for(k = 0; k < N; k++) {
        for(j = 0; j < N; j++) {
            for(i = 0; i < N; i++){
                if(A[i][j] > A[i][k] + A[k][j]) {
                    return !printf("-1\n");
                }
                else if(A[i][j] == A[i][k] + A[k][j]) {
                    if(k != i && k != j && edge[i][j]) {
                        ans -= A[i][j];
                        edge[i][j] = false;
                    }
                }
            }
        }
    }

    return !printf("%lld\n", ans/2);
}

Measured memory_bytes: 640
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
from functools import reduce


n,m = map(int,input().split())
pdic= {}
p = 2
while m >1:
    c = 0
    while m%p==0:
        c+=1
        m //= p
    if c>0:
        pdic[p] = c
    p+=1

d = factorial(n-1)
ans = 1
for p in pdic.keys():
    num = pdic[p]
    ans *= factorial(num+n-1)//(factorial(num)*d)
print(ans%(10**9+7))

Measured memory_bytes: 82848
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

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

var mod = 1e9+7;
function mul(a,b){return ((a>>16)*b%mod*65536+(a&65535)*b)%mod;}
function pow(a,n){for(var r=1;n;a=mul(a,a),n>>=1)if(n&1)r=mul(a,r);return r;}
function mput(n){return (n%mod+mod)%mod;}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  var az = 0, bz = 0, z = 0;
  var map = new Map();
  for(var i = 0; i < n; i++){
    var a = nextbig(), b = nextbig();
    if(a === 0n && b === 0n){z++; continue;}
    if(a === 0n){az++; continue;}
    if(b === 0n){bz++; continue;}
    var c = gcd(a,b);
    a /= c, b /= c;
    if(a < 0)a = -a, b = -b;
    if(map.has(a)){
      if(map.get(a).has(b))map.get(a).set(b,map.get(a).get(b)+1);
      else map.get(a).set(b,1);
    }else{
      map.set(a,new Map());
      map.get(a).set(b,1);
    }
  }
  var ans = pow(2,az) + pow(2,bz) - 1;
  for(var i of map){
    for(var j of i[1]){
      var t = 0;
      if(j[0] < 0){
        if(map.has(-j[0]) && map.get(-j[0]).has(i[0]))continue;
      }else{
        if(map.has(j[0]) && map.get(j[0]).has(-i[0]))t = pow(2,map.get(j[0]).get(-i[0]))-1;
      }
      t += pow(2,map.get(i[0]).get(j[0]));
      ans = mul(ans,t);
    }
  }
  return mput(ans-1+z);
}

Measured memory_bytes: 154724
#include<bits/stdc++.h>
#define uLL unsigned long long
using namespace std;
#define LL long long
#define N 200005
#define M 4000005
#define int LL
struct xx {
	int ed,last,ci,di;
} w[N<<1];
int cot = 0,head[N];
void Add(int s,int e,int c,int d) {
	w[++cot].ed = e,w[cot].last = head[s],head[s] = cot;
	w[cot].ci = c,w[cot].di = d;
	return ;
}


int lc[M],rc[M],rt[N<<1],sum[M],num[M],tot;
void Build(int &rt,int L,int R) {
	rt = ++tot;
	if(L == R) return ;
	int mid = L+R>>1;
	Build(lc[rt],L,mid);
	Build(rc[rt],mid+1,R);
	return ;
}
int idx;
int Update(int pre,int L,int R,int d) {
	int rt = ++tot;
	lc[rt] = lc[pre],rc[rt] = rc[pre],sum[rt] = sum[pre]+d,num[rt] = num[pre]+1;
	if(L == R) return rt;
	int mid = L+R>>1;
	if(idx <= mid) lc[rt] = Update(lc[rt],L,mid,d);
	else rc[rt] = Update(rc[rt],mid+1,R,d);
	return rt;
}
int dep[N],fa[N][23],n,Q;
void dfs(int now,int pre,int c,int d) {
	dep[now] = dep[pre]+1,fa[now][0] = pre;
	if(now == 1) rt[now] = rt[pre];
	else {
		idx = c;
		rt[now] = Update(rt[pre],1,n,d);
	}
	for(int i=head[now]; i; i=w[i].last) {
		int e = w[i].ed;
		if(e == pre) continue;
		dfs(e,now,w[i].ci,w[i].di);
	}
	return ;
}

int Up(int x,int step) {
	for(int i=0; i<=20; i++) {
		if( (step&(1<<i)) ) x = fa[x][i];
	}
	return x;
}

int Lca(int a,int b) {
	if(dep[a] > dep[b]) swap(a,b);
	b = Up(b,dep[b]-dep[a]);
	if(a == b) return a;
	for(int i=20; i>=0; i--) {
		if(fa[a][i] != fa[b][i])
			a = fa[a][i],b = fa[b][i];
	}
	return fa[a][0];
}

int Query_1(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return sum[T1]+sum[T2]-sum[T3]-sum[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_1(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_1(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}


int Query_2(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return num[T1]+num[T2]-num[T3]-num[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_2(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_2(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}

signed main() {
	cin >> n >> Q;
	for(int i=1,a,b,c,d; i<n; i++) {
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		Add(a,b,c,d);
		Add(b,a,c,d);
	}
	Build(rt[0],1,n);
	dfs(1,0,0,0);
	for(int j=1; j<=20; j++) {
		for(int i=1; i<=n; i++) fa[i][j] = fa[fa[i][j-1]][j-1];
	}
	int x,y,u,v;
	while(Q--) {
		scanf("%lld%lld%lld%lld",&x,&y,&u,&v);
		int LCA = Lca(u,v);
		LL he = sum[rt[u]]+sum[rt[v]] - sum[rt[LCA]] - sum[rt[LCA]];
		idx = x;
		he -= Query_1(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		int h = Query_2(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		he += h*y;
		printf("%lld\n",he);
	}
	return 0;
}

Measured memory_bytes: 105728
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,h,w,res1,res2;
signed main(){
	cin>>n>>h>>w;
	res1=n-h;
	res1++;
	res2=n-w;
	res2++;
	res1=res1*res2;
	cout<<res1<<endl;
	return 0;
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


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

    map<string,int>cnt;
    rep(i,n){
        string s;
        cin>>s;

        cnt[s]++;
    }

    int MAX=0;

    for(auto x:cnt){
        MAX=max(MAX,x.second);
    }

    for(auto x:cnt){
        if(x.second==MAX){
            cout<<x.first<<endl;
        }
    }

}


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

typedef long long lint;

const int iINF = 1L << 30;
const lint lINF = 1LL << 60;

int n, p[55], t[55];

void solve() {
	int dp[50][4];
	minit(dp, -1);
	
	if (p[0] > t[0]) {
		cout << "NG " << 1 << endl;
		return;
	}
	
	dp[1][1] = p[0];
	for_(i,1,n) {
		for_(k,1,4) {
			if (dp[i][k] == -1) continue;
			bool flag = false;
			
			int pos = p[i - 1];
			int time = t[i - 1];
			
			int dist = abs(p[i] - pos);
			int nxt = dist * (k + 1);
			
			if (k < 3 && time + nxt <= t[i]) {
				flag = true;
				if (dp[i + 1][k + 1] == -1) dp[i + 1][k + 1] = dp[i][k] + dist;
				else dp[i + 1][k + 1] = min(dp[i + 1][k + 1], dp[i][k] + dist);
			}
			
			dist = pos + p[i];
			nxt = pos * (k + 1) + p[i];
			if (time + nxt <= t[i]) {
				flag = true;
				if (dp[i + 1][1] == -1) dp[i + 1][1] = dp[i][k] + dist;
				else dp[i + 1][1] = min(dp[i + 1][1], dp[i][k] + dist);
			}
			
			if (!flag) dp[i][k] = iINF;
		}
	}
	
	int ans = iINF;
	for_(k,0,4) if (dp[n][k] != -1) ans = min(ans, dp[n][k] + p[n - 1]);
	if (ans != iINF) {
		cout << "OK " << ans << endl;
	} else {
		for_rev(i,n - 1, 0) {
			for_(k,0,4) {
				if (dp[i][k] == iINF) {
					cout << "NG " << i + 1 << endl;
					return;
				}
			}
		}
	}
}

int main() {
	while (cin >> n, n) {
		for_(i,0,n) cin >> p[i] >> t[i];
		solve();
	}
	return 0;
}

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

int main() {
  string s_arr[] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
  string S; cin >> S;
  int ans = 7;
  for (int i=0; i<7; i++) {
    if (S != s_arr[i]) ans--;
    else break;
  }
  cout << ans << endl;

  return 0;
}


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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define trav(a, x) for (auto& a : x)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;
#define INF (1ll<<60)

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    string s;
    cin >> s;
    int ans = 0;
    int rocks = 0;
    trav(c, s) {
        if (rocks > 0) {
            if (c == 'g') {
                ans++;
            }
            rocks--;
        } else {
            if (c == 'p') {
                ans--;
            } 
            rocks++;
        }
    }
    cout << ans << endl;
}

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

signed main(){
    int k; cin >> k;
    vector<int> a = {1,2,3,4,5,6,7,8,9};
    while (true){
        if (k <= a.size()){
            cout << a[k-1] << endl;
            return 0;
        }
        k -= a.size();
        vector<int> old; swap(a, old);
        rep(i,old.size()){
            for (int j = -1; j <= 1; j++){
                if (old[i]%10+j < 0 || old[i]%10+j > 9) continue;
                else a.push_back(10*old[i]+old[i]%10+j);
            }

        }
    }
    return 0;
}

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

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

	string s;

	cin >> s;
	
	int res = 0;

	if(s=="RRR")
	{
		cout << 3 << '\n';
	}
	else if(s=="RRS" || s=="SRR")
	{
		cout << 2 << '\n';
	}
	else if(s=="SSS")
	{
		cout << 0 << '\n';
	}
	else
	{
		cout << 1 << '\n';
	}
	return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include <stdlib.h>

struct Node{
  int id,K,parent,left,right;
};

struct Node *T;

int main(){
  int H,i;

  scanf("%d",&H);
  T = (struct Node *)malloc(sizeof(struct Node)*(H+1));
  for(i=1; i<=H; i++){
    T[i].id = i;
    scanf("%d",&T[i].K);
  }
  for(i=1; i<=H; i++){
    printf("node %d: key = %d, ",T[i].id,T[i].K);
    if(i != 1){
      T[i].parent = T[i/2].K;
      printf("parent key = %d, ",T[i].parent);
    } 
    if(2*i <= H) {
      T[i].left = T[2*i].K;
      printf("left key = %d, ",T[i].left);
    }
    if((2*i+1) <= H) {
      T[i].right = T[2*i+1].K;
      printf("right key = %d, ",T[i].right);
    }
    printf("\n");
  }
  return 0;
}

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

int main()
{
 long long n,i;
  cin>>n;
  vector<long long>v(n+1,0);
    long long a[n+1];
  a[0]=0;
  for(i=1;i<=n;i++)cin>>a[i];
  v[0]=0;
    v[1]=0;
    v[2]=abs(a[2]-a[1]);
  for(i=3;i<=n;i++)
  {
    v[i]=min(v[i-1]+abs(a[i]-a[i-1]),v[i-2]+abs(a[i]-a[i-2]));
  }

  cout<<v[n]<<endl;



}


Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, D = LI()
    X = []
    for _ in range(N):
        X.append(LI())

    counter = 0
    import itertools
    for i, j in itertools.combinations(range(N),2):
        summation = 0
        for dim in range(D):
            summation += (X[i][dim] - X[j][dim]) **2

        import math
        if math.sqrt(summation).is_integer():
            counter += 1


    print(counter)





main()

Measured memory_bytes: 3064
n = int(input())
x = list(map(int, input().split()))

s = 10000000000
for p in range(max(x)+1):
    sss = 0
    for i in range(n):
        a = (x[i]-p)**2
        sss += a
    if sss < s:
        s = sss
print(s)

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

using namespace std;

int main()
{
        int n;
        long long a[1<<17];
        long long b[1<<17];
        long long c[1<<17];
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        for(int i = 0; i < n; i++) cin >> c[i];

        sort(a, a+n);
        sort(c, c+n);

        long long cnt = 0;
        for(int i = 0; i < n; i++){
                long long na = lower_bound(a, a+n, b[i]) - a;
                long long nc = (c+n) - upper_bound(c, c+n, b[i]);
                cnt += na * nc;
        }

        cout << cnt << endl;

        return 0;
}

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

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

int main() {
        int h,w;
        cin >> h >> w;

        vector<vector<char>> adj(h,vector<char>(w));
        for(int i = 0; i < h; ++i) {
                for(int j = 0; j < w; ++j) {
                        cin >> adj[i][j];
                }
        }

        for(int i = 0; i < h; ++i) {
                for(int j = 0; j < w; ++j) {
                        if(adj[i][j] != '.') continue;
                        int cnt = 0;
                        for(int k = 0; k < 8; ++k) {
                                int ni = i + dr[k];
                                int nj = j + dc[k];
                                if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                                if(adj[ni][nj] == '#') cnt++;
                        }
                        adj[i][j] = '0' + cnt;
                }
        }

        for(int i = 0; i < h; ++i) {
                for(int j = 0; j < w; ++j) {
                        cout << adj[i][j];
                }
                cout << endl;
        }
}

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

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    if(n >= 2 * k - 1)puts("YES");
    else puts("NO");
    return 0;
}

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")

typedef long long ll;
typedef unsigned long long ull;
#define fatnet ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

const ll MOD = 1e9 + 7;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 2000003983;
const ll MOD3 = 1e9 + 9;
const ll p1 = 1e6 + 3;
const ll p2 = 2017;
const ll p3 = 37;
const ll INF = 5e18;

int main() {
    fatnet;

    ll n;
    cin >> n;
    vector < ll > b(n - 1);
    for (int i = 0; i < n - 1; ++i)
        cin >> b[i];
    vector < ll > a(n);
    for (int i = 0; i < n; ++i) {
        if (i == n - 1)
            a[i] = b[i - 1];
        else if (i == 0)
            a[i] = b[i];
        else
            a[i] = min(b[i], b[i - 1]);
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += a[i];
    cout << ans << "\n";

    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int arr[200000];
int main()
{
  long long   int n,b=0,c=0,a,f=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    for(int i=n-2;i>=0;i--)
    {
        if(arr[i]==arr[i+1]&&f==0){b=arr[i];f=1; i--;}
        else if(arr[i]==arr[i+1]&&f==1){c=arr[i];break;}
    }
    a=b*c;
    cout<<a<<endl;
}


Measured memory_bytes: 640
n, m = map(int, input().split())

neighbors = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in neighbors.keys():
    neighbors.update({a:set()})
  if b not in neighbors[a]:
    neighbors[a].add(b)
  if b not in neighbors.keys():
    neighbors.update({b:set()})
  if a not in neighbors[b]:
    neighbors[b].add(a)
#print(neighbors)
lst = [0] * (n - 1) #部屋１を除く、すべての部屋の通り方を調べる、「通っていない」を0として定義
visited = set() #一度訪れた部屋は再度探索する必要はないので、それを省くための集合
queue = [[0, set([1])]]
while queue:
  #print(queue)
  pre_room, rooms = queue.pop(0) #左が今いる部屋、右が次に進む部屋
  #print(pre_room, rooms)
  for room in rooms:
    if room in visited:
      continue
    if lst[room - 2] == 0 and room != 1: #次に進む部屋が通っていないかどうか（と今いる部屋が１ではないこと）の確認
      lst[room - 2] = pre_room #部屋2の場合、lstのindexは0に相当するので-2する必要がある
    visited.add(room) #今いる部屋を訪れたので、集合に入れる
    next_rooms = set() #次に進む部屋を探索する
    for nei in neighbors[room]:
      next_rooms.add(nei)
    next_rooms = [room, next_rooms]
    queue.append(next_rooms)
if 0 in lst:
  print('No')
else:
  print('Yes')
  for i in range(n - 1):
    print(lst[i])


Measured memory_bytes: 108612
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Silviase
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    DWangoA solver = new DWangoA();
    solver.solve(1, in, out);
    out.close();
  }

  static class DWangoA {

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      int n = in.nextInt();
      String[] s = new String[n];
      int[] t = new int[n];
      boolean f = false;
      long res = 0;
      for (int i = 0; i < n; i++) {
        s[i] = in.next();
        t[i] = in.nextInt();
      }
      String x = in.next();
      for (int i = 0; i < n; i++) {
        if (f) {
          res += (long) t[i];
        }
        if (x.equals(s[i])) {
          f = true;
        }
      }
      out.println(res);
    }

  }
}



Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
typedef pair < int , int > pii;
typedef long long LL;
#define mpr make_pair
#define FS first
#define SC second
#define PB push_back
template < typename T > T MAX(T a,T b){return (a>b)?a:b;}
template < typename T > T MIN(T a,T b){return (a<b)?a:b;}
template < typename T > void UMAX(T &a,T b){a=(a>b?a:b);}
template < typename T > void UMIN(T &a,T b){a=(a<b?a:b);}
LL readint(){
	char c=getchar();
	LL ret=0ll;
	while(!(c>='0' && c<='9')) c=getchar();
	while(c>='0' && c<='9'){
		ret=ret*10ll+(LL)(c-'0');
		c=getchar();
	}
	return ret;
}
void putint(LL v){
	if(!v){
		putchar('0');
		return;
	}
	if(v>=10ll) putint(v/10ll);
	putchar('0'+(v%10ll));
}
char readch(){
	char c=getchar();
	while(c==' '||c=='\n') c=getchar();
	return c;
}
int n,m,dp[105][105],a[105][105];
int main(){
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;++i){
		for(j=0;j<m;++j){
			a[i][j]=(readch()=='#'?1:0);
		}
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=(a[0][0]==1);
	for(i=0;i<n;++i){
		for(j=0;j<m;++j){
			if(dp[i][j]!=-1) continue;
			int cr=(int)1e5;
			if(i && dp[i-1][j]!=-1) UMIN(cr,dp[i-1][j]+(int)(a[i][j] && !a[i-1][j]));
			if(j && dp[i][j-1]!=-1) UMIN(cr,dp[i][j-1]+(int)(a[i][j] && !a[i][j-1]));
			if(cr<(int)1e5) dp[i][j]=cr;
//			printf("dp %d %d = %d\n",i,j,dp[i][j]);
		}
	}
	printf("%d\n",dp[n-1][m-1]);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t m,k,z=0,j;
  cin>>m>>k;
  vector<pair<int,int>> x(m);
  for(j=0;j<m;j++) cin>>x.at(j).first>>x.at(j).second;
  sort(x.begin(),x.end());
  for(auto y:x){
    z+=y.second;
    if(z>=k){
      cout<<y.first<<endl;
      break;
    }
  }
}

Measured memory_bytes: 4012
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

vector<int> a, ans;
vector<bool> used;
vector<vector<int>> graph;
const int INF = 1001001001;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    a.resize(n); ans.resize(n);
    used.resize(n); graph.resize(n);
    rep (i, n) cin >> a[i];
    rep (i, n - 1) {
        int u, v; cin >> u >> v; u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    stack<int> st_dfs; st_dfs.push(0);
    used[0] = true;
    vector<stack<P>> st(n + 1);
    rep (i, n + 1) st[i].push(P(-1, INF));
    while (!st_dfs.empty()) {
        bool rollback = true;
        int now = st_dfs.top();
        for (int i : graph[now]) {
            if (used[i]) continue;
            rollback = false;
            used[i] = true;
            st_dfs.push(i);
        }
        int ng = -1, ok = n + 1;
        eprintf("%d: ", now);
        rep (i, n) eprintf("%d ", (st[i].top().second == INF ? -1 : st[i].top().second));
        while (ok - ng > 1) {
            int med = (ok + ng) / 2;
            if (st[med].top().second >= a[now]) ok = med;
            else ng = med;
        }
        eprintf("(ok:%d) ", ok);
        if (rollback) {
            if (st[ok].top().second > a[now]) st[ok].push(P(now, a[now]));
            int l = -1, r = n + 1;
            while (r - l > 1) {
                int med = (r + l) / 2;
                if (st[med].top().second == INF) r = med;
                else l = med;
            }
            if (st[ok].top().first == now) st[ok].pop();
            ans[now] = r;
            st_dfs.pop();
        } else {
            if (st[ok].top().second > a[now]) st[ok].push(P(now, a[now]));
        }
        eprintf("-> ");
        rep (i, n) eprintf("%d ", (st[i].top().second == INF ? -1 : st[i].top().second)); eprintf("\n");
    }
    for (int i : ans) cout << i << "\n";
    return 0;
}

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int n;
    cin >> n;
    vector <int> a(n + 1);
    for (int i =0 ; i < n; i++) {
        cin >> a[i];
    }
    a[n] = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i] / 2;
        a[i] %= 2;
        if (a[i] && a[i + 1]) {
            a[i]--;
            a[i + 1]--;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3724
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <string>

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define PI acos(-1.0)

using namespace std;

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

pair <ll, ll> arr[200000];
int n;
pair <ll, ll> x, y;
long long dp[200001];

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> x.first >> x.second >> y.first >> y.second;
	cin >> n;
	if (x.first > y.first) swap(x, y);
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (a < x.first || a > y.first) {
			i--;
			n--;
		} else arr[i] = make_pair(a, b);
		
	}
	sort(arr, arr + n);
	dp[0] = x.second;
	if (x.second > y.second) {
		reverse(arr, arr + n);
		dp[0] = y.second;
	}
	for (int i = 1; i <= 200000; i++)
		dp[i] = INF;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i].second > max(x.second, y.second) || arr[i].second < min(x.second, y.second)) continue;
		int l = 0, r = n;
		int ans = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (arr[i].second < dp[mid]) r = mid - 1;
			else { 
				ans = mid;
				l = mid + 1;
			}
		}
		if (ans == -1)
			continue;
		dp[ans + 1] = min(dp[ans + 1], arr[i].second);
		cnt = max(cnt, ans + 1);
	}
	if (cnt == 1 && (x.first == y.first || x.second == y.second))
		printf("%.16lf\n", PI * 10 + 100 * abs(x.first - y.first) + 100 * abs(x.second - y.second) - 20);
	else if (cnt <= min(abs(x.first - y.first), abs(x.second - y.second)))
		printf("%.16lf\n", PI * 5 * cnt + 100 * abs(x.first - y.first) + 100 * abs(x.second - y.second) - 20 * cnt);
	else {
		cnt--;
		printf("%.16lf\n", PI * 5 * cnt + 100 * abs(x.first - y.first) + 100 * abs(x.second - y.second) - 20 * cnt + PI * 10 - 20);
	}
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=998244353;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}

string sa;
LL pp[200005];
LL num[200005];
int tes[200005];
int n,m;

int gcd(int a,int b){
	if(a<b)gcd(b,a);
	if(b==0)return a;
	return gcd(b,a%b);
}

LL check(int a){
	memset(tes,0,sizeof(tes));
	int i,j,k;
	LL b,c;
	LL s=0;
	for(i=0;i<a;i++){
		if(sa[i]=='0')continue;
		tes[i]=1;
		s+=pp[a-i-1];
		if(s>=MAX)s%=MAX;
	}
	bool flag=true;
	for(i=a;i<n;i++){
		tes[i]=1-tes[i-a];
		if(tes[i]==0 && sa[i]=='1')break;
		if(tes[i]==1 && sa[i]=='0'){
			flag=false;
			break;
		}
	}
	if(flag)s++;
	for(i=1;i<a;i++){
		if(a%i!=0)continue;
		s-=num[i];
		if(s<0)s+=MAX;
	}
	if(s>=MAX)s%=MAX;
	num[i]=s;
	return s;
}

int main(){
	LL i,j,k;
	LL a,b,c;
	LL s=0;
	cin>>n;
	cin>>sa;
	pp[0]=1;
	for(i=1;i<=n;i++){
		pp[i]=pp[i-1]*2;
		if(pp[i]>=MAX)pp[i]%=MAX;
	}
	for(i=1;i<=n;i++){
		if(n%i==0 && (n/i)%2==1){
			s+=check(i)*i*2;
			if(s>=MAX)s%=MAX;
		}
	}
	cout<<s<<endl;
}

Measured memory_bytes: 2948
#include <cstdio>
#include <algorithm>
#include <functional>

int main()
{
  int n;
  int a[100];
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
  {
    scanf("%d", a + i);
  }
  std::sort(a, a + n, std::greater<int>());
  int b = 0, c = 0;
  for (int i = 0; i < n; i += 2)
  {
    b += a[i];
  }
  for (int i = 1; i < n; i += 2)
  {
    c += a[i];
  }
  printf("%d\n", b - c);
  return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;


void main() {
    int x;
    scan(x);

    int ans = 1;

    foreach (i ; 2 .. x + 1) {
        for (int d = i*i; d <= x; d *= i) {
            ans = max(ans, d);
        }
    }

    writeln(ans);
}







































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;



void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod; 
    }
}

int main(){
	
	int n;
	
	scanf("%d",&n);
	vector<vector<int>> can(n, vector<int>(n));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            scanf("%d", &can[i][j]);
        }
    }
    vector<int> dp(1 << n); // 2^n
    dp[0] = 1;
    //~ for(int a = 0; a < n; ++a) {
    for(int mask = 0; mask < (1 << n) - 1; ++mask) {
        int a = __builtin_popcount(mask); // the number of bits set to 1
        for(int b = 0; b < n; ++b) {
            if(can[a][b] && !(mask & (1 << b))) {
                int m2 = mask ^ (1 << b);
                //~ debug() << imie(mask) imie(m2) imie(dp[mask]);
                add_self(dp[m2], dp[mask]);
            }
        }
    }
    //~ }
    printf("%d\n", dp[(1<<n)-1]);
}
	
	

	

Measured memory_bytes: 8448
//24
#include<iostream>

using namespace std;

struct record{
  int t,n,m,s;
};

int main(){
  for(int n,m;cin>>n>>m,n|m;){
    int r;
    cin>>r;
    record rec[10000];
    for(int i=0;i<r;i++){
      cin>>rec[i].t>>rec[i].n>>rec[i].m>>rec[i].s;
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
      int s,e,mm;
      cin>>s>>e>>mm;
      int ac=0;
      int at=0;
      int idx=0;
      for(int j=540;j<=1260;j++){
	while(idx<r&&rec[idx].t==j){
	  if(rec[idx].m==mm){
	    if(rec[idx].s){
	      ac++;
	    }else{
	      ac--;
	    }
	  }
	  idx++;
	}
	at+=ac&&s<=j&&j<e;
      }
      cout<<at<<endl;
    }
  }
  return 0;
}
	  

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;

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

    bool flag = true;
    for (int i = 1; i < N; i++) {
        if (H[i] > H[i - 1]) H[i]--;
        if (H[i] < H[i - 1]) flag = false;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 1000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;
typedef int64_t i64;

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

i64 N, K; 
string S;
cin >> N >> K >> S;

i64 ans = 0;
rep(i, 0, N - 1) 
    if (S[i] == S[i + 1]) ++ans;

ans += 2 * K;
cout << min(N - 1, ans) << endl;

}
// 書いて考える．場合分け
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 512
import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

pat = 0

for i in B:
    numA = bisect.bisect_left(A,i)
    numC = bisect.bisect(C,i)
    pat += numA * (len(C)-numC)

print(pat)

Measured memory_bytes: 29528
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
const long long mod = 1e9 + 7;
const int INF = 1 << 20;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    int x = min({a,b,c});
    int z = max({a,b,c});
    cout << x <<' ' <<  a + b + c - x - z << ' ' <<  z << endl;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> h(n);
    FOR(i, 0, n) cin >> h[i];
    vector<ll> a(m), b(m);
    FOR(i, 0, m) {
        cin >> a[i] >> b[i];
        --a[i];
        --b[i];
    }
    
    vector<int> res(n, 1);
    FOR(i, 0, m) {
        if (h[a[i]] > h[b[i]]) res[b[i]] = 0;
        if (h[a[i]] < h[b[i]]) res[a[i]] = 0;
        if (h[a[i]] == h[b[i]]) {
            res[a[i]] = 0; 
            res[b[i]] = 0;
        }
    }
    cout << accumulate(res.begin(), res.end(), 0);
}

signed main() {
    solve();
    return 0;
}

Measured memory_bytes: 6080
import static java.util.Arrays.deepToString;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	public void run() {
		for (;sc.hasNext();) {
			int n = sc.nextInt();
			if (n == 0) break;
			items = new Item[n]; 
			for (int i = 0; i < n; i++) {
				items[i] = new Item();
				items[i].name = sc.next();
				items[i].w = sc.nextInt();
				items[i].s = sc.nextInt();
			}
			
			int totalWeight = 0;
			for (Item item : items) totalWeight += item.w;
			
			bestG = Integer.MAX_VALUE;
			bestSeq = new Item[n];
			seq = new Item[n];
			dfs(0, 0, totalWeight);
			
			for (Item item: bestSeq) {
				System.out.println(item.name);
			}
		}
	}

	void dfs(int depth, int curG, int remainWeight) {
		if (depth == items.length) {
			if (bestG > curG) {
				bestG = curG;
				bestSeq = seq.clone();
			}
			return;
		}
		for (Item item : items) {
			if (!item.used && remainWeight - item.w <= item.s) {
				item.used = true;
				seq[depth] = item;
				dfs(depth + 1, curG + item.w * (depth+1), remainWeight - item.w);
				item.used = false;
				seq[depth] = null;
			}
		}
	}
	
	Item[] items;
	int bestG;
	Item[] bestSeq;
	Item[] seq;
	
	class Item {
		String name;
		int w;
		int s;
		boolean used;
	}
}

Measured memory_bytes: 19604
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define f first
#define s second
#define int long long
#define pb push_back
#define pencho ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 305
#define mod 1000000007

double dp[N][N][N];
int n;

double solveDp(int cnt_1, int cnt_2, int cnt_3) {

       if (cnt_1 < 0 || cnt_2 < 0 || cnt_3 < 0)      return 0;
       if ((int)dp[cnt_1][cnt_2][cnt_3] != -1)    return dp[cnt_1][cnt_2][cnt_3];

       dp[cnt_1][cnt_2][cnt_3] = ((1.0) * n) / (cnt_1 + cnt_2 + cnt_3)
                                 + (((1.0) * cnt_1) * (solveDp(cnt_1 - 1, cnt_2, cnt_3))) / (cnt_1 + cnt_2 + cnt_3)
                                 + (((1.0) * cnt_2) * (solveDp(cnt_1 + 1, cnt_2 - 1, cnt_3))) / (cnt_1 + cnt_2 + cnt_3)
                                 + (((1.0) * cnt_3) * (solveDp(cnt_1, cnt_2 + 1, cnt_3 - 1))) / (cnt_1 + cnt_2 + cnt_3);
       return dp[cnt_1][cnt_2][cnt_3];
}


void solve() {
       pencho
       cin >> n;
       int cnt_1 = 0, cnt_2 = 0, cnt_3 = 0, cnt;

       for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) dp[i][j][k] = -1;

       for (int i = 1; i <= n; i++) {
              cin >> cnt;
              if (cnt == 1)    cnt_1++;      else if (cnt == 2)      cnt_2++;      else cnt_3++;
       }
       dp[0][0][0] = 0;
       solveDp(cnt_1, cnt_2, cnt_3);
       cout << fixed << setprecision(10) << dp[cnt_1][cnt_2][cnt_3];
}


signed main()
{
#ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("o.txt", "w", stdout);
#endif

       solve();
}

Measured memory_bytes: 225480
fun main(args: Array<String>) {
  val (n, t) = readLine()!!.split(" ").map { it.toInt() }
  val a = readLine()!!.split(" ").map { it.toInt() }
  var c = 0
  var v = 0
  var mn = (1e9).toInt()
  for (i in 0 until n) {
    if (a[i] - mn > v) {
      v = a[i] - mn
      c = 1
    } else if (a[i] - mn == v) {
      c++
    }
    mn = arrayOf(mn, a[i]).min()!!
  }
  println(c)
}


Measured memory_bytes: 54176
from string import ascii_lowercase
s = input()
k = int(input())

sub = []
l = [[] for _ in range(5)]

for i in range(min(len(s),5)):
    if i == 0:
        for c in ascii_lowercase:
            if s.find(c) != -1:
                l[i].append(c)
                sub.append(c)
            if len(l[i]) >= k:
                break
    else:
        for ss in l[i-1]:
            for c in ascii_lowercase:
                tmp = ss + c
                if s.find(tmp) != -1:
                    l[i].append(tmp)
                    sub.append(tmp)
            if len(l[i]) >= k:
                break

sub.sort()
print(sub[k-1])



Measured memory_bytes: 3768
from math import factorial, floor
n = int(input())
a_list = list(map(int, input().split()))

co = a_list.copy()
if 0 in co:
    co.remove(0)
co.sort()


if not len(co) % 2 == 0:
    print(0)
    quit()

for index in range(len(a_list))[:-1:2]:
    if not co[index] == co[index + 1]:
        print(0)
        quit()


print(int(pow(2, floor(n / 2))) % (pow(10,9) + 7))

Measured memory_bytes: 13812
num = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
b, f, r, v, v1, n, x, y, z  = 0, 0, 0, 0, 0, 0, 0, 0, 0
n = int(input())
for i in range(n):
	b, f, r, v = list(map(int, input().split()))
	num[b - 1][f - 1][r - 1] += v
for i in range(4):
	if y >= 1:
		z = 0
		y = 0
		x += 1
		print()
		print('####################')
	for i in range(3):
		if z >= 1:
			z = 0
			y += 1
			print('')
		for i in range(10):
			print('', num[x][y][z], end = '')
			z += 1
print()

Measured memory_bytes: 7680
import bisect

n = int(input())
k = len(str(n))

k753_num = []
def get_k753_num(k, s):
  if k == 0:
    if "7" in s and "5" in s and "3" in s:
      k753_num.append(int(s))
      return True
    else:
      return False
  pata = get_k753_num(k-1, "7" + s)
  patb = get_k753_num(k-1, "5" + s)
  patc = get_k753_num(k-1, "3" + s)
  
def count_k753_num(k):
  if k<3:
    return 0
  else:
    return 3**k - (2**k * 3) + 3

# count up k-1 753 num
count = 0
for i in range(k):
  count += count_k753_num(i)

# add k 753 num
get_k753_num(k, "")
k753_num.sort()
count += bisect.bisect_right(k753_num, n)

print(count)

Measured memory_bytes: 3828