akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
struct Node{
  int depth;
  int height;
  int p;//parent
  int l,r;
  int id;
  int c;
} ;

int getHeight(int);

struct Node *tree;
int main(){
  
  int i,j,n,a,id,c,x,y,x1,x2;
  
  scanf("%d",&n);
  tree = malloc(sizeof(struct Node)*n);
  
  for(i=0;i<n;i++){
    tree[i].p = tree[i].l = tree[i].r = -1;
  }
  for(i=0;i<n;i++){
    scanf("%d",&id);
    tree[id].id = id;
    scanf("%d%d",&tree[id].l,&tree[id].r);
  }
  
  for(i=0;i<n;i++){//getChildren
    tree[i].c=0;
    if(tree[i].l != -1)tree[i].c++;
    if(tree[i].r != -1)tree[i].c++;
  }
  
  for(i=0;i<n;i++){//findParent
    for(j=0;j<n;j++){
      if(tree[i].id == tree[j].l)tree[i].p = tree[j].id;
      else if(tree[i].id == tree[j].r)tree[i].p = tree[j].id;
    }
  }
  
  for(i=0;i<n;i++){//getDepth
    x=0;
    y=i;
    while(tree[y].p>-1){
      y = tree[y].p;
      x++;
    }
    tree[i].depth = x; 
  }

  for(i=0;i<n;i++){//getHeight
    x1=0;
    y=i;
    while(tree[y].l>-1){
      y = tree[y].l;
      x1++;
    }

    x2=0;
    y=i;
    while(tree[y].r>-1){
      y = tree[y].r;
      x2++;
    }
    
    if(x1>=x2)tree[i].height = x1;
    else if(x1<x2)tree[i].height = x2;
  }

  for(i=0;i<n;i++)tree[i].height = getHeight(i);
  
  
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, ",i,tree[i].p);
    if (tree[i].p == -1)printf("sibling = -1, ");
    else if(tree[tree[i].p].l == i)printf("sibling = %d, ",tree[tree[i].p].r);
    else if(tree[tree[i].p].r == i)printf("sibling = %d, ",tree[tree[i].p].l);
    
    //getChildren;
    c=0;
    if(tree[i].l != -1)c++;
    if(tree[i].r != -1)c++;
    printf("degree = %d, ",c);
    
    printf("depth = %d, ",tree[i].depth);
    printf("height = %d, ",tree[i].height);
    
    
    
    
    if(tree[i].p == -1)printf("root");
    else if(tree[i].l == -1 && tree[i].r == -1)printf("leaf");
    else printf("internal node");
    printf("\n");
  }
  

  free(tree);
  
  
  return 0;
}

int getHeight(int i){
  int a=0,b=0;

  if(tree[i].l == -1 && tree[i].r == -1)return 0;
  else {
    if(tree[i].l != -1)a += getHeight(tree[i].l)+1;
    if(tree[i].r != -1)b += getHeight(tree[i].r)+1;
    if(a >= b) return a;
    else return b;
  }
}



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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    ll h,w;
    cin >> h >> w;
    vs s(h);
    rep(i,h)cin >> s[i];
    rep(i,h)cout << s[i] << endl << s[i] << endl;
    return 0;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define pr(a, b) pair<a, b>
#define si set<int>
#define sl set<long long>
#define pq prioirty_queue
#define all(v) v.begin(),v.end()
#define left (2*idx)+1
#define right (2*idx)+2
#define frt(i,a,b) for(int i=a; i<b; i++)
#define rew(i,a,b) for(int i=a; i>=b; i--)
#define fre(i,a,b) for(int i=a; i<=b; i++)
#define pb push_back

#define test if(true)

ll a[11][11];

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

    frt(i, 0, n)
    {
        frt(j, 0, d)
        {
            cin >> a[i][j];
        }
    }

    int cnt= 0;
    frt(i, 0, n)
    {
        frt(j, 0, i)
        {
            ll dst = 0;
            frt(k, 0, d)
            {
                dst = dst + ((a[i][k] - a[j][k])* (a[i][k] - a[j][k]));
            }

            ll tmp = sqrt(dst);
            if((tmp * tmp)== dst)
            {
                cnt+=1;
            }
        }
    }
    cout << cnt << "\n";

    
    return 0;
}

Measured memory_bytes: 256
# Problem: https://atcoder.jp/contests/abc051/tasks/abc051_b
# Python  3rd Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solver(maxNum, totalNum):
    result = 0
    for x in range(0,maxNum+1):
        for y in range(0,maxNum+1):
            z = totalNum - x - y
            if 0 <= z and z <= maxNum:
                result = result + 1
    return result


if __name__ == "__main__":
    K, S = MI()
    print("{}".format(solver(K, S)))


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
    char text [205];
    int length, i;

    fgets(text, 201, stdin);
    length = strlen(text) - 1;
    
    for(i = 0; i < length; i++){
        if(isalpha(text[i]) && islower(text[i])){
            text[i] = toupper(text[i]);
        }    
    }

    printf("%s", text);

    return (0);
}


Measured memory_bytes: 2044
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string s; vector<int> v;
string Letter(int, int);
string String(int, int);
string Cipher(int, int);
string Letter(int l, int r) {
	string ret(1, s[r - 1]);
	for (int i = l; i < r - 1; i++) {
		if (s[i] == '+') ret[0] = (ret[0] - 65 + 1) % 26 + 65;
		if (s[i] == '-') ret[0] = (ret[0] - 65 + 25) % 26 + 65;
	}
	return ret;
}
string String(int l, int r) {
	if (s[l] == '[') {
		string ret = Cipher(l + 1, r - 1);
		reverse(ret.begin(), ret.end());
		return ret;
	}
	return Letter(l, r);
}
string Cipher(int l, int r) {
	string ret;
	int d = 0, pl = l;
	for (int i = l; i < r; i++) {
		if (s[i] == '[') d++;
		if (s[i] == ']') {
			d--;
			if (d == 0) {
				ret += String(pl, i + 1);
				pl = i + 1;
			}
		}
		if (d == 0 && 'A' <= s[i] && s[i] <= 'Z') {
			ret += String(pl, i + 1);
			pl = i + 1;
		}
	}
	return ret;
}
string solve(int pos, string t) {
	if (pos == v.size()) {
		s = t;
		return Cipher(0, s.size());
	}
	string ret = "~";
	for (int i = 0; i < 26; i++) {
		t[v[pos]] = i + 65;
		ret = min(ret, solve(pos + 1, t));
	}
	return ret;
}
int main() {
	string t;
	while (cin >> t, t != ".") {
		v.clear();
		for (int i = 0; i < t.size(); i++) {
			if (t[i] == '?') v.push_back(i);
		}
		cout << solve(0, t) << endl;
	}
	return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
double dp[305][305][305];
int n,a[3];
double rec(int a,int b,int c){
	if(dp[a][b][c] >= -1e16) return dp[a][b][c];
	if(a+b+c == 0) return 0.0;
	double sum = 0;
	if(a) sum += (double)(a)/(double)(a+b+c)*rec(a-1,b,c);
	if(b) sum += (double)(b)/(double)(a+b+c)*rec(a+1,b-1,c);
	if(c) sum += (double)(c)/(double)(a+b+c)*rec(a,b+1,c-1);
	sum += 1.0*(double)(n)/(double)(a+b+c);
	return dp[a][b][c] = sum;
}
int main(){
	cin>>n;
	for(int i=0;i<305;i++) for(int j=0;j<305;j++) for(int k=0;k<305;k++){
		dp[i][j][k]=-1e18;
	}
	for(int i=0;i<305;i++) for(int j=0;j<305;j++) for(int k=0;k<305;k++){
		if(i+j+k > n) continue;
		dp[i][j][k] = rec(i,j,k);
	}
	rep(i,n){
		int x; cin>>x; a[x-1]++;
	}
	printf("%.12f\n",dp[a[0]][a[1]][a[2]]);
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N;
  cin>>N;
  vector<ll> a(N);
  rep(i,0,N)
    cin>>a[i];

  multiset<ll> s; // 各色の最小値
  for (int i=N-1; i>=0; i--) {
    auto it = s.upper_bound(a[i]);
    if (it != s.end()) {
      s.erase(it);
      s.insert(a[i]);
    } else {
      s.insert(a[i]);
    }
  }
  cout<<s.size()<<endl;
}


Measured memory_bytes: 5760
from sys import stdin

N = int(stdin.readline().rstrip())
data = stdin.readline().rstrip().split()

abs_sum = 0
negative_elements = []
zero_exist = False

for number in data:
    num = int(number)
    abs_sum += abs(num)
    if num == 0:
        zero_exist = True
    elif num < 0:
        negative_elements.append(int(num))

if len(negative_elements) % 2 == 0 or zero_exist:
    print(abs_sum)
else:
    print(abs_sum - (2 * min([abs(int(x)) for x in data])))

Measured memory_bytes: 18332
h, w = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1: 1] = (['#'] + list(input()) + ['#'] for _ in range(h))
d = (-1, 0), (1, 0), (0, -1), (0, 1)

step = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1)
       if a[i][j] == '#']

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)


Measured memory_bytes: 133584
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
  int64_t N, W;
  cin >> N >> W;
  vector<int64_t> weight(N + 1, 0);
  vector<int64_t> value(N + 1, 0);
  for (int64_t i = 1; i <= N; ++i) {
    cin >> weight[i] >> value[i];
  }

  vector<vector<int64_t>> dp(N + 1, vector<int64_t>(W + 1, 0));
  for (int64_t n = 1; n <= N; ++n) {
    for (int64_t w = 0; w <= W; ++w) {
      if (w < weight[n]) {
        dp[n][w] = dp[n - 1][w];
      } else {
        dp[n][w] = std::max(dp[n - 1][w], dp[n - 1][w - weight[n]] + value[n]);
      }
    }
  }
  std::cout << dp[N][W] << std::endl;
  return 0;
}


Measured memory_bytes: 80256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,r;
    cin>>s>>r;
    int c=0;
    if(s[0]==r[0])
    c++;
    if(s[1]==r[1])
    c++;
    if(s[2]==r[2])
    c++;
    cout<<c<<"\n";
}

Measured memory_bytes: 3564
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        String tmp;
        dp = new int[n][26];
        for (int i = 0; i < n; i++) {
            tmp = sc.next();
            for (int j = 0; j < tmp.length(); j++) {
                dp[i][tmp.charAt(j)-'a']++;
            }
        }
        int[] ans = new int[26];
        Arrays.fill(ans,-1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                if (ans[j] == -1) {
                    //初登場であればそのまま代入
                    ans[j] = dp[i][j];
                } else {
                    //２回目以降は最小値を入力
                    ans[j] = Math.min(ans[j], dp[i][j]);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < ans[i]; j++) {
                System.out.print((char)(97+i));
            }
        }
        System.out.println();
    }
}


Measured memory_bytes: 22996
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		long w = sc.nextLong();
		long h = sc.nextLong();
		long x = sc.nextLong();
		long y = sc.nextLong();
		
		double a1 = x*y, a2 = (w - x)*y, a3 = x*(h - y), a4 = (w - x)*(h - y);
//		System.out.println(a1+" "+a2+" "+a3+" "+a4);

//		System.out.print(Math.max(Math.min(a1 + a2, a3 + a4), Math.min(a1 + a3, a2 + a4)) + " ");
		System.out.print((double)w*h/2+" ");
		
//		if(Math.min(a1 + a2, a3 + a4) == Math.min(a1 + a3, a2 + a4)) {
		if((double)x == (double)w/2 && (double)y == (double)h/2) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
	}

}


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;
//const i64 inf = 1'000'000'000'000'000'000ll + 7;
const i64 inf = 1'000'000'007;

const long double eps = 1e-8;

const i64 MAXN = 5'000 + 5;

i64 T;

i64 h, w, k;
string a[MAXN];

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed); cerr.precision(15); cerr.setf(ios::fixed);

    cin >> h >> w >> k;
    for (i64 i = 0; i < h; i++) {
        cin >> a[i];
    }

    i64 R = 0;
    for (i64 i = 0; i < (1ll << h); i++) {
        for (i64 j = 0; j < (1ll << w); j++) {
            /*
            set<pair<i64, i64>> q;
            for (i64 x = 0; i < h; x++) {
                if (i & (1 << x) == 0) {
                    continue;
                }
                for (i64 y = 0; y < w; y++) {
                    q.insert({ x, y });
                }
            }


            for (i64 y = 0; y < w; y++) {
                if (j & (1 << y) == 0) {
                    continue;
                }

                for (i64 x = 0; i < h; x++) {
                    q.insert({ x, y });
                }
            }
            */
            i64 c = 0;
            for (i64 x = 0; x < h; x++) {
                for (i64 y = 0; y < w; y++) {
                    if (a[x][y] == '#' && ((i & (1ll << x)) == 0) && ((j & (1ll << y)) == 0)) {
                        c += 1;
                    }
                }
            }
            if (c == k) {
                R += 1;
            }
        }
    }


    cout << R << endl;

    return 0;
}

Measured memory_bytes: 3840
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <numeric>

using namespace std;
typedef long long ll;

int get2(int start, int goal){
    
    int count = 0;
    while (start < goal){
        start *= 2;
        count++;
    }

    return count;
}

int main(){
    int n, k;

    cin >> n >> k;

    double ans = 0;
    for (int i = n; i > 0; i--){
        //cout << "get2: " << get2(i, k) << endl;
        //cout << "1 / 2^" << get2(i, k) << " : " << (1/pow(2, get2(i, k))) << endl;
        double temp = (1.0 / n) * (1.0 / pow(2, get2(i, k)));
        //cout << temp << endl;
        ans += temp;
    }

    printf("%.12f\n", ans);

    return 0;
}

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

using namespace std;

int main(){
	string s;
	cin >> s;
	int ans=0; 
	for(int i=0;i<(s.size()-1);i++){
		if(s[i]!=s[i+1])ans+=1;
	}
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] p = new int[n];
		int ans = 0;

		for(int i = 0; i < n; i++)
			p[i] = in.nextInt();

		for(int i = 1; i<n-1; i++) {
			boolean dontMax = (p[i] < Math.max(p[i-1], p[i+1]));
			boolean dontMin = (p[i] > Math.min(p[i-1], p[i+1]));
			if(dontMax && dontMin)
				ans++;

		}

		System.out.println(ans);
	}

}

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

int main()
{
  int n; cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; ++i) cin >> v[i];
  sort(v.begin(), v.end());
  int ans = 0;
  for(int i = 0; i < n; ++i)
  {
    for(int j = i+1; j < n; ++j)
    {
      for(int k = j+1; k < n; ++k)
      {
        if((v[i]!=v[j]) and (v[i]!=v[k]) and (v[j]!=v[k]))
           {
             if(v[i]+v[j] > v[k]) ++ans;
           }
      }
    }
  }
  cout << ans;  
  return 0;
}

Measured memory_bytes: 3656
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	int n,m;
	List<List<Integer>> graph;
	static int[] memo;//graph.get(i)の有向パスの最大を記録
	static boolean f[];//memo[i]に記録されているならばtrue;

	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
	}

	private void solve() {
		n = nextInt();
		m = nextInt();
		graph = new ArrayList<List<Integer>>();
		for(int i=0;i<=n;i++)graph.add(new ArrayList<Integer>());
		for(int i=0;i<m;i++)graph.get(nextInt()).add(nextInt());

		f = new boolean [n+1];
		memo = new int [n+1];
		Arrays.fill(memo, -1);
		for(int i=1;i<=n;i++)if(!f[i])memo[i] = SearchVerticesPass(i);

		Arrays.sort(memo);
		System.out.println(memo[n]);
	}

	private int SearchVerticesPass(int vi) {
		if(f[vi])return memo[vi];
		List<Integer>V = graph.get(vi);
		int cntmax=0;
		for(int i=0;i<V.size();i++)cntmax=Math.max(SearchVerticesPass(V.get(i))+1, cntmax);
		f[vi]=true;
		return memo[vi] = cntmax;
	}

	private int nextInt() {
		return Integer.parseInt(sc.next());
	}
}

Measured memory_bytes: 68536
#include <bits/stdc++.h>
#define Maxn 207
using namespace std;
int last[Maxn],pre[Maxn],other[Maxn],cnt=0;
int dis[Maxn],path[Maxn];
int p[Maxn],p1[Maxn];
bool vis[Maxn];
int dfn=0,g[Maxn];
int n,tot=0;
int dep[Maxn];
void insert(int u,int v)
{
	other[++cnt]=v,pre[cnt]=last[u],last[u]=cnt;
}
void dfs(int u,int fa)
{
	for (int q=last[u];q;q=pre[q])
	{
		int v=other[q];
		if (v!=fa)
		{
			dis[v]=dis[u]+1;
			dfs(v,u);
		}
	}
}
void get_path(int u,int fa,int goal)
{
	if (u==goal)
	{
		dfn=tot;
		for (int i=1;i<=dfn;i++)
			g[i]=path[i];
		return;
	}
	for (int q=last[u];q;q=pre[q])
	{
		int v=other[q];
		if (v!=fa)
		{
			path[++tot]=v;
			get_path(v,u,goal);
			--tot;
		}
	}
}
void get_dep(int u,int fa)
{
	for (int q=last[u];q;q=pre[q])
	{
		int v=other[q];
		if (v!=fa&&dep[v]==0)
		{
			dep[v]=dep[u]+1;
			++p1[u];
			p[dep[u]]=max(p[dep[u]],p1[u]);
			get_dep(v,u);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		insert(u,v),insert(v,u);
	}
	int now=1;
	dfs(now,-1);
	for (int i=1;i<=n;i++)
		if (dis[i]>dis[now]) now=i;
	memset(dis,0,sizeof(dis));
	dfs(now,-1);
	int a=now,b=now;
	for (int i=1;i<=n;i++)
		if (dis[i]>dis[b]) b=i;
	tot=0;
	path[++tot]=a;
	get_path(a,-1,b);
	for (int i=1;i<=dfn;i++)
		vis[g[i]]=true;
	++dis[b];
	printf("%d ",(dis[b]+1)/2);
	if (dis[b]%2==0)
	{
		dep[g[dis[b]/2]]=1;
		dep[g[dis[b]/2+1]]=1;
		get_dep(g[dis[b]/2],-1);
		get_dep(g[dis[b]/2+1],-1);
		long long ans=2;
		for (int i=1;i<dis[b]/2;i++)
			ans=1LL*ans*p[i];
		printf("%lld\n",ans);
	} else
	{
		int l=0,rt=g[(dis[b]+1)/2],rtt;
		long long ans=1;
		dep[rt]=1;
		get_dep(rt,-1);
		for (int i=1;i<(dis[b]+1)/2;i++)
			ans=1LL*ans*p[i];
		for (int q=last[rt];q;q=pre[q])
		{
			rtt=other[q];
			memset(dep,0,sizeof(dep));
			dep[rt]=1,dep[rtt]=1;
			memset(p,0,sizeof(p));
			memset(p1,0,sizeof(p1));
			get_dep(rt,-1);
			get_dep(rtt,-1);
			long long ans1=2;
			for (int i=1;i<(dis[b]+1)/2;i++)
				ans1=1LL*ans1*p[i];
			ans=min(ans,ans1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}


Measured memory_bytes: 256
N = int(input())
S = [1 if l == 'E' else 0 for l in list(input())]

for i in range(1,N):
    S[i] += S[i-1]
S.insert(0,0)

ans = N
for i in range(N):
    diff = i - S[i] + S[-1] - S[i+1]
    if ans > diff:
        ans = diff

print(ans)

Measured memory_bytes: 15184
#include<stdio.h>

int main (void){
	
	long long int n,a,i,max,min,sum;
	scanf("%lld",&n);
	scanf("%lld",&a);
	max = a;
	min = a;
	sum = a;
	for(i=0;i<n-1;i++){
		scanf("%lld",&a);
		if(max<a){
			max = a;
		}else if(min>a){
			min = a;
		}
		sum += a;
		
	}
	printf("%lld %lld %lld\n",min,max,sum);
return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
int main()
{
	int A, B, C, D;
	scanf("%d %d %d %d", &A, &B, &C, &D);
	if ((A + B) > (C + D))
		printf("Left");
	else if ((A + B) < (C + D))
		printf("Right");
	else
		printf("Balanced");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n,q;
  cin >> n;
  vector<int> A(n);
  for (int i=0;i<n;i++) cin >> A[i];
  cin >> q;
  vector<int> M(q);
  vector<string> ans(q,"no");
  for (int i=0;i<q;i++) cin >> M[i];
    for (int bit=0;bit<(1<<n);bit++){
      int s = 0;
      for (int i=0;i<n;i++){
        if ((1<<i) & bit) s += A[i];
      }
      auto itr = find(M.begin(),M.end(),s); 
      while (true){
        if (itr != M.end()){
          ans[distance(M.begin(), itr)] = "yes";
          itr = find(itr+1,M.end(),s);
        }
        else break;
      }
    }
  for (int i=0;i<q;i++) cout << ans[i] << endl;
}


Measured memory_bytes: 3236
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

int n;
string up = "";
string down = "";
string upAdd = "..##";
string downAdd = ".#.#";

int MAIN()
{
	cin >> n;

	while(true)
	{
		bool findIt = false;
		for(int i = 0; i < 4; i++)
		{
			string qUp = up;
			string qDown = down;
			qUp += upAdd[i];
			qDown += downAdd[i];
			cout << qUp << endl;
			cout << qDown << endl;
			cout << flush;
			string rev;
			cin >> rev;
			if(rev == "end") return 0;
			if(rev == "T")
			{
				up = qUp;
				down = qDown;
				findIt = true;
				break;
			}
		}
		if(!findIt)
			break;
	}

	while(true)
	{
		bool findIt = false;
		for(int i = 0; i < 4; i++)
		{
			string qUp = "";
			string qDown = "";
			qUp += upAdd[i];
			qDown += downAdd[i];
			qUp += up;
			qDown += down;
			cout << qUp << endl;
			cout << qDown << endl;
			cout << flush;
			string rev;
			cin >> rev;
			if(rev == "end") return 0;
			if(rev == "T")
			{
				up = qUp;
				down = qDown;
				findIt = true;
				break;
			}
		}
		if(!findIt)
			break;
	}
	return 0;
}

int main()
{
	int start = clock();
	#ifdef LOCAL_TEST
		freopen("in.txt", "r", stdin);
		freopen("out2.txt", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cout << fixed << setprecision(16);
	int ret = MAIN();
	#ifdef LOCAL_TEST
		cout << "[Finished in " << clock() - start << " ms]" << endl;
	#endif
	return ret;
}


Measured memory_bytes: 724
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 2000000
#define D 20

struct node{
  int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}




void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  /* your code */
  t->next->prev = t->prev;
  t->prev->next = t->next;
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t != nil ) deleteNode(t);
}

void deleteLast(){
  NodePointer t = nil->prev;
  /* your code */
  if(t!=nil)deleteNode(t);

}

void delete(int key){
  /* your code */
  NodePointer del = nil->next;
  while(1){
    if(del->key == key){
      deleteNode(del);
      break;
    }
    del = del->next;
    if(del == nil->next)return;
  }
}


void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;

  x->prev = nil;
  x->next = nil->next;
  nil->next->prev =x;
  nil->next = x;
  /* 

   your code 


  */

}

int main(){
  int key, n, i;
  char com[20];

  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) insert(key);
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      }
      else delete(key); 
    }
  }

  printList();
  return 0;
}



Measured memory_bytes: 36084
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000;
#define mod (int)1000000007
#pragma region header
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
#pragma endregion
#pragma endregion
lint gcd(lint a, lint b) {
	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}
lint dp[1000010][2][2];


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	lint n; cin >> n;
	if (n == 1) {
		cout << 0 << endl;
		return 0;
	}
	if (n == 2) {
		cout << 2 << endl;
		return 0;
	}
	dp[0][0][0] = 8;
	dp[0][1][0] = 1;
	dp[0][0][1] = 1;
	dp[0][1][1] = 0;
	for (int i = 1; i <= 1000000; i++) {
		dp[i][0][0] = dp[i - 1][0][0] * 8;
		dp[i][1][0] = dp[i - 1][1][0] * 9 + dp[i - 1][0][0];
		dp[i][0][1] = dp[i - 1][0][1] * 9 + dp[i - 1][0][0];
		dp[i][1][1] = dp[i - 1][1][1] * 10 + dp[i - 1][0][1] + dp[i - 1][1][0];
		dp[i][0][0] %= mod;
		dp[i][1][0] %= mod;
		dp[i][0][1] %= mod;
		dp[i][1][1] %= mod;
	}
	cout << dp[n - 1][1][1] << endl;

	return 0;
}

Measured memory_bytes: 34876
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void fastIO(){
  ios_base::sync_with_stdio(0); cin.tie(0);
}


int main(){
  fastIO();
  int h,w;
  cin>>h>>w;
  char painting[h+2][w+2];
  for(int i=0;i<=h+1;i++){
  	for(int j=0;j<=w+1;j++){
  		painting[i][j]='.';
  	}
  }
  for(int i=1;i<=h;i++){
  	for(int j=1;j<=w;j++){
  		cin>>painting[i][j];
  	}
  }
  bool found = true;
  for(int i=1;i<=h;i++){
  	for(int j=1;j<=w;j++){
  	  int ret=0;
  	  if(painting[i][j]=='#'){
  	  	if(painting[i-1][j]=='#'||painting[i+1][j]=='#'||painting[i][j+1]=='#'||painting[i][j-1]=='#'){
  	  	  ret++;
  	  	}
  	  }
  	  if(!ret&&painting[i][j]=='#'){
  	  	found=false;
  	  }
  	}
  }
  found?cout<<"Yes"<<endl:cout<<"No"<<endl;
}







Measured memory_bytes: 256
N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
L_max = max(L)
R_min = min(R)
if R_min >= L_max:
    ans = R_min - L_max + 1
else:
    ans = 0
print(ans)

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

int main(){
  int X,Y;
  cin >> X >> Y;
  if(X==1 && Y==1){
    cout << 300000*2+400000 << endl;
  }
  else {
    int count=0;
    if(X==1){
      count+=300000;
    }
    else if(X==2){
      count+=200000;
    }
    else if(X==3){
      count+=100000;
    }
    if(Y==1){
      count+=300000;
    }
    else if(Y==2){
      count+=200000;
    }
    else if(Y==3){
      count+=100000;
    }
    cout << count << endl;
  }
}


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

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < 8; ++i) {
        bitset<3> bs(i);
        int ans = (s[0] - '0');
        for (int j = 0; j < 3; ++j) bs.test(j) ? (ans += (s[j + 1] - '0')) : (ans -= (s[j + 1] - '0'));
        if (ans == 7) {
            cout << s[0];
            for (int j = 0; j < 3; ++j) {
                cout << (bs.test(j) ? "+" : "-");
                cout << s[j + 1];
            }
            cout << "=7" << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}


Measured memory_bytes: 256
def construct(L):
    if L <= 5: return [(1,2,x) for x in range(1,L+1)], 2
    h = L//2
    e, n = construct(h)
    e.append((n, n+1, 0))
    e.append((n, n+1, h))
    if h*2 != L: e.append((1, n+1, L))
    return e, n+1

L = int(input())-1
e, n = construct(L)
e.append((1, n, 0))
print(n, len(e))
for T in e: print(*T)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
	int N;
	cin >> N;
	vector<i64> A(N);
	rep(i, N) cin >> A[i];
	vector<i64> sum_L(N+1, 0), sum_R(N+1, 0);
	for(int i = 0 ; i < N; i++) sum_L[i+1] += sum_L[i] + A[i];
	for(int i = N ; i > 0; i--) sum_R[i-1] += sum_R[i] + A[i-1];

	i64 ans = 2020202020;
	rep(i, N+1) ans = min(ans, abs(sum_L[i] - sum_R[i]));
	cout << ans << endl;
}


Measured memory_bytes: 4992
<?php
    $str = trim(fgets(STDIN));
    $record_cound = trim(fgets(STDIN));

    for($i = 0; $i < $record_cound; $i++){
        $order = explode(" ",trim(fgets(STDIN)));
        $a = $order[1];
        $b = $order[2];
        $length = $b - $a + 1;

        switch ($order[0]){
            case 'print':
                print substr($str, $a, $length)."\n";
                break;
            case 'reverse':
                $str = substr_replace($str, strrev(substr($str, $a, $length)), $a, $length);
                break;
            case 'replace':
                $str = substr_replace($str, $order[3], $a, $length);
                break;
        }
    }

Measured memory_bytes: 15348
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    s = input().split(',')

    print(' '.join(s))

if __name__ == '__main__':
    main()

Measured memory_bytes: 10316
#include <stdio.h>

int main(){
    double w, h, x, y; 
  	int ok;
    scanf("%lf%lf%lf%lf", &w, &h, &x, &y);
    double area = (w * h) / 2.0;
    if(2 * x == w && 2 * y == h) ok = 1;
    else ok = 0;
    printf("%.6lf %d\n", area, ok);
}

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

int main() {
  int d,n;
  cin >>d >>n;
  if(n==100) n++;
  int ans = 100*n;
  for(int i = 1; i<d; i++){
    ans *= 100;
  }
  if(d==0) ans = n;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import math

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = [True] * (V + 1)
        self.primes = []
        for i in range(2, V + 1):
            if self.is_prime[i]:
                self.primes.append(i)
                for j in range(i * i, V + 1, i):
                    self.is_prime[j] = False
    
    def factorize(self, x):
        assert x > 1
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

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

int main() {
  string S, L, ans;
  cin >> S;
  int N, M;
  N = S.size();
  M = (N - 1) / 2;
  ans = "No";
  L = S;
  for(int i = 0; i < N; i++){
    L.at(i) = S.at(N - 1 - i);
  }
  if(L == S){
    ans = "Yes";
  }
  if(ans == "Yes"){
    for(int i = 0; i < M; i++){
      if(S.at(i) != S.at(M - 1 - i)){
        ans = "No";
        break;
      }
    }
    if(ans == "Yes"){
      for(int i = M + 1; i < N; i++){
        if(S.at(i) != S.at(N + M + 1 - 1 - i)){
          ans = "No";
          break;
        }
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  char num[3];
  int flag=0;
  
  for(int i=0;i<3;i++)
  {
    scanf("%c",&num[i]);
    if(num[i]=='7')
      flag=1;
  }
  if(flag)
    printf("Yes");
  else
    printf("No");
}

Measured memory_bytes: 1668
#include <iostream>
using namespace std;
int main() {
    int s1;
    int s2;
    int m1;
    int m2;
    int h;
    cin >> s1;
    s2 = s1 % 60;
    m1 = (s1-s2)/60;
    m2 = m1 % 60;
    h = (m1-m2)/60;
    cout << h <<":"<<m2 <<":"<<s2<<endl;
    
    
}


Measured memory_bytes: 3068
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int nax = 305;
double p[nax][nax][nax], ev[nax][nax][nax];
// ev[a][b][c] - the expected number of operations so far to get to state (a,b,c)
// easier: p-bility of getting to this state at all

int main() {
    int n;
    scanf("%d", &n);
    vector<int> cnt(4);
    for(int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        ++cnt[x];
    }
    p[cnt[1]][cnt[2]][cnt[3]] = 1;
    for(int c = n; c >= 0; --c) {
        for(int b = n; b >= 0; --b) {
            for(int a = n; a >= 0; --a) {
                if(a == 0 && b == 0 && c == 0) {
                    continue;
                }
                if(a + b + c > n) {
                    continue;
                }
                // dp[a][b][c]
                
                double p_waste = (double) (n - (a + b + c)) / n;
                // p_waste + p_waste^2 + ... = S
                // 1 + S = S / p_waste
                double ev_waste = p_waste / (1 - p_waste) + 1;
                debug() << imie(a) imie(b) imie(c) imie(ev_waste);
                ev[a][b][c] += ev_waste * p[a][b][c];
                
                // remove 1 -> dp[a-1][b][c]
                // we will eventually choose one of a+b+c
                if(a != 0) {
                    double p_go = (double) a / (a + b + c);
                    p[a-1][b][c] += p[a][b][c] * p_go;
                    ev[a-1][b][c] += ev[a][b][c] * p_go;
                }
                
                // remove 2 -> dp[a+1][b-1][c]
                if(b != 0) {
                    double p_go = (double) b / (a + b + c);
                    p[a+1][b-1][c] += p[a][b][c] * p_go;
                    ev[a+1][b-1][c] += ev[a][b][c] * p_go;
                }
                
                // remove 3
                if(c != 0) {
                    double p_go = (double) c / (a + b + c);
                    p[a][b+1][c-1] += p[a][b][c] * p_go;
                    ev[a][b+1][c-1] += ev[a][b][c] * p_go;
                }
            }
        }
    }
    printf("%.10lf\n", ev[0][0][0]); // + cnt[1] + 2 * cnt[2] + 3 * cnt[3]);
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll MRINF = 5000000000000000;


int main() {

  string c1, c2, c3;
  cin >> c1 >> c2 >> c3;

  cout << c1[0] << c2[1] << c3[2] << endl;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

using namespace std;

int main() {
	int n, h[21];
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	int res = 0, mm = 0;
	for (int i = 1; i <= n; ++i) {
		if (h[i] >= mm) res++;
		mm = max(mm, h[i]);
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 256
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  x = InputLine.to_i

  y = (x - 400) / 200
  puts (8 - y).to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 14368
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
typedef long double ld;
typedef pair<int,int> P;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0L)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 10*10
#define EPS 1e-9

//----***パーツ***----
#define fr first
#define se second

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

signed main(){
  int N,A;cin>>N>>A;
  int ans=0;
  vector<int> v(N);
  REP(i,0,N){cin>>v[i];}

  vector<vector<vector<int>>> dp(N+5,vector<vector<int>>(N+5,vector<int>(N*50+10,0)));

  dp[0][0][0]=1;
  REP(j,1,N+1)REP(k,0,N+1)REP(s,0,N*50+10){
    int elem=0;
    if(j>0&&v[j-1]>s){
      elem=dp[j-1][k][s];
    }
    else if (j>0&&k>0&&v[j-1]<=s){
      elem=dp[j-1][k-1][s-v[j-1]]+dp[j-1][k][s];
    }
    dp[j][k][s]=elem;
  } 
  ans=0;
  REP(k,1,N+1){
    ans+=dp[N][k][k*A];
  }
  print(ans)

}


Measured memory_bytes: 60928
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;

long long gcd (long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
long long lcm (long long a, long long b) {
    return (a/gcd(a, b))*b; //Divide before multiplying to prevent overflow
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (b-a+1) - (b/c) - (b/d) + ((a-1)/c) + ((a-1)/d) - ((a-1)/lcm(c, d)) + (b/lcm(c, d)) << endl;
}

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

int heap[2000005];
int heap_size;

int parent(int i) {
    return i/2;
}

int left(int i) {
    return 2*i;
}

int right(int i) {
    return 2*i+1;
}

void maxHeapify(int A[], int i) {
    int l = left(i);
    int r = right(i);
    int largest;
    if(l <= heap_size && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }
   
    if(r <= heap_size && A[r] > A[largest]) {
        largest = r;
    }
    if(largest != i) {
        int t = A[i];
        A[i] = A[largest];
        A[largest] = t;
        maxHeapify(A, largest);
    }
}

void buildMaxHeap(int A[]) {
    int i;
    for(i=heap_size/2;i>0;i--) {
        maxHeapify(A, i);
    }
}

int heapExtractMax(int A[]) {
	int max;
    if(heap_size < 1) {
        return INT_MIN;	// エラー
    }
    max = A[1];
    A[1] = A[heap_size];
    heap_size = heap_size - 1;
    maxHeapify(A, 1);
    return max;
}

void heapIncreaseKey(int A[], int i, int key) {
    if(key < A[i]) {
        return; // error 新しいキーは現在のキーより小さい
    }
    A[i] = key;
    while(i > 1 && A[parent(i)] < A[i]) {
    	int t = A[i];
    	A[i] = A[parent(i)];
    	A[parent(i)] = t;
        i = parent(i);
    }
}

void maxHeapInsert(int A[], int key) {
    heap_size = heap_size + 1;
    A[heap_size] = INT_MIN;
    heapIncreaseKey(A, heap_size, key);
}

int main(void) {
    int n;
    char buff[100];
    heap_size = 0;
   
	while(scanf("%s %d\n", buff, &n)>0) {
		if(buff[2] == 'd') break;
		switch(buff[2]) {
			case 's': // insert
				maxHeapInsert(heap, n);
				break;
			case 't': // extract
				printf("%d\n", heapExtractMax(heap));
				break;
		}
	}

    return 0;
}

Measured memory_bytes: 4704
#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using ll = long long;

int main() {
    int N;
    std::cin >> N;
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        int in;
        std::cin >> in;
        ans += in - 1;
    }

    std::cout << ans << std::endl;


    return 0;
}


Measured memory_bytes: 256
p=[]
for i in range(2,1121):
    for j in range(2,int(i**0.5)+1):
        if not i%j:break
    else:p+=[i]
dp=[[0]*1121 for _ in range(15)]
dp[0][0]=1
for x,y in enumerate(p):
    for i in range(min(x+1,14),0,-1):
        for j in range(y,1121):
            dp[i][j]+=dp[i-1][j-y]
while 1:
    n,k=map(int,input().split())
    if n==0:break
    print(dp[k][n])

Measured memory_bytes: 8184
import java.util.Scanner

fun main(args:Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val leftmax = IntArray(n)
    val rightmax = IntArray(n)
    val num = IntArray(n)
    leftmax[0] = 0
    rightmax[n - 1] = 0
    for (i in 0 until n) {
        num[i] = sc.nextInt()
    }
    for (i in 1 until n) {
        leftmax[i] = Math.max(leftmax[i - 1], num[i - 1])
    }
    for (i in n - 1 downTo 1) {
        rightmax[i - 1] = Math.max(rightmax[i], num[i])
    }
    for (i in 0 until n) {
        println(Math.max(leftmax[i], rightmax[i]))
    }
}


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

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

typedef struct point2dwithcircle{
  int x,y,r;
} point;

double distance(point *a,point *b){
  int dx=a->x-b->x;
  int dy=a->y-b->y;
  int64 d=(int64)dx*dx+(int64)dy*dy;
  int64 r=a->r+b->r;
  if(d<=r*r) return 0;
  return (double)(d-r*r)/(sqrt(d)+r);
}

void run(void){
  point s,t;
  scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);
  s.r=0;
  t.r=0;
  int n;
  scanf("%d",&n);
  point *array=(point *)malloc(sizeof(point)*(n+2));
  array[0]=s;
  array[n+1]=t;
  int i;
  for(i=1;i<=n;i++) scanf("%d%d%d",&array[i].x,&array[i].y,&array[i].r);
  double *dp=(double *)malloc(sizeof(double)*(n+2));
  int *used=(int *)malloc(sizeof(int)*(n+2));
  for(i=0;i<=n+1;i++){
    dp[i]=1e18;
    used[i]=0;
  }
  dp[0]=0;
  for(i=1;i<=n+1;i++){
    int index;
    for(index=0;used[index]!=0;index++);
    double min=dp[index];
    int j;
    for(j=index+1;j<=n+1;j++){
      if(!used[j] && dp[j]<min){
	min=dp[j];
	index=j;
      }
    }
    used[index]=1;
    for(j=0;j<=n+1;j++){
      dp[j]=MIN(dp[j],dp[index]+distance(array+index,array+j));
    }
  }
  printf("%.10lf\n",dp[n+1]);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e4+5;
int h,n,dp[N];
int main()
{
    memset(dp,inf,sizeof(dp));
    dp[0]=0;
    scanf("%d%d",&h,&n);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        for(int j=0;j<=10000;j++)
            dp[j+a]=min(dp[j+a],dp[j]+b);
    }
    int ans=inf;
    for(int i=h;i<=20000;i++)
        ans=min(ans,dp[i]);
    printf("%d\n",ans);
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int dig(int n){
    int dig=0;
    while(n>0){
        dig++;
        n /= 10;
    }
    return dig;
}

int main() {
    int a,b;
    cin >> a >> b;
    for(int i=0;i<dig(b);i++) a *=10;
    int x = a+b;

    for(int i=0;i<1000;i++){
        if(i*i == x){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256