akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 100005
#define NIL -1
 
typedef struct{
  int parent, left, right;
}Node;
 
Node Tree[MAX];
int Depth[MAX];
int Height[MAX];
int degree[MAX];
int h;
 
int getDepth(int);
int getHeight(int);
void print(int);
 
 
int main(void){
  int i, n;
  int vertex;
  int child[2];
 
 
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ) {
    Tree[i].parent = NIL;
    Tree[i].left = NIL;
    Tree[i].right = NIL;
  }
 
  for ( i = 0; i < n; i++ ){
    scanf("%d %d %d", &vertex, &child[0], &child[1]);
 
    //子どもがいない場合はdegreeは0である。
    if(child[0] == NIL && child[1] == NIL)
      degree[vertex] = 0;
 
    //子どもがどちらかにいればdegreeは1である。
    else if(child[0] == NIL && child[1] != NIL){
      degree[vertex] = 1;
      Tree[child[1]].parent = vertex;
      Tree[vertex].right = child[1];
    }
     
    else if(child[0] != NIL && child[1] == NIL){
      degree[vertex] = 1;
      Tree[child[0]].parent = vertex;
      Tree[vertex].left = child[0];
    }
 
 
    //子どもが両方存在するという事はdegreeは2という事
    else{
      degree[vertex] = 2;
      Tree[child[0]].parent = vertex;
      Tree[child[1]].parent = vertex;
       
      Tree[vertex].left = child[0];
      Tree[vertex].right = child[1];
    }
  }
 
  for(i = 0;i < n; i++){
    Height[i] = getHeight(i);
  }
 
  for ( i = 0; i < n; i++ )
    Depth[i] = getDepth(i);
   
  for ( i = 0; i < n; i++ )
    print(i);
   
  return 0;
}
 
int getHeight(int u){
  int l = Tree[u].left;
  int r = Tree[u].right;
  int heightL = 0;
  int heightR = 0;
 
  if(l == NIL && r == NIL){
    return 0;
  }
 
  if(l != NIL){
    heightL = getHeight(l) + 1;
  }
 
  if (r != NIL){
    heightR = getHeight(r) + 1;
  }
 
  if(heightL < heightR){
    return heightR;
  }
  else{
    return heightL;
  }
}
 
 
int getDepth(int u){
  int d = 0;
 
  while(Tree[u].parent >= 0){
    u = Tree[u].parent;
    d++;
  }
 
  return d;
}
 
void print(int u){
  int index = Tree[u].parent;
 
  printf("node %d: parent = %d, ",u, Tree[u].parent);
  if(index == NIL){
    printf("sibling = %d, ",NIL);
  }
  else if(Tree[index].right != u){
    printf("sibling = %d, ",Tree[index].right);
  }
  else if(Tree[index].left != u){
    printf("sibling = %d, ",Tree[index].left);
  }
     
  printf("degree = %d, depth = %d, height = %d, ",degree[u], Depth[u], Height[u]);
 
  if(Tree[u].parent == NIL)
    printf("root\n");
 
  else if(degree[u] == 0)
    printf("leaf\n");
 
 
  else if(2 >= degree[u] && degree[u] >= 1)
    printf("internal node\n");
 
} 



Measured memory_bytes: 2048
/*input

*/
#include<bits/stdc++.h>
using namespace std;

#define int long long



signed main(){
  int a,b;
  cin >> a >> b;
  for(int i = 1;i <= 3;i++){
  	if((a*b*i)%2){
  		cout << "Yes";
  		return 0;
  	}
  }
  cout << "No";
  return 0;
}

Measured memory_bytes: 256
N,M = map(int, input().split())
anything = list(map(int, input().split()))
count = 0
sum = 0
for a in anything:
    sum = sum + a

for a in anything:
    if a >= sum/(4*M):
        count = count + 1
    

if count >= M:
    print("Yes")
else:
    print("No")



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

const int max_N = 100 + 21;

int n,a[max_N<<1],ans;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=2*n;++i)
		scanf("%d",a+i);
	std::sort(a+1,a+1+2*n);
	for(int i=1;i<=2*n;i+=2)
		ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	std::vector<int> dp(n, 1 << 30); dp[0] = 0;
	for(int i = 0; i < n; i++) {
		if(i + 1 < n) dp[i + 1] = std::min(dp[i + 1], dp[i] + std::abs(a[i + 1] - a[i]));
		if(i + 2 < n) dp[i + 2] = std::min(dp[i + 2], dp[i] + std::abs(a[i + 2] - a[i]));
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}


Measured memory_bytes: 1024
A = input()
B = input()
if len(A)>len(B):
    print("GREATER")
elif len(A)<len(B):
    print("LESS")
else:
    for i in range(len(A)):
        if A[i]>B[i]:
            print("GREATER")
            break
        elif A[i]< B[i]:
            print("LESS")
            break
        if i == len(A)-1:
            print("EQUAL")

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

int main(){
  int n;
  scanf("%d",&n);
  int a[1000]={0};
  int cnt1=0;
  int cnt2=0;
  int cnt3=0;
  int cnt4=0;
  int cnt5=0;
  int cnt6=0;
  int cnt7=0;
  int cnt8=0;
  int cnt9=0;

  for(int i = 0;i < n;i++){
    scanf("%d",&a[i]);
    if(a[i]<400){
      cnt1=1;
    }else if(a[i]<800){
      cnt2=1;
    }else if(a[i]<1200){
      cnt3=1;
    }else if(a[i]<1600){
      cnt4=1;
    }else if(a[i]<2000){
      cnt5=1;
    }else if(a[i]<2400){
      cnt6=1;
    }else if(a[i]<2800){
      cnt7=1;
    }else if(a[i]<3200){
      cnt8=1;
    }else{
      cnt9++;
    }
  }
  int res1 = cnt1+cnt2+cnt3+cnt4+cnt5+cnt6+cnt7+cnt8;

  int res2 = res1 + cnt9;
  if(res1==0){
    res1=1;
  }
  


  printf("%d %d",res1,res2);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int n, t[112345], a[112345];

    cin >> n;
    REP(i, n)
    cin >> t[i + 1];
    REP(i, n)
    cin >> a[i + 1];

    int s = -1;

    t[0] = 0;
    t[n + 1] = MOD;
    a[0] = MOD;
    a[n + 1] = 0;

    int mat = 0;
    int maa = 0;
    REP(i, n)
    {
        mat = max(mat, t[i + 1]);
        maa = max(maa, a[i + 1]);
    }

    if (mat != maa)
    {
        cout << 0 << endl;
        return 0;
    }

    REP(i, n)
    {
        if (a[i + 1] == t[i + 1] && a[i + 1] == mat)
        {
            s = i + 1;
            break;
        }
    }

    if (s == -1)
    {
        cout << 0 << endl;
        return 0;
    }

    ll res = 1;

    for (int i = 1; i < s; i++)
    {
        if (t[i - 1] < t[i])
        {
        }
        else
        {
            (res *= t[i]) %= MOD;
        }
    }

    for (int i = n; i > s; i--)
    {
        if (a[i + 1] < a[i])
        {
        }
        else
        {
            (res *= a[i]) %= MOD;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1152
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main() {
    int S;
    ll md = 1000000007;

    cin >> S;

    vector<int> dp(S+1,0);
    dp[0] = 1;

    for(int i=1;i<=S;i++) {
        for(int j=0;j<=i-3;j++) {
            dp[i] += dp[j];
            dp[i] %= md;
        }
    }

    cout << dp[S] << endl;

    return 0;
    
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
using namespace std;
int n,m,p;
vector <int> mp[8][8];
int cnt;
void reset() {
  for(int i=0;i<8;i++)
    for(int j=0;j<8;j++)
      mp[i][j].clear();
}

void out(){
  cout << "-----------------"<<endl;
  for(int k=0;k<n;k++){
    cout <<"-----------"<<k<<"-----------"<<endl;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(mp[i][j].size() <= k) cout <<".";
	else cout << mp[i][j][k];
      }
      cout << endl;
    }
  }


}

void check(int x,int y,int z,int dx,int dy,int dz,int sta) {
  int nx=x+dx,ny=y+dy,nz=z+dz;
  if(nx<0 || ny<0 || nz<0 || nx>=n || ny>=n || nz>=n || mp[ny][nx].size()<=nz);
  else if(mp[ny][nx][nz] == sta) {
    cnt++;
    check(nx,ny,nz,dx,dy,dz,sta);
  }
}
  

int main() {
  
  while(1) {
    cin >> n >> m >> p;
    if(n==0 && m==0 && p==0) break;
    
    reset();
    
    int sta =1;
    int ans =-1;
    int kai = 0;
    int mv;
    for(int q=0;q<p;q++) {
      int x,y;
      cin >> x >> y;
      x--,y--;
      mp[y][x].push_back(sta%2);
      int z = mp[y][x].size()-1;
      //out();
      kai++;
      for(int i=-1;i<2;i++)
	for(int j=-1;j<2;j++)
	  for(int k=-1;k<2;k++){
	    if(i==0 && j==0 && k==0) continue;
	    if(ans != -1) continue;
	    cnt = 1;
	    check(x,y,z,i,j,k,sta%2);
	    if(cnt >= m ) ans = sta%2,mv = kai;
	    else check(x,y,z,-i,-j,-k,sta%2);
	    if(cnt >= m) ans = sta%2,mv = kai;
	    //   cout << cnt <<endl;
	  }
      
      sta++;
	    
    }
    if(ans == -1) cout << "Draw"<<endl;
    else {
      if(ans == 0) cout << "White ";
      else cout << "Black ";
    cout << mv << endl;
    }
    
  }
  
  
  return 0;  
  
}
    

Measured memory_bytes: 1220
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String> al = new ArrayList<>();
        while(true) {
            String s1 = sc.next();
            if(s1.equals("-")) {
                break;
            }
            int a = sc.nextInt();
            String s2 = null;
            String s3 = null;
            String s4 = s1;
            for(int i =0; i < a; i++) {
                int b = sc.nextInt();
                s2 = s4.substring(0, b);
                s3 = s4.replaceFirst(s2, "");
                s4 = s3.concat(s2);
            }
            al.add(s4);
        }
        for(String s : al) {
            System.out.println(s);
        }
    }
}



Measured memory_bytes: 26536
#include<iostream>
#define M std::cin>>
int s[200001];main(){int n,c,l,z,x,h=1e9+7;M n;M z;c=l=s[z]=1;for(int i=2;i<=n;i++){M x;if(x!=z){c+=s[x];c%=h;s[x]+=l;s[x]%=h;}l=c;z=x;}std::cout<<c;}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {

	int n, i, j;
	int all[52];
	int cards[52];
	char symbol;
	int number;
	int snum;
	int card;

	for (i = 0; i < 52; i++) {
	
		all[i] = 1;

	}

	scanf("%d", &n);

	for (j = 0; j < n; j++) {
		scanf("\n%c %d", &symbol, &number);

		switch (symbol) {

		case 'S':
			snum = 0;
			break;
		case 'H':
			snum = 1;
			break;
		case 'C':
			snum = 2;
			break;
		case 'D':
			snum = 3;
			break;
		}

		cards[j] = snum * 13 + number - 1;

	}

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

		card = cards[j];

		all[card] = 0;

	}

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

		if (all[i] == 1) {

			number = (i + 1) % 13;
			if (number == 0) {
				number = 13;
			}

			snum = (i - number + 1) / 13;

			switch (snum) {

			case 0:
				symbol = 'S';
				break;
			case 1:
				symbol = 'H';
				break;
			case 2:
				symbol = 'C';
				break;
			case 3:
				symbol = 'D';
				break;

			}

			printf("%c %d\n", symbol, number);

		}
	}

	return(0);

}


Measured memory_bytes: 2044
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	int CD = lcm(C, D);
	int AtoB = B - A + 1;
	int num = (B / C - (A - 1) / C) + (B / D - (A - 1) / D) - (B / CD - (A - 1) / CD);
	cout << AtoB - num;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

#define AS(a) (sizeof(a)/sizeof(a[0]))
using namespace std;
long long int MOD = 1000000007;
long long int INF = 1000000007;

int main() {
  long long int n,a,b;
  cin >> n >> a >> b;
  long long int x[n];
  for(int i = 0; i < n; i++) {
    cin >> x[i];
  }
  long long int sum = 0;
  for(int i = 1; i < n; i++) {
    sum += min((x[i] - x[i-1]) * a,b);
  }
  cout << sum << endl;

}


Measured memory_bytes: 1024
import itertools
import math
import numpy as np
z = []
N = int(input())
for i in range(N):
  z.append(list(map(int,input().split(' '))))
d = 0  
x = []
p = list(itertools.permutations(z, N))
#print(p,N)  
for i in p:
  #print(i)
  #ans = math.sqrt((i[0][0]-i[1][0])**2) + math.sqrt((i[0][1]-i[1][1])**2)
  for j in range(N-1):
    #print(j,i)
    #d += np.linalg.norm(np.array([i[j+1][0],i[j+1][1]]) - np.array([i[j][0],i[j][1]]))
    d += math.sqrt(((i[j][0]-i[j+1][0])**2) + ((i[j][1]-i[j+1][1])**2))
    #print(([i[j+1][0],i[j+1][1]]), ([i[j][0],i[j][1]]))
  x.append(d) 
  d = 0
  
  
#  print(ans)
  
#print(x)  
print(sum(x)/len(x))  


Measured memory_bytes: 18252
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());
typedef long long ll;

int n;

void dfs(string s,char mc){
  if(s.size() == n){
    cout << s << endl;
    return;
  }
  for(char c = 'a';c <= mc+1;c++){
    dfs(s+c,max(c,mc));
  }
}

int main(){
  cin >> n;
  dfs("a",'a');
}


Measured memory_bytes: 1536
#include<iostream>
#include<sstream>

using namespace std;
string tmp,str;
int num,ans[2],n;

string i2s(int num){
  string str;
  stringstream s;
  s<<num;
  s>>str;
  return str;
}
  
void dfs(string str,int cnt){
  if(str.size()==1){
    ans[cnt%2]=1;
    return;
  }
  tmp="";
  num=(str[0]-'0')+(str[1]-'0');
  tmp+=i2s(num);
  if(str.size()>2)tmp+=str.substr(2,str.size()-2);
  dfs(tmp,cnt+1);
}
int main(){
  cin>>n;
  while(n--){
    ans[0]=ans[1]=0;
    string str;
    cin>>str;
    dfs(str,0);
    if(!ans[0]) cout<<"Fabre wins."<<endl;
    else cout<<"Audrey wins."<<endl;
    
  }
  return 0;
}

Measured memory_bytes: 2412
#include<cstdio>
int D[310][310][610], w[310], n, Mod = 1000000007, F[410], InvF[410], res;

int Pow(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1)r = 1ll * r*a%Mod;
		a = 1ll * a*a%Mod; b >>= 1;
	}
	return r;
}

int main() {
	int i, j, k, s = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	F[0] = InvF[0] = 1;
	for (i = 1; i <= 400; i++) {
		F[i] = 1ll * F[i - 1] * i%Mod;
		InvF[i] = Pow(F[i], Mod - 2);
	}
	D[0][0][0] = 1;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < i; j++) {
			for (k = 0; k <= s; k++) {
				D[i][j][k] = (D[i][j][k] + 1ll * D[i - 1][j][k] * InvF[w[i] - 1])%Mod;
				if (w[i] >= 2) D[i][j + 1][k + w[i] - 2] = (D[i][j + 1][k + w[i] - 2] + 1ll * D[i - 1][j][k] * InvF[w[i] - 2]) % Mod;
			}
		}
		if (w[i] >= 2)s += w[i] - 2;
	}
	for (i = 3; i <= n; i++) {
		for (j = 0; j <= s; j++) {
			if (i != n && j == 0)continue;
			int t = 1ll * D[n][i][j] * F[i - 1] % Mod * InvF[2] % Mod * F[j] % Mod;
			if (i == n) res = (res + t) % Mod;
			else res = (res + 1ll * t*F[n - i - 1]%Mod*InvF[j-1]) % Mod;
		}
	}
	printf("%d\n", res);
}

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

using namespace std;

#define long long long


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

    string s;

    cin >> s;

    int ans = 1;

    for (int i = 0; i < n; i++) {
        if (i != 0 && s[i] != s[i - 1]) ans++;
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

int gcd(int x,int y){
  if(x%y==0) return y;
  else return gcd(y,x%y);
}

bool isPrime(int n){
  if(n < 2) return false;
  else if(n == 2) return true;
  else if(n%2==0) return false;

  for(int i=3;i<=sqrt(n);i++){
    if(n%i==0) return false;
  }
  return true;
}

int main(){
  int n,d;
  cin >> n >> d;
  cout<< (n+2*d)/(2*d+1) <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>

using namespace std;
typedef long long int64;

int64 gcd(int64 a, int64 b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  else return gcd(b, a % b);
}

map<int64, int64> getPrimeFactors(int64 n) {
  map<int64, int64> ret;
  for (int64 i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      n /= i;
      ++ret[i];
    }
  }
  if (n != 1) ++ret[n];
  return ret;
}

int main() {
  int64 A, B;
  cin >> A >> B;
  int64 g = gcd(A, B);
  map<int64, int64> prime_factors = getPrimeFactors(g);
  cout << 1 + prime_factors.size() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 20000005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
const int MOD = 1000000007;
int inc(int a,int b) {
	return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
	return 1LL * a * b % MOD;
}
void update(int &x,int y) {
	x = inc(x,y);
}
int fpow(int x,int c) {
	int res = 1,t = x;
	while(c) {
		if(c & 1) res = mul(res,t);
		t = mul(t,t);
		c >>= 1;
	}
	return res;
}
int dp[150][405],N,f[150][405][405],w,ans;
int a[405],b[405],fac[405],invfac[405];
bool visa[405],visb[405],vis[405][405];
int cnt[405][405],g[405];
int A(int n,int m) {
	if(n < m) return 0;
	return mul(fac[n],invfac[n - m]);
}
void Solve() {
	read(N);
	for(int i = 1 ; i <= N ; ++i) read(a[i]);
	for(int i = 1 ; i <= N ; ++i) read(b[i]);
	fac[0] = 1;
	for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
	invfac[N] = fpow(fac[N],MOD - 2);
	for(int i = N - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
	dp[1][2] = 1;
	for(int i = 1 ; i < N / 3 ; ++i) {
		for(int j = 0 ; j <= i * 2 ; ++j) {
			for(int h = 0 ; h <= j; ++h) {
				update(dp[i + 1][j + 2 - h],mul(A(j,h),dp[i][j]));
			}
		}
	}
	for(int j = 0 ; j <= (N / 3) * 2 ; ++j) update(w,mul(dp[N / 3][j],fac[j]));
	for(int i = 1 ; i <= N ; ++i) {
		visa[a[i]] = 1;
		cnt[i][0] = i;
		memset(visb,0,sizeof(visb));
		for(int j = 1 ; j <= N ; ++j) {
			visb[b[j]] = 1;
			cnt[i][j] = cnt[i][j - 1];
			if(!visa[b[j]]) cnt[i][j]++;
			if(!visa[b[j]] && !visb[a[i]]) vis[i][j] = 1;
		}
	}
	for(int t = N / 3 ; t >= 1 ; --t) {
		memset(g,0,sizeof(g));

		for(int i = N ; i >= 1 ; --i) {
			int s = (t == N / 3);
			for(int j = N ; j >= 1 ; --j) {
				if(vis[i][j]) f[t][i][j] = mul(s,N - 3 * (N / 3 - t) - cnt[i][j]);
				update(s,g[j]);
				update(g[j],f[t + 1][i][j]);
			}
		}
	}
	for(int i = 1 ; i <= N ; ++i) {
		for(int j = 1 ; j <= N ; ++j) {
			update(ans,f[1][i][j]);
		}
	}
	ans = mul(ans,w);
	out(ans);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}


Measured memory_bytes: 87808
#include <stdio.h>

int main(void)
{
	int k;
	scanf("%d", &k);
	
	int x[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	
	printf("%d", x[k-1]);
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <set>
#include <array>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <numeric>

using namespace std;

int main() {

	int n, m;

	cin >> n >> m;

	vector<int> x(m);

	for (int i = 0; i < m; i++) cin >> x[i];

	if (m <= n)
	{
		cout << 0 << endl;
		return 0;
	}

	sort(x.begin(), x.end());

	vector<pair<int, int>> sub(m);

	for (int i = 0; i < m - 1; i++)
	{
		sub[i].first = x[i + 1] - x[i];
		sub[i].second = i;
	}

	sort(sub.begin(), sub.end(), greater<pair<int, int>>());

	int sum = accumulate(sub.begin() + n - 1, sub.end(), 0, [](int acc, pair<int, int> i) {
		return acc + i.first;
	});

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 1408
def func():
    N, k = map(int, input().split() )
    h = list( map(int,input().split()) )

    dp = [float('inf')] * N
    dp[0] = 0
    for n in range(1, N):
        # can_min = 10**4
        # for k in range(1,K+1l):
        #     if n-k >= 0 :
        #         can = dp[n-k] + abs(h[n]-h[n-k])
        #         can_min = min(can, can_min)
        # dp[n] = can_min 
        dp[n] = min([ dp[j] + abs(h[n]-h[j]) for j in range(max(n-k,0), n) ])
    print(dp[N-1])

if __name__=='__main__':
    func()





Measured memory_bytes: 13980
#include <bits/stdc++.h> 
 
#define INF (1<<31) - 1 //INT_MAX/2
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using P = std::pair<int, int>;

int main(int argc, char *argv[])
{
    int N, K;
    std::cin >> N >> K;

    std::vector<int> h(N);
    for (int i = 0; i < N; i++) {
        std::cin >> h[i];
    }

    std::sort(h.rbegin(), h.rend());

    std::vector<ll> v;
    for (int i = 0; i < N-K+1; i++) {
        int temp = h[i] - h[i+K-1]; 
        v.push_back(temp);
    }

    ll min = INF;
    for (int i = 0; i < v.size(); i++) {
        if (min > v[i]) {
            min = v[i];
        }
    }

    std::cout << min << std::endl;
    return 0;
}

Measured memory_bytes: 1784
fun main(args: Array<String>) {
    val sequence =
        listOf(1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51)

    val k = readLine()!!.toInt()

    println(sequence[k - 1])
}

Measured memory_bytes: 33740
#include <iostream>

int main()
{
    int K,A,B;
    std::cin >> K >> A >> B;

    if(A<=B-(B%K))
    {
        std::cout << "OK" << std::endl;
    }
    else
    {
        std::cout << "NG" << std::endl;
    }
    
}


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

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

    return gcd(b, a % b);
}


int main(){
    int k;
    int sum = 0;
    int x, y;
    cin >> k;
    for(int a=1;a<=k;a++){
        for(int b=1;b<=k;b++){
            for(int c=1;c<=k;c++){
                x = gcd(a, b);
                y = gcd(x, c);
                sum += y;    
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3632
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int i = 0; i <= 100; i++) {
      for (int j = 0; j <= 100; j++) {
        if (i*4 + j*7 == N) {
          System.out.println("Yes");
          return;
        }
      }
    }
    System.out.println("No");
  }
}

Measured memory_bytes: 21844
#include <stdio.h>

int main(){
  int n, m, x, y, total=0;
  scanf("%d", &n);
  int v[n];

  for(int i = 0; i < n; ++i){
    scanf("%d", &v[i]);
    total+= v[i];
  }
  scanf("%d", &m);

  for(int i = 0; i < m; ++i){
    scanf("%d %d", &x, &y);
    printf("%d\n", total-v[x-1]+y);
  }
  return 0;
}


Measured memory_bytes: 128
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))

visited = {}
for i in range(1, N+1):
    visited[i] = False

i2p = {}
p2i = {}
i = 0
cur = 1
while True:
    i2p[i] = cur
    p2i[cur] = i
    visited[cur] = True
    if visited[A[cur]]:
        break
    cur = A[cur]
    i += 1

start_loop = p2i[A[cur]]
end_loop = len(i2p)
num_loop = end_loop - start_loop

if K < end_loop:
    print(i2p[K])
else:
    print(i2p[(K-start_loop)%num_loop+start_loop])


Measured memory_bytes: 66600
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline LL read(){
    LL x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
//a:abs大的负数->abs小的负数->小正数->大正数
//b:大正数->小正数->abs小的负数->abs大的负数 
int n,fir;//a[fir]是a数组中第一个非负数
LL k;
LL a[200006],b[200006];
inline int finda(int i,LL ans){
    R int l=1,r=n,mid,ret=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(a[mid]*a[i]<=ans) ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret>=i?(ret-1):ret;//如果ret>=i，说明其中有一对是两个a[i]相乘得到，此时要减1
}
inline int findb(int i,LL ans){
    R int l=1,r=n,mid,ret=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(b[mid]*a[i]<=ans) ret=mid,l=mid+1;
        else r=mid-1;
    }
    return (ret+i>n)?(ret-1):ret;//同理，但b是倒序
}
inline int check(LL ans){
    LL nowk=0;
    for(R int i=1;i<fir;i++)//负数 
        nowk+=findb(i,ans);
    for(R int i=fir;i<=n;i++)//正数
        nowk+=finda(i,ans);
    nowk/=2;//去重
    return nowk>=k;
}
inline int cmp(int x,int y){
    return x<y;
}
int main(){
    n=read();k=read();
    for(R int i=1;i<=n;i++) a[i]=read(); 
    std::sort(a+1,a+1+n,cmp);
    fir=n+1;
    for(R int i=1;i<=n;i++)
        if(a[i]>=0){fir=i;break;}
    for(R int i=1;i<=n;i++) b[n-i+1]=a[i];//存入b数组，对负数二分时使用
    R LL l=-1e18,r=1e18,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    std::printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 6860
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

string S;

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

  cin >> S;
  
  int t1 = (S[0]-'0')*10 + (S[1]-'0');
  int t2 = (S[2]-'0')*10 + (S[3]-'0');
  
  cerr << "t1: " << t1 << ", t2: " << t2 << endl;

  bool m1 = false, y1 = false;
  if (1 <= t1 && t1 <= 12) m1 = true;
  else y1 = true;
  
  bool m2 = false, y2 = false;
  if (1 <= t2 && t2 <= 12) m2 = true;
  else y2 = true;

  if (m1 && m2) {
      cout << "AMBIGUOUS" << endl;
  } else if (y1 && m2) {
      cout << "YYMM" << endl;
  } else if (m1 && y2) {
      cout << "MMYY" << endl;
  } else {
      cout << "NA" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <numeric>
#include <unordered_map>
#include <bitset>
#include <queue>

#ifdef WIN32
#define I64 "%I64d"
#else
#define I64 "%lld"
#endif
#define speed() ios_base::sync_with_stdio(0), cin.tie()
#define pb push_back
#define mp make_pair
#define y1 y1asd
#define F first
#define S second
#define all(s) (s).begin(), (s).end()
#define sqr(xx) ((xx)*(xx))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
const int inf = (1 << 30) - 1;
const int sz = (int)2e5 + 5;
const double eps = 1e-7;

ll s, x, n, ans;
char a[666][666];
ll p[11111], w[666][666], r[666][666];

inline char get(int x, int y, int A, int B) {
    x += A;
    y += B;
    if (x >= n) x -= n;
    if (y >= n) y -= n;
    return a[x][y];
}

ll get1(ll x, ll l, ll R) {
    ll res = (r[x][R] - (l ? r[x][l - 1]:0)) * p[700 - R] % mod;
    if (res < 0) res += mod;
    return res;
}

ll get2(ll x, ll l, ll r) {
    ll res = (w[r][x] - (l ? w[l - 1][x]:0)) * p[700 - r] % mod;
    if (res < 0) res += mod;
    return res;
}

void solve() {
    cin >> n;
    p[0] = 1;
    for (int i = 1; i <= 700; i++) p[i] = (p[i - 1] * 31) % mod;
    for (int i = 0; i < n + n; i++) {
        for (int j = 0; j < n + n; j++) {
            int x = i % n, y = j % n;
            if (i < n && j < n) {
                cin >> a[x][y];
                a[x][y] -= 'a' - 1;
            } else {
                a[i][j] = a[x][y];
            }
        }
    }
    for (int i = 0; i < n + n; i++) {
        for (int j = 0; j < n + n; j++) {
            r[i][j] = ((j ? r[i][j - 1] : 0) + p[j] * a[i][j]) % mod;
            w[i][j] = ((i ? w[i - 1][j] : 0) + p[i] * a[i][j]) % mod;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int f = 1;
            for (int c = 0; c < n; c++) {
                ll h1 = get1(i + c, j, j + n - 1), h2 = get2(j + c, i, i + n - 1);
                f &= h1 == h2;
            }
            ans += f;
        }
    }

    cout << ans;
}

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


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

typedef long long int ll;
ll powk(ll a, ll n = 2){
    ll r = 1;
    for(ll i = 0;i < n;i++){
        r *= a;
    }

    return r;
}


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

    string ans;
    ll t = 26;
    while(n >= 1)
    {
        ll x = n % t;
        if(x == 0){
            x = 26;
            n -= 26;
        }
        ans.push_back((char)('a' + x - 1));
        n /= t;
    }

    reverse(ans.begin(),ans.end());

    cout << ans;

    return 0;
}

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

typedef pair<int, int> P;

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( a > b ) { a = b; return 1; } return 0; }

const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
  int N, v, p, sum;
  while( cin >> N >> v >> p, N ){
    sum = 0;
    vector<int> x( N );
    REP( i, N ){
      cin >> x[i];
      sum += x[i] * 100;
    }
    sum = sum * ( 100 - p ) / 100;

    if( x[v - 1] ) cout << sum / x[v - 1] << endl;
    else       cout << 0 << endl;
  }

}


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

typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7;
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define f first
#define s second

ll N,K;
ll M;
ll Y[100005];
ll SY[100005];
P X[100005];
ll ans;

string S;

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>K>>S;

ll j=0;
char c=S[0];
rep(i,S.size()){
	if(S[i]!=c){
		j++;
		c=S[i];
	}
	Y[j]++;
}

SY[0]=Y[0];
rep1(i,j+1){
	SY[i]=SY[i-1]+Y[i];
}

rep(i,j+1){
	if(S[SY[i]-1]=='0'){
		if(i==0) X[M].f=0;
		else if(i==1) X[M].f=0;
		else X[M].f=SY[i-2];

		if(i==j) X[M].s=SY[i]-1;
		else X[M].s=SY[i+1]-1;
		M++;
	}
}

rep(i,M-K+1){
	ll chk=X[i+K-1].s-X[i].f+1;
	ans=max(ans,chk);
}

if(K>=M){
	cout<<N<<endl;
}else{
	cout<<ans<<endl;
}

}
	


Measured memory_bytes: 2768
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll Mid(ll(a), ll(b), ll(c)) {
	return a+b+c-Max(a,b,c)-Min(a,b,c);
}

int gcd(ll(a), ll(b)) {
	ll c = a;
	while (a % b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return b;
}



int main() {
	string S;
	cin >> S;
	stack<char> an;
	rep(i, S.size()) {
		if (S.at(i) == 'S') {
			an.push('S');
		}
		else {
			if (an.size() == 0 || an.top() == 'T') {
				an.push('T');

			}
			else {
				an.pop();
			}
		}
	}

	cout << an.size() << endl;
}

Measured memory_bytes: 644
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    
    int a, b;
    cin >> a >> b;
    if(a < b ){
        REP(i, b) cout << a ;
    }
    else REP(i, a) cout << b;

    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
vector <int> v(100005);
int dp[100005];
int solve(int i){
    if(i==n){
        return 0;
    }
    if(i>n){
        return 2e9;
    }
    if(dp[i]!=-1){
        return dp[i];
    }
    int q = min(abs(v[i]-v[i+1])+solve(i+1), abs(v[i]-v[i+2])+solve(i+2));
    dp[i]=q;
    return q;
}
void initialize(){
    for(int i=0; i<100005;i++){
        dp[i]=-1;
    }
}
int main(){
    initialize();
    cin>>n;
    for(int i=1; i<=n;i++){
        cin>>v[i];
    }
    cout<<solve(1)<<endl;
}


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

using namespace std;

int a[10010];
int g[110][110];

int main()
{
	int h , w;
	cin >> h >> w;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	int x = 1;
	for(int i = 1; i <= h; i++)
	{
		if(i % 2 == 1)
		{
			for(int j = 1; j <= w; j++)
			{
				if(a[x] > 0)
				{
					g[i][j] = x;
					a[x]--;
				}
				else
				{
					x++;
					g[i][j] = x;
					a[x]--;
				}
			}
		}
		else
		{
			for(int j = w; j > 0; j--)
			{
				if(a[x] > 0)
				{
					g[i][j] = x;
					a[x]--;
				}
				else
				{
					x++;
					g[i][j] = x;
					a[x]--;
				}
			}
		}
	}
	for(int i = 1; i <= h; i++)
	{
		for(int j = 1; j <= w; j++)
		{
			cout << g[i][j] << " ";
		}
		cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
using namespace std;
const long long inf = 1LL<<55;
const int NODE = 210;
int main()
{
  int n,m;
  while(cin>>n>>m&&n&&m){
    long long sea[n][n];
    long long land[n][n];
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        if( i!=j ){
          sea[i][j]=land[i][j]=inf;
        }else{
          sea[i][j]=land[i][j]=0;
        }
      }
    }
    for(int i = 0; i < m; ++i){
      int x,y;
      long long t;
      char sl;
      cin >> x >> y >> t >> sl;
      --x;
      --y;
      if( sl == 'S' ){
        sea[x][y]=min(sea[x][y],t);
        sea[y][x]=min(sea[y][x],t);
      }else{
        land[x][y]=min(land[x][y],t);
        land[y][x]=min(land[y][x],t);
      }
    }
    for(int k=0;k<n;++k){
      for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
          sea[i][j]=min(sea[i][j],sea[i][k]+sea[k][j]);
          land[i][j]=min(land[i][j],land[i][k]+land[k][j]);
        }
      }
    }

    int R;
    int cur,ship;
    int prez,z;
    long long preA[n][n];
    long long A[n][n];
    
    cin >> R;
    cin >> z;
    --z;
    cur = ship = z;
    for(int j = 0; j < n; ++j){
      for(int k = 0; k < n; ++k){
        preA[j][k] = A[j][k] = inf;
      }
    }
    A[cur][ship] = 0;
    for(int i = 1; i < R; ++i){
      for(int j = 0; j < n; ++j){
        for(int k = 0; k < n; ++k){
          preA[j][k] = A[j][k];
          A[j][k] = inf;
        }
      }
      prez = z;
      cin >> z;
      --z;
      for(int j = 0; j < n; ++j){
        A[z][j] = min( A[z][j], preA[prez][j] + land[prez][z]);
        for(int k = 0; k < n; ++k){
          A[z][k] = min( A[z][k], preA[prez][j] + land[prez][j] + sea[j][k] + land[k][z] );
          //cout << z << ' ' << k << ' ' << A[z][k] << endl;
        }
      }
    }
    long long res = inf;
    for(int i = 0; i < n; ++i){
      res = min( res, A[z][i] );
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 2116
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int N, i;
  int ret = 0;
  cin >> N;
  int s[101];
  for (i=0;i<N;++i){
    cin >> s[i];
  }
  sort(s, s+N);
  for (i=N-1;i>=0;i-=2){
    int A_point = s[i];
    int B_point = (i-1>=0) ? s[i-1] : 0;
    ret += (A_point - B_point);
  }
  cout << ret;
  
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int a[maxn],to[maxn],from[maxn];
queue<int> que;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    ll ans=0;
    to[1]=1; from[1]=1;
    que.push(1);
    for(int i=2;i<=n;i++)
    {
        int top=que.front();
        que.pop();
        ans+=(ll)a[top];
        to[i]=to[top]; from[to[top]]=i;
        from[i]=top; to[top]=i;
        que.push(i);
        que.push(top);
        a[top]=a[i];
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 6808
n = int(input())
sn = input()
sr = ''.join(list(reversed(sn)))
sint = int(sn, 2)
spop = sn.count('1')

def f(x):
    count = 0
    while x != 0:
        count += 1
        pop = bin(x).count('1')
        x %= pop
    return count



m1 = sint % (spop + 1)
m2 = 0 if spop <= 1 else sint % (spop - 1)

a = [0] * n
for i in range(n):
    if sr[i] == '0':
        d = pow(2, i, spop + 1)
        m = (m1 + d) % (spop + 1)
        a[i] = f(m) + 1
    elif spop != 1:
        d = pow(2, i, spop - 1)
        m = (m2 - d + spop - 1) % (spop - 1)
        a[i] = f(m) + 1
    else:
        a[i] = 0

for ans in reversed(a):
    print(ans)


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

typedef struct {
	int key, id;
} data;

void merge_sort(data x[], int n)
{
	static data y[100001] = {};
	if (n == 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

typedef struct {
	int *par, *size, *max;
} UF_forest;

void UF_initialize(UF_forest *F, int n)
{
	int i;
	F->par = (int*)malloc(sizeof(int) * (n + 1));
	F->size = (int*)malloc(sizeof(int) * (n + 1));
	F->max = (int*)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) {
		F->par[i] = i;
		F->size[i] = 1;
		F->max[i] = i;
	}
}

void UF_merge(UF_forest *F, int u, int v)
{
	for (; F->par[u] != u; u = F->par[u]);
	for (; F->par[v] != v; v = F->par[v]);
	if (u == v) return;
	else if (F->size[u] > F->size[v]) {
		F->par[v] = u;
		F->size[u] += F->size[v];
		F->max[u] = (F->max[u] < F->max[v])? F->max[v]: F->max[u];
	} else {
		F->par[u] = v;
		F->size[v] += F->size[u];
		F->max[v] = (F->max[u] < F->max[v])? F->max[v]: F->max[u];
	}
}

int UF_root(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return v;
}

int UF_size(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return F->size[v];
}

int UF_max(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return F->max[v];
}

int main()
{
	int i, N, M;
	data d[100001];
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++) scanf("%d %d", &(d[i].id), &(d[i].key));
	merge_sort(d, N);
	
	int ans = 0, tmp;
	UF_forest F;
	UF_initialize(&F, M + 1);
	for (i = N - 1; i >= 0; i--) {
		if (d[i].id > M) continue;
		tmp = UF_max(&F, d[i].id);
		if (tmp <= M) {
			ans += d[i].key;
			UF_merge(&F, d[i].id, tmp + 1);
		}
	}
	
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 4424
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
typedef long long ll;
int main(){
    string s;
    cin >> s;
    bool ans = false;
    REP(i,s.length()-1){
        if(s.substr(i,2) == "AC") ans = true;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
use std::io;
use std::cmp;


fn main() {
    let (n, t) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    let tn = read::<usize>();

    let mut ans = t;
    for i in 1..n {
        ans += cmp::min(t, tn[i] - tn[i - 1]);
    }

    println!("{}", ans);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

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

int main(){
  int m = 0;
  char s[2000000];
  char t[2000000];
  
  scanf("%s",s);
  scanf("%s",t);
  
  int n = strlen(s);
  
  for(int i=0;i<n;i++){
    if(s[i]!=t[i]){
      m+=1;
    }
  }
  printf("%d\n",m);
  return 0;
}
    

Measured memory_bytes: 2088
// skip until line 65
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

#define BR "\n"
#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a, b) ((((a) % (b) ) + (b)) % (b))
#define MO(a) AS_MOD(a,mod)
#define FEACH(it, cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it, cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)
#define MIN(V, T) V=min(V,T)

#define DumpArray(cont, from, to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

/*
 * ***_bound(6)
 * 5 6 6 6 6 6 7 7 7
 *   ^lower    ^upper
 * void reverse(c.begin(), c.end())
 *
 * graph
 * seg tree
 * dp
 * brute force
 */
struct Comparator{
    int operator()(int l, int r) const {
        return r<l;
    }
};
struct Vec;
//set<int, Comparator> S;

// solution below
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
int main() {
    cout.precision(15);
    cout << fixed;
    vector<ll> facs(1000100,0);
    ll N;
    cin >> N;
    {
        ll t=N;
        for(ll i=2;i<1000*1000+10;++i) {
            while(t%i==0) {
                t/=i;
                facs[i]++;
            }
        }
        if (t>=1000*1000+10&&N!=1) {
            facs[1000*1000+3]=1;
        }
    }
    ll ans=0;
    for(ll i=2;i<1000*1000+10;++i) {
        for(ll v=1;v<50;++v) {
            if ((1+v)*v/2 <= facs[i] && facs[i]<(1+v)*(2+v)/2) {
                ans+=v;
                break;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 11004
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int n;
vector<ll> a(410),sum(410,0);
vector<vector<ll>> dp(410,vector<ll>(410,-1));

ll dfs(int l,int r){
  if(dp[l][r]!=-1) return dp[l][r];
  if(l==r) return dp[l][r]=0;
  ll ret=inf;
  FOR(i,l,r){
    ret=min(ret,dfs(l,i)+dfs(i+1,r)+sum[r]-sum[l-1]);
  }
  return dp[l][r]=ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    FOR(i,1,n+1){
      cin>>a[i];
      sum[i]=sum[i-1]+a[i];
    }
    cout<<dfs(1,n)<<endl;
}

Measured memory_bytes: 1664
N,M=map(int,input().split())
AB=[]
for i in range(N):
    A,B=map(int,input().split())
    AB.append([A,B])
AB.sort()
money=0
for i in AB:
    a=i[0]
    b=i[1]
    for j in range(b):
        money+=a
        M-=1
        if M==0:
            break
    if M==0:
        break
print(money)

Measured memory_bytes: 59096
#include <iostream>
using namespace std;
int n, out = 0, x[8][8] = {}, f[8] = {};
void search(int s, int c) {
  if (c == n) {
    out++;
    return;
  }
  for (int i = 1; i < n; i++) {
    if (x[s][i] == 1 && f[i] == 0) {
      f[i] = 1;
      search(i, c + 1);
      f[i] = 0;
    }
  }
  return;
}

int main() {
  int m;
  cin >> n >> m;
  for (int i = 0, a, b; i < m; i++) {
    cin >> a >> b;
    x[a - 1][b - 1] = 1;
    x[b - 1][a - 1] = 1;
  }
  search(0, 1);
  cout << out << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string p;
  map<char, int> counter;

  while (true) {
    getline(cin, p);
    if (p.empty()) break;
    
    for (auto e : p) {
      counter[tolower(e)] += 1;
    }
  }
  char str;
  for (int i = 0; i < 26; i++) {
    str = 'a' + i;
    cout << str << " : " << counter['a' + i] << endl;
  }
}



Measured memory_bytes: 3164
import java.util.Scanner;
class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = 1;
        int y = 1;
        while (x!=0 || y!=0) {
        	x = sc.nextInt();
        y = sc.nextInt();
        if (x == 0 && y == 0) break;
        if (x > y) {
            System.out.println(y+" "+x);
        } else {
            System.out.println(x+" "+y);
        }
        }
    }
}


Measured memory_bytes: 35764