akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<P,P> PP;
const ll MOD=1000000007;
const ll INF=1000000010;
const int MAX=100011;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
vector<int> G[MAX];
int dfs(int v){
	vector<int> a;
	for(int i=0;i<G[v].size();i++){
		a.push_back(dfs(G[v][i]));
	}
	sort(all(a));
	int ma=1;
	for(int i=0;i<a.size();i++){
		ma=max(ma,a[i]+(int)a.size()-i);
	}
	return ma;
}
int main(){
	int n;cin>>n;
	for(int i=2;i<=n;i++){
		int a;cin>>a;
		G[a].push_back(i);
	}
	cout<<dfs(1)-1<<endl;
	return 0;
}


Measured memory_bytes: 13568
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


template< typename T >
struct SparseTable {
  vector< vector< T > > st;
  vector< int > lookup;

  SparseTable(const vector< T > &v) {
    int b = 0;
    while((1 << b) <= v.size()) ++b;
    st.assign(b, vector< T >(1 << b));
    for(int i = 0; i < v.size(); i++) {
      st[0][i] = v[i];
    }
    for(int i = 1; i < b; i++) {
      for(int j = 0; j + (1 << i) <= (1 << b); j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for(int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  inline T rmq(int l, int r) {
    int b = lookup[r - l];
    return min(st[b][l], st[b][r - (1 << b)]);
  }
};

int n;
bool f(int k,SparseTable<int> &st,vector<int> &a){
    unordered_map<int,P> ma;
    int bf = 0;
    for (int i = 0; i < n; i++) {
        int t = a[i];
        if(ma.find(t) != ma.end()){
            if(st.rmq(ma[t].sc,i) < t) ma[t] = mp(0,i);
        }
        if(t < bf && ma[t].fs == 0) ma[t] = mp(1,i); 
        ma[t].fs++;
        ma[t].sc=i;
        while(ma[t].fs == k + 1){
            ma[t].fs = 1;
            if(ma.find(t-1) != ma.end()){
                if(st.rmq(ma[t-1].sc,i) < t - 1) ma[t - 1] = mp(1,i);
                else ma[t - 1].sc = i;
            }
            else ma[t - 1] = mp(1,i);
            ma[t-1].fs++;
            t--;
            if(t<=0||k==1) return false;
        }
        bf = a[i];
    }
    return true;
};

int main(){
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d",&a[i]);
    }
    SparseTable<int> st(a);
    int l = 0, r = INF;
    while(abs(r - l) > 1){
        int m =  l + (r - l) / 2;
        if(f(m,st,a)) r = m;
        else l = m;
    }
    cout << r << endl;
    return 0;
}


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

int main() {
	//input
	int K;
	cin >> K;

	vector<int> U(32);
	U[0] = 1;
	U[1] = 1;
	U[2] = 1;
	U[3] = 2;
	U[4] = 1;
	U[5] = 2;
	U[6] = 1;
	U[7] = 5;
	U[8] = 2;
	U[9] = 2;
	U[10] = 1;
	U[11] = 5;
	U[12] = 1;
	U[13] = 2;
	U[14] = 1;
	U[15] = 14;
	U[16] = 1;
	U[17] = 5;
	U[18] = 1;
	U[19] = 5;
	U[20] = 2;
	U[21] = 2;
	U[22] = 1;
	U[23] = 15;
	U[24] = 2;
	U[25] = 2;
	U[26] = 5;
	U[27] = 4;
	U[28] = 1;
	U[29] = 4;
	U[30] = 1;
	U[31] = 51;

	//output
	cout << U[K - 1] << endl;


	return 0;
}


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

#define ll long long int
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MOD = 1e9 + 7;
typedef unsigned long long u64;

int main()
{
    IOS;
    int t=1;
    //cin >> t;
    while (t--)
    {
        ll a,b,n;
        cin>>a>>b>>n;
        ll minm=min(b,n);
        ll x=-1;
        if(minm==b)
        {
            x=b-1;
            ll diff=(a*x)/b;
            cout<<diff<<endl;
        }
        else
        {
            x=n;
            ll diff=(a*x)/b;
            cout<<diff<<endl;
        }
    }
    return 0;
}


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

int main(void){
  int x,y,f0,f1,f;
  int swx,swy,nex,ney,col;
  int dir; // E>N>W>S>E...
  
  swx=swy=0; nex=ney=1;
  col = 0; dir = 0;
  cin >> x >> y;
  f0 = 0; f1 = 1;
  while(1){
    //cout << "("<<swx<<","<<swy<<")-("<<nex<<","<<ney<<"): "<<col+1<<endl;
    if (swx<=x && x<nex && swy<=y && y<ney){
      cout << col+1 << endl;
      break;
    }
    // expand
    f = f0+f1;
    switch(dir){
      case 0: nex += f; break;
      case 1: ney += f; break;
      case 2: swx -= f; break;
      case 3: swy -= f; break;
    }
    col = (col+1)%3;
    dir = (dir+1)%4;
    f0=f1; f1=f;
  }
  return 0;
}


Measured memory_bytes: 3112
def otoshidama(N, Y):
        y = Y/1000
    
        for a in range(int(y/10)+1, -1, -1):
            for b in range(N - a, -1, -1):
                c = N - a - b
                if 10*a + 5*b + c == y:
                    return a, b, c


        return -1, -1, -1
    
if __name__ == '__main__':
    N, Y = map(int,input().split())
    a, b, c = otoshidama(N, Y)
    print(a, b, c)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;


int main() {
    int a, b;

    cin >> a >> b;

    
    cout << a / b << " " << a % b << " " << fixed << setprecision(8) << static_cast<double>(a) / static_cast<double>(b) << endl;

    return 0;
} 

Measured memory_bytes: 3292
import sys

def triangle_check(a, b, c):
    e1, e2, e3 = sorted([a, b, c], reverse=True)
    if e1 <= 0 or e2 <= 0 or e3 <= 0: return 0
    if e1 > e2 + e3: return 0
    if e1**2 == e2**2 + e3**2: return 1
    elif e1**2 < e2**2 + e3**2: return 2
    elif e1**2 > e2**2 + e3**2: return 3

ans = [0 for i in range(4)]

lines = sys.stdin.readlines()
for line in lines:
    a, b, c = list(map(int, line.split(' ')))
    rst = triangle_check(a, b, c)
    if rst == 0:
        print(' '.join(list(map(str, ans))))
        break
    ans[0] += 1
    ans[rst] += 1


Measured memory_bytes: 5644
#include <stdio.h>

#define N 1000
#define MAX 1000000

 int main(){
   int n, i, j, u, k, v, min;
    int d[N], c[N], g[N][N];
      
    scanf("%d", &n);
      
    for( i = 0; i < n; i++){
        for( j = 0; j < n; j++){
            g[i][j]=MAX;
        }
    }
      
    for( i = 0; i < n; i++){
        d[i] = MAX;
        c[i] = 0;
        scanf("%d%d", &u, &k);
        for( j = 0; j < k; j++){
            scanf("%d", &v);
            scanf("%d", &g[u][v]);
        }
    }
    
	d[0] = 0;
      
    while(1){
      
	  min=MAX;
        
	for(i=0;i<n;i++){
        
	    if(d[i]<min && c[i]==0){
                min=d[i];
                u=i;
            }
        }
          
        if( min == MAX)break;
        c[u] = 1;
          
     for( v = 0; v < n; v++){
            if( d[v] > d[u] + g[u][v]){
                d[v] =d [u] + g[u][v];
            }
        }
    }
    for(i = 0;i < n; i++){
        printf("%d %d\n", i, d[i]);
    }
    return 0;
}

Measured memory_bytes: 996
#include<stdio.h>
int main(){
	int n;
  scanf("%d",&n);
  int sum=0;
  int m=n;
  while(m!=0){
   sum+=m%10;
    m/=10;
  }
  if(n%sum==0){
    puts("Yes");
  }else{
      puts("No");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<fstream>
#include<string.h>
using namespace std;
string s;
int main(){
	cin>>s;
	for(int i=0;i<=s.length()-9;i++){
		cout<<s[i];
	}
	return 0;
}
/*

in:
YAKINIKUFESTIVAL

out:
YAKINIKU

*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll ans=INF;
	for(ll i=1;i<=sqrt(n);i++){
		if(n%i==0){
			ans=min(ans,n/i+i-2);
		}
	}
	cout <<ans;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int a, b, c;

int main() {
	scanf("%d %d %d", &a, &b, &c);
int t;
	if(a>b)t=a,a=b,b=t;
	if(b>c)t=b,b=c,c=t;
	if(a>b)t=a,a=b,b=t;
	printf("%d %d %d\n", a, b, c);
	return 0;
}


Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
const int mod = 1e9+7;
int a[N];
int b[N];
int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	for(int i=1;i<=n;i++) {
		cin>>b[i];
	}
	reverse(b+1,b+1+n);
	vector<int>p,q;
	int val=0,cnt=0;
	for(int i=1;i<=n;i++) {
		if(a[i]!=b[i]) continue;
		cnt++;
		p.push_back(i);
		val = b[i]; 
	}
	for(int i=1;i<=n;i++) {
		if(!cnt)break;
		if(a[i]==b[i]) {
			continue;
		}
		if(a[i]!=val&&b[i]!=val) {
			cnt--;
			q.push_back(i);
		}
	}
	if(cnt)  {
	cout<<"No"<<endl;
	return 0;
}
	for(int i=0;i<q.size();i++) {
		swap(b[p[i]],b[q[i]]);
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++) {
		cout<<b[i]<<" ";
	}
	
	return 0;
}

Measured memory_bytes: 5892
#include <stdio.h>
int main()
{
	int H,A;
	scanf("%d%d",&H,&A);
	H%A<=0?printf("%d",H/A):printf("%d",H/A +1);//kalo yang pertama kondisi contoh 10/5 jdi habis kalo kondisi kedua contoh 10/4 jdi sisa dan harus ditambah 1 kali atatck
	return 0;
}


Measured memory_bytes: 3216
N = int(input())
H = list(map(int,input().split()))
A = []
while sum(H)>0:
    hmin = 101
    cur = 0
    for i in range(N):
        h = H[i]
        if h>0:
            hmin = min(hmin,h)
        elif hmin<=100:
            A.append(hmin)
            for j in range(cur,i):
                H[j] -= hmin
            cur = i+1
            hmin = 101
        else:
            cur = i+1
    if cur<N:
        A.append(hmin)
        for j in range(cur,N):
            H[j] -= hmin
        hmin = 101
print(sum(A))

Measured memory_bytes: 39152
#include<stdio.h>
int main()
{
    char str[101];
    int flag=0;

    scanf("%s",str);

    for(int i=0;str[i]!='\0';i+=2)
    {
        if(str[i]=='L')
            flag++;
    }
    for(int i=1;str[i]!='\0';i+=2)
    {
        if(str[i]=='R')
            flag++;
    }

    if(flag==0)
        printf("Yes");
    else
        printf("No");

}


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

int a, b, c, x, ans = 0; 

int main()
{
	scanf("%d %d %d %d", &a, &b, &c, &x);
	for(int i = 0; i <= a; i++){
		for(int j = 0; j <= b; j++){
			for(int k = 0; k <= c; k++){
				if(i * 500 + j * 100 + k * 50 == x)	ans++;
			}
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 128
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    AB = []
    for _ in range(M):
        a, b = map(int, readline().split())
        AB.append((a,b))
    ans = [N*(N-1)//2]
    for i in range(M-1,-1,-1):
        a,b = AB[i][0], AB[i][1]
        if uf.same(a-1,b-1):
            ans.append(ans[-1])
        else:
            tmp = ans[-1] - uf.size(a-1)*uf.size(b-1)
            ans.append(tmp)
            uf.union(a-1,b-1)
    for i in range(M-1,-1,-1):
        print(ans[i])
if __name__ == '__main__':
    main()

Measured memory_bytes: 23716
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <sstream>
using namespace std;

int main()
{
	int x, a;
	cin >> x >> a;
	if (x < a) {
	  	cout << 0 << endl;
	}
	else {
	  	cout << 10 << endl;
	}
	return(0);
}





Measured memory_bytes: 256
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k()
s = s()
r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r*g*b
for i in range(n-2):
    for j in range((n-i+1)//2):
        if s[i]!=s[i+j] and s[i+j]!=s[i+2*j] and s[i+2*j]!=s[i]:
            ans-=1

print(ans)


Measured memory_bytes: 10128
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

//ここから書き換える
		Scanner sc = new Scanner (System.in);
		
		String stationStr  = sc.next();
		String[] staArr = new String[3];
		boolean busFlg=false;
		String result;

		for(int i=0;i<3;i++){
			staArr[i]=stationStr.substring(i,i+1);
		}
		
		for(int i=0;i<2;i++){
			if(staArr[i].equals(staArr[i+1])){
				//隣の駅と一致したら何もしない
			}else{
				busFlg=true;
				break;
			}
		}


		result = (busFlg == true) ? "Yes" : "No";
		System.out.println(result);



//ここまで書き換える
	}
 
}

Measured memory_bytes: 23764
nums = input().split()
W = int( nums[0])
H = int( nums[1])
x = int( nums[2])
y = int( nums[3])
r = int( nums[4])
   
if (x - r) >= 0 and (x + r) <= W:
    if (y - r) >= 0 and (y + r) <= H:
        print( "Yes")
    else:
        print( "No")
else:
    print( "No")

Measured memory_bytes: 7712
#define MYDEBUG
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>
#include <unordered_map>

#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
using namespace std;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last)
			out << ",";
	}
	out << "]";
	return out;
}

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(a * b, c * d) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<map>
using namespace std;
int main(){
char c;
cin>>c;
if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
cout<<"vowel"<<endl;
}
else{
cout<<"consonant"<<endl;
}
}

Measured memory_bytes: 256
#include<math.h>
int count_common_circle_segment(int x1,int y1,int x2,int y2,int r){
	int x12=x2-x1;
	int y12=y2-y1;
	float d=fabs(-y12*x1+x12*y1)/hypot(x12,y12);
	int ip1=-x1*x12-y1*y12;
	int ip2=x2*x12+y2*y12;
	if(ip1>0&&ip2>0&&d<=r)
		if(d<r)
			return 2;
		else
			return 1;
	return 0;
}
int is_origin_inner_triangle(int x1,int y1,int x2,int y2,int x3,int y3){
	float o1,o2,o3;
	o1=(float)x2*y3-(float)y2*x3;
	o2=(float)x3*y1-(float)y3*x1;
	o3=(float)x1*y2-(float)y1*x2;
	return o1*o2>0&&o2*o3>0;
}
int main(){
	int x1,y1,x2,y2,x3,y3,x4,y4,r;
	int inner1,inner2,inner3;
	int common1,common2,common3;
	for(;scanf("%d%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4,&r),x1|y1;){
		x1-=x4,y1-=y4;
		x2-=x4,y2-=y4;
		x3-=x4,y3-=y4;
		inner1=x1*x1+y1*y1<=r*r;
		inner2=x2*x2+y2*y2<=r*r;
		inner3=x3*x3+y3*y3<=r*r;
		if(inner1&&inner2&&inner3){
			puts("b");
		}else if(!inner1&&!inner2&&!inner3){
			common1=count_common_circle_segment(x2,y2,x3,y3,r);
			common2=count_common_circle_segment(x3,y3,x1,y1,r);
			common3=count_common_circle_segment(x1,y1,x2,y2,r);
			if(common1==2||common2==2||common3==2){
				puts("c");
			}else if(common1==1||common2==1||common3==1){
				if(is_origin_inner_triangle(x1,y1,x2,y2,x3,y3))
					puts("a");
				else
					puts("c");
			}else{
				if(is_origin_inner_triangle(x1,y1,x2,y2,x3,y3))
					puts("a");
				else
					puts("d");
			}
		}else{
			puts("c");
		}
	}
	return 0;
}

Measured memory_bytes: 0
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    H=[int(_) for _ in input().split()]
    H[0]-=1
    for i in range(1,n):
        if H[i-1]<H[i]:H[i]-=1
        elif H[i-1]>H[i]:
            print("No")
            break
    else:print("Yes")
if __name__=='__main__':
    main()

Measured memory_bytes: 14396
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

int n;
int p[30]; //parent
int l[30]; //left
int r[30]; //right

void dfs(int n, int depth){ //calculate the depth
  if(p[n] == -1){ //if the node n does't have parent, that is root
    cout << "depth = " << depth << ", "; //a depth is a distance from root to node n 
    return ;
  }

  dfs(p[n], depth + 1); //if the node n isn't root, continue to search depth recursively
  return ;
}

int height(int i, int h){ //calculate height
  int hl = 0, hr = 0;

  if(l[i] == -1 && r[i] == -1) return h; //if the node i doesn't have a child, return the height
  if(l[i] != -1) hl = height(l[i], h + 1); //if the node i have a left child, search height recursively
  if(r[i] != -1) hr = height(r[i], h + 1); //if the node i have a right child, search height recursively

  return max(hl, hr); //return the largest value
}

void searchsibling(int i){
  if(p[i] == -1) cout << "sibling = " << -1 << ", "; //if the node i doesn't have parent, that node doesn't have sibling
  else if(l[p[i]] == i) cout << "sibling = " << r[p[i]] << ", "; //if the left child of parent of node i is i, sibling is right
  else cout << "sibling = " << l[p[i]] << ", "; //else sibling is left
}

void searchdegree(int i){
  if(l[i] == r[i]) cout << "degree = " << 0 << ", "; //if l[i] == r[i], or both value are -1, the node i doesn't have a child
  else if(l[i] == -1 || r[i] == -1) cout << "degree = " << 1 << ", "; //else if either l[i] or r[i] is -1, the node i have a child
  else cout << "degree = " << 2 << ", "; //else the node i have two children
}

void searchtype(int i){
  if(p[i] == -1) cout << "root"; //if the node i doesn't have parent, that node is root
  else if(l[i] == -1 && r[i] == -1) cout << "leaf"; //if l[i] == r[i] == -1, or the node i doesn't have a child, that is leaf
  else cout << "internal node"; //else the node i is internal node
}

void solve(){ //out put function
  for(int i = 0;i < n;i++){
    cout << "node " << i << ": ";
    cout << "parent = " << p[i] << ", ";
    searchsibling(i);
    searchdegree(i);
    dfs(i, 0);
    cout << "height = " << height(i, 0) << ", ";
    searchtype(i);
    cout << endl;
  }
}

int main(){

  //input
  cin >> n;
  for(int i = 0;i < n;i++) p[i] = l[i] = r[i] = -1;
  for(int i = 0;i < n;i++){
    int id, left, right;

    cin >> id >> left >> right;
    l[id] = left;
    r[id] = right;
    p[left] = p[right] = id;
  }

  //output
  solve();

  return 0;
}




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

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

	int a, b, c;
	cin >> a >> b >> c;
	swap(a,b);
	swap(a,c);
	cout << a << " " << b << " " << c;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int INF=1e9;
const int MOD=1e9+7;
const double pi=acos(-1);

int main(){
  int k;cin>>k;
  if(k==1 || k==2 || k==3||k==5||k==7||k==11||k==13||k==15||k==17||k==19||k==23||k==29||k==31)cout<<1<<endl;
  if(k==4||k==6||k==9||k==10||k==14||k==21||k==22||k==25||k==26)cout<<2<<endl;
  if(k==28||k==30)cout<<4<<endl;
  if(k==8||k==12||k==18||k==20||k==27)cout<<5<<endl;
  if(k==16)cout<<14<<endl;
  if(k==24)cout<<15<<endl;
  if(k==32)cout<<51<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
typedef long long ll;

int main() {
    int N;
    cin >> N;
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            if(i * j == N) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main(){
  char s[100000];
  scanf("%s",s);
  int count=0;
  int i;
  int len = strlen(s);
  for(i=1;i<len;i++){
    if(s[i-1] == s[i]){
      count++;
      if(s[i] =='1'){
        s[i] = '0';
      }
      else{
        s[i] = '1';
      }
      }
  }
  printf("%d\n",count);
}


Measured memory_bytes: 256
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
from datetime import datetime as dt

def main():
  n = int(readline())
  x = list(map(int, readline().split()))
  ave = int(sum(x)/n+0.5)
  ans = 0
  for i in range(n):
    ans += (x[i]-ave)**2
  print(ans)
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 5248
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FI first
#define SC second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const int LINF = 1e18;
const double EPS = 1e-9;
ll cnt = 0;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}


int main()
{
  double w, h, x, y ;
  cin >> w >> h >> x >> y ;
  int fl = 0 ;
  if(x==w/2 && y == h/2){
    fl = 1 ;
  }
  
  cout << setprecision(10) << w*h/2 << " " << fl <<endl ;


  return 0 ;
}




Measured memory_bytes: 256
n = int(input())
s = list(map(int, input()))
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p = 0
            while p < len(s) and s[p] != i: p += 1
            p += 1
            while p < len(s) and s[p] != j: p += 1
            p += 1
            while p < len(s) and s[p] != k: p += 1
            if p < len(s):
                ans += 1
print(ans)

Measured memory_bytes: 75396
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    string s;
    cin >> s;

    s[k - 1] += 'a' - 'A';

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <iomanip>
#include<queue>
#include<set>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
std::vector<T> enum_div(T n)//nの約数を列挙
{
	std::vector<T> ret;
	for(T i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}


int N;
string S;
vector<vector<int>> li;
vector<int> siz;
bool judge(int len){
	map<string,int> s;
	string now=S.substr(0,len);
	REP(i,0,N-len+1){
		if(s.find(now)!=s.end()){
			int t=s.find(now)->second;
			if(t+len<=i){
				return true;
			}
		}else{
			s[now]=i;
		}
		now=S.substr(i+1,len);
	}
	return false;
}


int main()
{
	ll T1,T2,A1,A2,B1,B2;
	cin>>T1>>T2>>A1>>A2>>B1>>B2;

	ll a=T1*(A1-B1);
	ll b=T2*(A2-B2);

	if(a==-b){
		cout<<"infinity"<<endl;
	}else{
		if(a>0){
			if(a+b>0){
				cout<<0<<endl;
			}else{
				if(b%(a+b)==0){
					ll n=b/(a+b);
					cout<<2*n-2<<endl;
				}else{
				ll n=b/(a+b);
				cout<<2*n-1<<endl;
				}
			}
		}else{
			if(a+b<0){
				cout<<0<<endl;
			}else{
				if(b%(a+b)==0){
					ll n=b/(a+b);
					cout<<2*n-2<<endl;
				}else{
				ll n=b/(a+b);
				cout<<2*n-1<<endl;
				}
			}
			
		}
		
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
#define LL long long
#define PAIR pair<LL,int>
using namespace std;
int main() {
	int N, M, K, S, P, Q;
	cin >> N >> M >> K >> S >> P >> Q;
	int *zombie;
	zombie = new int[K];
	short *danger;
	danger = new short[N + 1]{ 0 };
	for (int i = 0; i < K; ++i) {
		cin >> zombie[i];
		danger[zombie[i]] = 2;
	}
	vector<vector<int> > road(N+1);
	int a, b;
	for (int i = 0; i < M; ++i) {
		cin >> a >> b;
		road[a].push_back(b);
		road[b].push_back(a);
	}
	queue<int> date, stock;
	for (int i = 0; i < K; ++i) {
		date.push(zombie[i]);
	}
	int dummy;
	for (int i = 0; i < S; ++i) {
		while (!date.empty()) {
			dummy = date.front();
			date.pop();
			for (int m = road[dummy].size(), j = 0; j < m; ++j) {
				if (danger[road[dummy][j]] == 0) {
					danger[road[dummy][j]] = 1;
					stock.push(road[dummy][j]);
				}
			}
		}
		swap(date, stock);
	}
	LL inf = N*Q*2;
	PAIR *map;
	map = new PAIR[N + 1];
	for (int i = 1; i <= N; ++i) {
		map[i].first = inf;
		map[i].second = i;
	}
	bool *used;
	used = new bool[N + 1]{ false };
	map[1].first = 0;
	priority_queue<PAIR, vector<PAIR>, greater<PAIR> > que;
	que.push(map[1]);
	PAIR top;
	while (map[N].first == inf) {
		top = que.top();
		que.pop();
		if (used[top.second])continue;
		used[top.second] = true;
		for (int m = road[top.second].size(), i = 0; i < m; ++i) {
			if (danger[road[top.second][i]]==1) {
				if (!used[road[top.second][i]]) {
					map[road[top.second][i]].first = top.first + Q;
					que.push(map[road[top.second][i]]);
				}
			}
			else if (danger[road[top.second][i]] == 0) {
				if (!used[road[top.second][i]]) {
					map[road[top.second][i]].first = top.first + P;
					que.push(map[road[top.second][i]]);
				}
			}
		}
	}
	if (danger[N] == 1) {
		cout << map[N].first - Q << endl;
	}
	else {
		cout << map[N].first - P << endl;
	}
	return 0;
}

Measured memory_bytes: 11452
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int a, b;
    cin >> a >> b;
    if (a+b == 15) {
        cout << "+" << endl;
    } else if (a*b == 15) {
        cout << "*" << endl;
    } else {
        cout << "x" << endl;
    }
    return 0;
}


Measured memory_bytes: 3664
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    int l, r, d, cnt=0, i;
    
    scanf("%d%d%d", &l, &r, &d);
    
    for(i=l; i<=r; i++){
        if (i%d==0) {
            cnt++;
        }
    }
    
    printf("%d", cnt);
    
    return 0;
}



Measured memory_bytes: 1724
#include <stdio.h>

void sort(int A[], int n) {
    for (int i = 1; i < n; ++i) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = v;
    }
}

void print(int A[], int n) {
    for (int i = 0; i < n; ++i) {
        if (i == 0) printf("%d", A[i]);
        else
            printf(" %d", A[i]);
    }
}

int main() {
    int a, A[3];
    for (int i = 0; i < 3; ++i) {
        scanf("%d", &a);
        A[i] = a;
    }
    
    sort(A, 3);
    print(A, 3);
    printf("\n");
    return 0;
    
}


Measured memory_bytes: 2088
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	x=II()

	a=0

	for i in range(100000):
		a+=x
		if a%360==0:
			print(i+1)
			exit(0)





if __name__ == "__main__":
	main()


Measured memory_bytes: 62028
#include<bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string &s)
{
    return '"' + s + '"';
}

string to_string(const char *s)
{
    return to_string((string)s);
}

string to_string(bool b)
{
    return (b ? "true" : "false");
}

string to_string(vector<bool> v)
{
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v)
{
    string res = "";
    for (size_t i = 0; i < N; i++)
    {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

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

template <typename A, typename B>
string to_string(pair<A, B> p)
{
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << " " << to_string(H);
    debug_out(T...);
}

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair
#define fst first
#define snd second
#define fr(i, a, b) for(int i=a; i<b; i++)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int n; cin >> n;
    int all = 0;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i]; all ^= a[i];
    }
    for(int i=0; i<n; i++) {
        cout << (all ^ a[i]) << " \n"[i==n-1];
    }
}


Measured memory_bytes: 3924
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main()
{
    vector<bool> digit(10);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int now;
        cin >> now;
        digit.at(now) = true;
    }
    for (int i = n;; i++)
    {
        int now = i;
        bool ans = true;
        while (now != 0)
        {
            int next = now % 10;
            if (digit.at(next))
            {
                ans = false;
            }
            now /= 10;
        }
        if (ans)
        {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

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

const int N = 100010;
using pii = std::pair <int, int>;

int l[N], r[N];
pii p[N];
int suf[N];

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i){
        scanf("%d%d", &l[i], &r[i]);
    }
    int posl = std::max_element(l, l + n) - l;
    int posr = std::min_element(r, r + n) - r;
    if (posl == posr){
        int max = 0;
        for (int i = 0; i < n; ++ i){
            if (i == posl){
                continue;
            }
            max = std::max(max, r[i] - l[i] + 1);
        }
        max += r[posl] - l[posl] + 1;
        printf("%d\n", max);
        return 0;
    }
    int max = 0;
    int cnt = 0;
    int max1 = 0;
    for (int i = 0; i < n; ++ i){
        max = std::max(max, r[i] - l[i] + 1);
        if (i != posl && i != posr){
            p[cnt ++] = {l[i], r[i]};
            max1 = std::max(max1, r[i] - l[i] + 1);
        }
    }
    max = std::max(max, max1 + std::max(0, r[posr] - l[posl] + 1));
    std::sort(p, p + cnt);
    suf[cnt] = r[posl];
    for (int i = cnt - 1; i >= 0; -- i){
        suf[i] = std::min(suf[i + 1], p[i].second);
    }
    for (int i = 0; i < cnt; ++ i){
        max = std::max(max, std::max(0, suf[i + 1] - l[posl] + 1) + std::max(0, r[posr] - std::max(l[posr], p[i].first) + 1));
    }
    max = std::max(max, std::max(0, suf[0] - l[posl] + 1) + r[posr] - l[posr] + 1);
    printf("%d\n", max);
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
int read(){
	int sum=0,f=1;
	char s=getchar();
	while (s<'0' or s>'9'){
		if (s=='-')f=-1;
		s=getchar();
	}
	while (s>='0' and s<='9'){
		sum=sum*10+s-'0';
		s=getchar();
	}
	return sum*f;
}
int main(){
	int n=read(),x=read(),t=read();
	int sum=0;
	if (n%x)sum=n/x+1;
	else sum=n/x;
//	cout<<sum<<endl;
	sum*=t;
	cout<<sum<<endl;
	return 0;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	ll n;
	cin>>n;
	ll arr[n]={0};
	for(ll i=0;i<n;i++){
	    cin>>arr[i];
	}
	ll ans=0,cur_height=arr[0];
	for(ll i=1;i<n;i++){
	    if(arr[i] < cur_height){
	        ans += (cur_height - arr[i]);
	    }
	    if(arr[i] > cur_height){
	        cur_height=arr[i];
	    }
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 5140
#include<stdio.h>
int main(){
  char b;
  scanf("%c", &b);
  if(b == 'A'){
    printf("T");
  }
  if(b == 'C'){
    printf("G");
  }
  if(b == 'G'){
    printf("C");
  }
  if(b == 'T'){
    printf("A");
  }
  return 0;
}

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

int main() {
	long n,c,ans=0;
	cin >> n;
	for(long i=0; i<n; i++){
		cin >> c;
		while(c%2==0){
			c/=2;
			ans++;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    string s;
    cin >> s;
    int len = s.size();
    if (len%2 == 1) {
        cout << "No" << endl;
        return 0;
    } else {
        for (int i = 0; i < len-1; i += 2) {
            if (s[i] == 'h' && s[i+1] == 'i') {
            } else {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#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
#include <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

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

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }

    if (a.second != b.second) {
        return a.second > b.second;
    }
    else {
        return true;
    }
}

int main()
{
    vector<int> x(4), y(4);

    cin >> x[0] >> y[0] >> x[1] >> y[1];

    x[2] = x[1] - (y[1] - y[0]);
    y[2] = y[1] + x[1] - x[0];
    x[3] = x[2] - (y[2] - y[1]);
    y[3] = y[2] + x[2] - x[1];

    cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3] << endl;
}

Measured memory_bytes: 256
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code
)]
//use proconio::fastout;
use proconio::{input,marker::*};
//use std::collections::*;
use std::cmp::*;

fn main() {
  input! {
    N:i64,X:i64,T:i64
  }
  
  println!("{}", (N + (X-1))/X * T);
}


Measured memory_bytes: 2096
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <stack>

const int MOD = 1e9 + 7;
const int iINF = 100000000;
const long long int llINF = 1 << 30;
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct
{
    int to;
    int cost;
};

vector<edge> graph[1000000];
ll dist[1000000];

int V, E, start;

void bellman(int s)
{
    rep(i, V) dist[i] = llINF;
    dist[s] = 0;
    while (true)
    {
        bool update = false;
        rep(i, E)
        {
            for (auto e : graph[i])
            {
                if (dist[i] != llINF && dist[e.to] > dist[i] + e.cost)
                {
                    dist[e.to] = dist[i] + e.cost;
                    update = true;
                }
            }
        }

        if (!update)
            break;
    }
}

int main()
{

    cin >> V >> E >> start;
    rep(i, E)
    {
        int a, t, d;
        cin >> a >> t >> d;
        graph[a].push_back({t, d});
    }

    bellman(start);

    rep(i, V)
    {
        if (dist[i] != llINF)
            cout << dist[i] << endl;
        else 
            cout << "INF" << endl;
    }
    return 0;
}


Measured memory_bytes: 33784
#include <iostream>
#include <vector>
#define MOD 1000000007
#define REP(i,a,n)for(int i=(a);i<=(n);i++)
#define ADDMOD(a, b) (a)=((a)+(b))%MOD
using namespace std;
typedef pair<int, int> pii;

int N,M,L,R,X;
vector<pii> Q[301];
int dp[301][301][301];

bool check(int m, int i, int j) {
  for(pii p : Q[m]) {
    int l=p.first,x=p.second;
    bool bi=l<=i,bj=l<=j;
    if(x==1 && (bi || bj)) return false;
    if(x==2 && !(bi ^ bj)) return false;
    if(x==3 && (!bi || !bj)) return false;
  }
  return true;
}

int main(void) {
  cin>>N>>M;
  REP(i,1,M) {
    cin>>L>>R>>X;
    Q[R].push_back(pii(L,X));
  }

  REP(i,0,N) REP(j,0,N) REP(k,0,N) dp[i][j][k]=0;
  dp[0][0][0]=1;

  REP(i,0,N-1) REP(j,0,N-1) REP(k,0,N-1) if(dp[i][j][k] > 0) {
    int m=max(i,max(j,k))+1;
    if(check(m,j,k)) ADDMOD(dp[m][j][k], dp[i][j][k]);
    if(check(m,k,i)) ADDMOD(dp[i][m][k], dp[i][j][k]);
    if(check(m,i,j)) ADDMOD(dp[i][j][m], dp[i][j][k]);
  }

  long ans=0;
  REP(i,0,N-1) REP(j,0,N-1) {
    ADDMOD(ans, dp[N][i][j]);
    ADDMOD(ans, dp[i][N][j]);
    ADDMOD(ans, dp[i][j][N]);
  }
  cout<<ans<<endl;

  return 0;
}


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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int h, w, sx, sy, ex, ey;
	cin >> h >> w >> sx >> sy >> ex >> ey;
	sx--, sy--, ex--, ey--;
	vector<string> g(h);
	for (int i = 0; i < h; i++) cin >> g[i];
	
	vector<vector<int>> ans(h, vector<int>(w, 1e9));
	ans[sx][sy] = 0;
	deque<vector<int>> q;
	q.push_back({sx, sy});
	while (!q.empty()) {
		vector<int> cur = q.front();
		q.pop_front();
		for (int i = cur[0] - 1; i <= cur[0] + 1; i++) {
			for (int j = cur[1] - 1; j <= cur[1] + 1; j++) {
				if (i < 0 || j < 0 || i >= h || j >= w || (abs(cur[0] - i) + abs(cur[1] - j) != 1)) continue;
				if (g[i][j] != '#' && ans[i][j] > ans[cur[0]][cur[1]]) {
					ans[i][j] = ans[cur[0]][cur[1]];
					q.push_front({i, j});
				}
			}
		}
		for (int i = cur[0] - 2; i <= cur[0] + 2; i++) {
			for (int j = cur[1] - 2; j <= cur[1] + 2; j++) {
				if (i < 0 || j < 0 || i >= h || j >= w) continue;
				if (g[i][j] != '#' && ans[i][j] > ans[cur[0]][cur[1]] + 1) {
					q.push_back({i, j});
					ans[i][j] = ans[cur[0]][cur[1]] + 1;
				}
			}
		}
	}
	cout << (ans[ex][ey] == 1e9 ? -1 : ans[ex][ey]);
}


Measured memory_bytes: 9324
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;

int main(){
	unordered_map<char, int> memo;
	string s;
	cin>>s;
	for(int i = 0; i < s.size(); i++){
		memo[s[i]]++;
	}
	for(auto itr = memo.begin(); itr != memo.end(); ++itr){
		if(itr->second % 2 != 0){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
def shuffle(s, n)
  s[n..-1] + s[0..(n-1)]
end

loop do
  s = gets.chomp
  break if s == '-'
  m = gets.chomp.to_i
  m.times do
    n = gets.chomp.to_i
    s = shuffle(s, n)
  end
  puts s
end

Measured memory_bytes: 6100
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define mp make_pair
#define mt make_tuple
#define um unordered_map
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
using namespace std::chrono;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
void input(vector<int>&a,int n)
{
   rep(i,0,n-1)
   cin>>a[i];
}
void solve()
{
  int x1,x2,x3,x4,x5; cin>>x1>>x2>>x3>>x4>>x5; 
  if(x1==0) cout<<1<<"\n";
  else if(x2==0) cout<<2<<"\n";
  else if(x3==0) cout<<3<<"\n";
  else if(x4==0) cout<<4<<"\n";
  else cout<<5<<"\n";
  return; 
}
int main()
{
  #ifndef ONLINE_JUDGE
  auto start=high_resolution_clock::now();
  #endif
  ios_base::sync_with_stdio(false); 
  cin.tie(0);
  int t=1;
  while(t--)
  {
   solve();
  }
  #ifndef ONLINE_JUDGE
  auto stop=high_resolution_clock::now();
  auto duration=duration_cast<microseconds>(stop-start);
  cout<<"duration-> "<<duration.count()<<" microseconds\n";
  #endif
  return 0;
}

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

static const int MAX = 50;

int main() {
    int h, w;
    string S[MAX + 3];
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        cin >> S[i];
    }

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

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if(S[i][j] == '#') continue;

            int cnt = 0;

            for (int k = 0; k < 8; ++k) {
                int ni = i + dy[k];
                int nj = j + dx[k];

                if (ni < 0 or h <= ni) continue;
                if (nj < 0 or w <= nj) continue;

                if (S[ni][nj] == '#') cnt++;
            }

            S[i][j] = to_string(cnt)[0];

        }
    }
    for (int i = 0; i < h; ++i) {
        cout << S[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define MAX 101
#define INF (1<<21)

int n,bri[MAX][MAX];

void prim(){
  bool visit[MAX];
  int cost[MAX],d[MAX];

  for(int i = 0 ; i < n ; i++){
    visit[i] = false;
    cost[i] = INF;
  }

  cost[0] = 0;
  d[0] = -1;

  while(true){
    int u ,mincost = INF;
    for(int i = 0 ; i < n ; i++){
      if(!visit[i]&&cost[i] < mincost){
	mincost = cost[i];
	u = i;
      }
    }
    if(mincost == INF) break;
    visit[u] = true;

    for(int j = 0 ; j < n ; j++){
      if(visit[j] || bri[u][j] == INF) continue;
      if(bri[u][j] < cost[j]){
	cost[j] = bri[u][j];
	d[j] = u;
      }
    } 
  }

  int sum = 0;
  for(int i = 0 ; i < n ; i++){
    if(d[i] == -1) continue;
    sum += bri[i][d[i]];
  }

  cout << sum << endl;
}

int main(){
  int m,a,b,c;

  while(cin >> n >> m , n + m){
    for(int i = 0 ; i < MAX ; i++)
      for(int j = 0 ; j < MAX ; j++)
	bri[i][j] = INF;

    for(int i = 0 ; i < m ; i++){
	cin >> a >> b >> c;
	bri[a][b] = bri[b][a] = c;
    }

    prim();
  }

  return 0;
}

Measured memory_bytes: 1200
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int MOD=1000000007;
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k){
  // cerr<<n<<" C "<<k<<endl;
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  COMinit();
  int h,w,a,b;
  cin>>h>>w>>a>>b;
  int64_t result=0;
  int target_r=h-a-1,target_c=b;
  while(target_r>=0&&target_c<w){
    // cout<<COM(target_r+target_c,target_r)*COM(h-target_r-1+w-target_c-1,h-target_r-1)<<endl;
    result+=COM(target_r+target_c,target_r)*COM(h-target_r-1+w-target_c-1,h-target_r-1);
    target_r--;
    target_c++;
    result%=MOD;
  }
  cout<<result<<endl;



  return 0;
}


Measured memory_bytes: 12160