akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main{
	public static void main(String[]args){
    Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int m=sc.nextInt();
      int a=1;
      for(int i=m/n;true;i--){
      	if(m%i==0){
        	
      System.out.println(i);
          break;
        }
      }
    
    }


}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> A(N), B(N);
    for (auto &a : A) cin >> a;
    for (auto &b : B) cin >> b;
    Int total = 0, add1 = 0, add2 = 0;
    for (int i = 0; i < N; i++) {
        total += B[i] - A[i];
        if (A[i] > B[i]) {
            add1 += A[i] - B[i];
        } else {
            add2 += (B[i] - A[i] + 1) / 2;
        }
    }
    if (max(add1, add2) <= total) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 384
import sys

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
A=list(map(int,input().split()))
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

grundy=[-1]*N

def dfs(v):
    if grundy[v]!=-1:
        return grundy[v]

    mex=[False]*(len(edge[v])+1)
    for nv in edge[v]:
        if A[nv]<A[v]:
            g=dfs(nv)
            if g<=len(edge[v]):
                mex[g]=True
    for i in range(len(edge[v])+1):
        if not mex[i]:
            grundy[v]=i
            return i

ans=[]
for i in range(N):
    if dfs(i)!=0:
        ans.append(i+1)

print(*ans)


Measured memory_bytes: 75832
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)





int main() {
    ll n;
    cin >> n;
    vector<ll> s(n);
    REP(i, n){
        cin >> s[i];
    }
    ll q;
    cin >> q;
    ll ans = 0;
    REP(i, q){
        ll t;
        cin >> t;
        ll v = *lower_bound(s.begin(), s.end(), t);
        if(v == t) ans++;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3604
// https://atcoder.jp/contests/abc047/tasks/arc063_a

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{
  string s;
  cin >> s;

  int cnt = -1;
  char l = 'S';
  for (char &c : s)
  {
    if (c != l)
    {
      l = c;
      cnt++;
    }
  }

  cout << cnt << '\n';

  return 0;
}


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

public class Main {
    
    public static void main(String[] args) {
    
        var sc = new Scanner(System.in);
    
        int n = Integer.parseInt(sc.next());
        var a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(sc.next());
        }
    
        Arrays.sort(a);
        long ans = a[n-1];
        int j = n-2;
        for(int i = 0; i < n-2; i++){
            ans += a[j];
            if(i%2 == 1) j--;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 60260
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ABS(ll x){
  return x<0?-x:x;
}
int main(){
  int n;
  ll a,b,c,d;  scanf("%d%lld%lld%lld%lld",&n,&a,&b,&c,&d);
  b-=a;
  if(b<0)b=-b;

  n--;
  for(int i=0;i*2<=n;++i){
    int j=n-i*2;
    //j*[c,d],i*[0,d-c]
    ll Min=j*c,Max=j*d+i*(d-c);
    if(Min<=b&&b<=Max)return puts("YES"),0;
    Min=j*c-i*(d-c);
    Max=j*d-i*(d-c);
    if(Max<0){
      Max=-Max;Min=-Min;swap(Min,Max);
    }
    if(Min<=b&&b<=Max)return puts("YES"),0;
  }
  puts("NO");
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>

using namespace std;
typedef pair<int,bool> Pair;

int main(){

  int N;
  int h[100001];
  int DP[100001];

  cin >> N;

  for (int i = 0; i < N;++i) cin >> h[i];

  DP[0] = 0;
  DP[1] = abs(h[0] - h[1]);

  for (int i = 2; i < N;++i){

    DP[i] = min(DP[i-1] + abs(h[i] - h[i - 1]), DP[i-2] + abs(h[i] - h[i - 2]));

  }

  cout << DP[N-1] << endl;

    return 0;

}

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

int main() {
    int x, y; cin >> x >> y;
    if (x == 2 && y == 2) puts("Yes");
    else if (x == 4 || x == 6 || x == 9 || x == 11) {
        if (y == 4 || y == 6 || y == 9 || y == 11) {
            puts("Yes");
        }
        else {
            puts("No");
        }
    }
    else {
        if (y == 4 || y == 6 || y == 9 || y == 11) {
            puts("No");
        }
        else {
            if (x == 2 || y == 2) puts("No");
            else puts("Yes");
        }
    }
}


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

#define rep(i, first, to) for(int i = first; i < to; ++i)
#define REP(i, first, to) for(int i = first; i <= to; ++i)
#define MyDebug

#ifdef MyDebug
	#define debug(x) cout << #x << " : " << x << endl
	#define debugP(x) cout << x << endl
#else
	#define debug(x)
	#define debugP(x)
#endif

using namespace std;
typedef long long ll;

int n;
int a[(int)1e5 + 1];
int cnt = 0;
void solve() {
	cin >> n;
	REP(i, 1, n) {
		cin >> a[i];
	}
	int j = 1;
	cnt = 0;
	rep(i, 0, n) {
		j = a[j];
		++cnt;
		if (j == 2) {
			cout << cnt << endl;
			return;
		}
	}
	cout << -1 << endl;
}

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

Measured memory_bytes: 640
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def sub(w, v, b):
    """重みリストw, 価値リストv, 重さ上限bのナップサックを解く
    """
    dp = [0] * (b+1)
    for i in range(len(w)):
        for j in range(b, -1, -1):
            if w[i]<=j:
                dp[j] = max(dp[j], dp[j-w[i]]+v[i])
    return dp
n,w = map(int, input().split())
ws = [None]*n
vs = [None]*n
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
dp = sub(ws, vs, w)
print(dp[w])

Measured memory_bytes: 68296
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n-1):
    if(a[i] < a[i+1]):
        #if(b[i-1] < 1):
        b[i] = 1
        #else:
        #    b[i] = 2
    if(a[i] > a[i+1]):
        #if(b[i-1] > -1):
        b[i] = -1
        #else:
        #    b[i] = -2
    #else:
        #if(b[i-1] > 0):
    #       b[i] = 2
     #   else:
      #      b[i] = -2
b[-1] = -1
#print(b)
h = [1000,0]
for i in range(n):
    if(b[i] == 1):
        h[1] += h[0]//a[i]
        h[0] %= a[i]
    elif(b[i] == -1):
        h[0] += h[1]*a[i]
        h[1] *= 0
    #print(h)
print(h[0])

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    int N = input();
    vector< int > A(N);
    cin >> A;

    i64 ans = 0;
    map< int, i64 > cnt;
    range(i, 0, N) {
        ans += cnt[A[i] - i];
        cnt[-A[i] - i]++;
    }

    cout << ans << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 26692
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int cnt[100000];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b; a--; b--;
		cnt[a]++;
		cnt[b]++;
	}
	for (int i = 0; i < N; i++) {
		if (cnt[i] % 2 == 1) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 640
S = list(input())
odd_zero = 0
even_zero = 0
odd_one = 0
even_one = 0
for n in range(len(S)):
    if n%2 == 0:
        if S[n] == '0':
            even_zero += 1
        else:
            even_one += 1
    else:
        if S[n] == '0':
            odd_zero += 1
        else:
            odd_one += 1
print(len(S)-max(even_zero+odd_one, even_one+odd_zero))


Measured memory_bytes: 3956
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<int, int> mp;
map<int, int>mm;
#define ll long long
#define ld long double
#define PI 3.14159265358979l

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


int main() {
	string s;
	cin >> s;
	int cnt = 0;
	int max=0;
	rep(i, s.size()) {
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
			cnt++;
		}
		else {
			if (max < cnt)max = cnt;
			cnt = 0;
		}
	}
	if (max < cnt)max = cnt;
	cout << max << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ; 
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fast ios_base:: sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define endl "\n"
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int> 
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

long long M  = 1e9+7;
 
signed main(){
    fast;
    int x; cin >> x;
    int ans = 0;
    int curr = 100;
    while(curr < x){
        ans++;
        curr = curr*0.01 + curr;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3652
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace atcoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var buffer = Console.ReadLine().Split();
            var A = new List<long>();
            foreach (var v in buffer)
                A.Add(long.Parse(v));

            var list = new List<long>();
            list.Add(0);
            for (int i = 0; i < N; i++)
                list.Add(list[i] + A[i]);

            long ans = 0;
            for (int i = 0; i < N; i++)
            {
                ans += A[i] * ((list[N] - list[i + 1]) % 1000000007);
                ans %= 1000000007;
            }
            Console.WriteLine(ans);
        }
    }
}


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

int main(){
	int n, x;
	scanf("%d %d", &n, &x);
	std::vector<int> a({x});
	for(int i=0; i<n; i++){
		scanf("%d", &x);
		a.push_back(x);
	}
	int ans = 0;
	std::sort(a.begin(), a.end(), std::greater<int>());
	for(int i=0; i<n; i++) ans = std::__gcd(ans, a[i]-a[i+1]);
	printf("%d\n", ans);
}


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

int main(){
    string S; cin >> S;

    stack<int> st1;
    stack<pair<int, int>> st2;

    int sum = 0;

    for(int i=0; i<S.size(); ++i){
        if(S[i] == '\\'){
            st1.push(i);
        }else if(S[i] == '/' && st1.size()>0){
            int j = st1.top();
            st1.pop();
            sum += i-j;
            int a = i-j;
            while(st2.size()>0 && st2.top().first > j){
                a += st2.top().second;
                st2.pop();
            }
            st2.push({j, a}); // 水たまりの一番左と水たまりの面積をst2に入れる
        }
    }

    vector<int> ans;
    while(st2.size() > 0){
        ans.push_back(st2.top().second);
        st2.pop();
    }
    reverse(ans.begin(), ans.end());


    cout << sum << endl;
    cout << ans.size();
    for(int i=0; i<ans.size(); ++i){
        cout << " " << ans[i];
    }
    cout << endl;
}


Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)

using namespace std;

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

    for(string S; cin >> S, S != "#";){
        int len = S.size();

        int h = 0, w = 0;
        vector<vector<int>> field(1);

        for(auto& c : S){
            if(c == '/'){
                field.push_back(vector<int>());
                h++;
            }
            else if('1' <= c and c <= '9'){
                int num = c - '0';
                rep(loop, num){
                    field[h].push_back(0);
                }
            }
            else {
                field[h].push_back(1);
            }
        }
        h++;
        w = field[0].size();

        int a, b, c, d; cin >> a >> b >> c >> d; a--, b--, c--, d--;
        field[c][d] = field[a][b];
        field[a][b] = 0;

        string res = "";
        rep(y, h){
            if(y != 0) res += '/';
            int cnt = 0;
            rep(x, w){
                int cur = field[y][x];
                if(cur == 0){
                    cnt++;
                }
                else {
                    if(cnt > 0){
                        res += (cnt + '0');
                        cnt = 0;
                    }
                    res += 'b';
                }
            }
            if(cnt > 0){
                res += (cnt + '0');
                cnt = 0;
            }
        }

        cout << res << endl;
    }

    return 0;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

lli gcd(lli x, lli y)
{
	if(DEBUG)cout<<"x="<<x<<"y="<<y<<endl;
        if (y == 0) {
                return x;
        } else {
                return gcd(y, x % y);
        }
}

map<lli,lli> makePrimeList2(lli n){
	map<lli,lli> m;
	lli a = 2;
	while(n>=a*a){
		if(n%a==0){
			m[a]++;
			n /= a;
		}
		else a++;
	}
	if(n!=1)m[n]++;
	return m;
}

signed main(){

	lli a,b;
	cin>>a>>b;
	if(b>a)swap(a,b);

	lli num = gcd(a,b);
	map<lli,lli> m = makePrimeList2(num);

	cout<<m.size()+1<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
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); } }
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; }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

void Main() {
	string s; cin >> s;
	if (s[0] <= 'Z') {
		cout << 'A' << endl;
	} else {
		cout << 'a' << endl;
	}
}

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


Measured memory_bytes: 3636
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    int ans = 1;
    cin >> n;
    int h[n];
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }

    for(int i = 1; i < n; i++){
        int count = 0;
        for(int j = 0; j < i; j++){
            if(h[j] <= h[i]) count++;
        }
        if(count == i) ans++;
    }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
  int ans = 0, n, flag1, flag2, cnt;
  char s[101];
 
  scanf("%d", &n);
  scanf("%s", s);
 
  for(int i = 1; i < n; i++){
    cnt = 0;
    for(int j = 'a'; j <= 'z'; j++){
      flag1 = flag2 = 0;
      for(int k = 0; k < i; k++)
        if(s[k] == j)
          flag1++;
      for(int k = i; k < n; k++)
        if(s[k] == j)
          flag2++;
      if(flag1 > 0 && flag2 > 0)
          cnt++;
    }
    if(cnt > ans)
      ans = cnt;
  }
 
  printf("%d", ans);
 
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_A=5000,MAX_B=5000;

int A,B;
int ana[MAX_A],bruno[MAX_B];

vector<int> C[MAX_B+1];

int main(){
	scanf("%d %d",&A,&B);
	for (int i=0;i<A;i++){
		scanf("%d",&ana[i]);
	}
	for (int i=0;i<B;i++){
		scanf("%d",&bruno[i]);
	}
	//Cを完成させる
	for (int i=0;i<B;i++){
		for (int j=0;j<A;j++){
			if (bruno[i]==ana[j]){
				C[i].push_back(j);
			}
		}
	}
	int ma=0;
	int last;
	for (int i=0;i<B;i++){
		if (C[i].empty()) continue;
		last=C[i][0];
		for (int j=i+1;;j++){
			auto ite=upper_bound(C[j].begin(),C[j].end(),last);
			if (ite==C[j].end()){
				//見つからなかった
				ma=max(ma,j-i);
				break;
			}
			last=*ite;
		}
	}
	printf("%d\n",ma);
	return 0;
}

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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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



int main(void)
{
  ll n;
  vector<ll> a;
  cin >> n;
  ll cnt = 0;
  REP(i, n) {
    ll a1;
    cin >> a1;
    a.push_back(a1);
    for(;a1%2!=1;a1/=2,cnt++) ;
  }
  cout << cnt << endl;
}


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

using namespace std;

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

int main() {
    int n, k, m;
    while(cin>>n>>k>> m, n+k+m) {
        vector<int> stones(n);
        iota(stones.begin(), stones.end(), 1);
        m -= 1;
        while(stones.size()>1) {
            stones.erase(stones.begin()+m);
            m = (m+k-1) % stones.size();
        }
        cout << stones[0] << endl;
    }
}


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

int main(void){
  int N, M, i;
  cin >> N >> M;
  int L, R, l = 1, r = N;
  for(i = 0; i < M; i++){
    cin >> L >> R;
    l = max(l, L);
    r = min(r, R);
  }
  cout << max(0, r-l+1) << endl;
  return 0;
}


Measured memory_bytes: 256
n, k = gets.chomp.split(" ").map(&:to_i)
h = gets.chomp.split(" ").map(&:to_i)
h = h.sort
i = 0
ans = 0
k.times do
    if h != []
    h.pop
        if h == []
            ans += 1
            break
        end
    else
        ans += 1
        break
    end

end
if h != [] && ans == 0
puts h.inject(:+)
elsif ans >= 1
    puts "0"

end


Measured memory_bytes: 36964
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x)&(-x)
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define maxd 1000000007
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
int n,cnt[30],q,pos[200200],op[2][200200];
char s[200200],t[10];

int read()
{
	int x=0,f=1;char ch=getchar();
	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
	return x*f;
}

int left(int mid)
{
	int now=mid;
	rep(i,1,q)
	{
		if (op[0][i]==pos[now]) now+=op[1][i];
		if (now>n) return 0;
		if (now<1) return 1;
	}
	return 0;
}

int rght(int mid)
{
	int now=mid;
	rep(i,1,q)
	{
		if (op[0][i]==pos[now]) now+=op[1][i];
		if (now>n) return 1;
		if (now<1) return 0;
	}
	return 0;
}

int main()
{
	n=read();q=read();
	scanf("%s",s);
	rep(i,1,n) pos[i]=s[i-1]-'A';
	rep(i,1,q)
	{
		scanf("%s",t);
		op[0][i]=t[0]-'A';
		scanf("%s",t);
		if (t[0]=='L') op[1][i]=-1;else op[1][i]=1;
	}
	int l=1,r=n,ansl=0,ansr=n+1;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (left(mid)) {ansl=mid;l=mid+1;}
		else r=mid-1;
	}
	l=1;r=n;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (rght(mid)) {ansr=mid;r=mid-1;}
		else l=mid+1;
	}
	printf("%d",n-ansl-(n-ansr+1));
	return 0;
}

Measured memory_bytes: 2816
#include<iostream>
#include<string>
using namespace std;
int main(){
    int N;
    cin >> N;
    int d[N];
    for(int i=1;i<=N;i++) cin >> d[i];
    int sum=0;
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j++){
            if(i!=j){
                sum=sum+d[i]*d[j];
            }
        }
    }
    cout << sum << endl;

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i, n) ;for (int i = 0;i < (int)(n);i++)
#define rep2(i, s, n) ;for (int i = s; i < (int)(n);i++)
#define ALL(vec)  (vec).begin(),(vec).end()
#define pi 3.1415926535897932384626433832795
#define MAX_INF 9223372036854775807
#define MIN_INF (922337203685477587+1)
#define sosuu 1000000007

int main() {
  int N;
  cin >> N;
  double D;
  cin >> D;
  int ans=0;
  rep(i,N){
    double a,b;
      cin >>a>>b;
    if(D>=sqrt(a*a+b*b))
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3720
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		int a=cin.nextInt(),b=cin.nextInt(),c=cin.nextInt(),res=0;
		for(int i=a;i<=b;i++){
			if(c%i==0)res++;
		}
		System.out.println(res);
	}

}



Measured memory_bytes: 26324
import math
def cmb(n, r):
  n_ = math.factorial(n)
  n_r_ = math.factorial(n-r) 
  r_ = math.factorial(r)
  return n_//(r_*n_r_)

n,k = list(map(int, input().split(" ")))

for i in range(1, k+1):
  if n-k+1 >= i:
    ans =  cmb(n-k+1,i)*cmb(k-1,i-1)%(10**9+7)
  else:
    ans = 0
  print(ans)

Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int a[3];
int main() {
	for (int i = 0; i < 3; i++) {
		cin >> a[i];
	}
	ll count = 0;
	while (a[1] != a[2] || (a[1] - a[0]) % 2 != 0) {
		sort(a, a + 3);
		a[0]++;
		a[1]++;
		count++;
		
	}
	cout << count + (a[1] - a[0]) / 2 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i< (int) n; i++)
 
 
int main () {
    int x;

    cin >> x ;

    if(x < 1200) cout <<"ABC" <<endl;
    else cout << "ARC" << endl;


}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            if (n == 0 && x == 0) {
                break;
            }

            int i, j, k;
            int count = 0;
            for (i = 1; i <= n - 2; i++) {
                for (j = i + 1; j <= n - 1; j++) {
                    for (k = j + 1; k <= n; k++) {
                        if (i + j + k == x) {
                            count += 1;
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}



Measured memory_bytes: 26992
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int main() {
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >> F;
	int res1 = 100*A;
	int res2 = 0;
	int i, j, k, l;
	for (i = 0;i * 100 * A <= F;i++) {
		for (j = 0;100 * (i*A + j*B) <= F;i++) {
			for (k = 0;100 * (i*A + j*B) + k*C <= F;k++) {
				for (l = 0; 100 * (i*A + j*B) + k*C + l*D <= F;l++) {
					if (res2*(100 * (i*A + j*B) + k*C + l*D)<res1*(k*C + l*D)
						&& (k*C + l*D)*(100 + E) <= E*(100 * (i*A + j*B) + k*C + l*D)) {
						res1 = 100 * (i*A + j*B) + k*C + l*D;
						res2 = k*C + l*D;
					}
				}
			}
		}
	}
	cout << res1 << " " << res2 << endl;
	return 0;
}


Measured memory_bytes: 256
//============================================================================
// Name        : YakusuuTest.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int a,b,c,amo,div,i;
	cin>>a>>b>>c;
	for(i=a-1;i<b;i++){
		div=c%a;
		a++;
		if(div==0){
			amo++;
		}
	}
	cout<<amo<<endl;
}



Measured memory_bytes: 3096
import bisect


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]

    colors = [-a[0]]
    for aa in a[1:]:
        i = bisect.bisect_right(colors, -aa)
        if i == len(colors):
            colors.append(-aa)
        else:
            colors[i] = -aa
    print(len(colors))


main()


Measured memory_bytes: 11804
#include<iostream>

using namespace std;

int main(){
    unsigned long long i, n, tmpa, tmpb;
    int mn =11;
    cin >> n;
    for(i=1;i*i<=n;i++){
        if(n%i!=0)continue;
        tmpa=n/i;
        tmpb=i;
        int cnta=0,cntb=0;
        while(tmpa>0){
            cnta++;
            tmpa/=10;
        }
        while(tmpb>0){
            cntb++;
            tmpb/=10;
        }
        mn = min(mn, max(cnta, cntb));
    }
    cout << mn << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#define println(S) (cout << S << endl)
using namespace std;

int main() {
	int N;
	cin >> N;
	set<string> s;
	char last,first;
	string buf;
	cin >> buf;
	last = buf[buf.length()-1];
	s.insert(buf);
	for (int i = 1; i < N; ++i) {
		cin >> buf;
		first = buf[0];
		if(last!= first || s.find(buf) != s.end()){
			println("No");
			return 0;
		}
		last = buf[buf.length()-1];
		s.insert(buf);
	}
	println("Yes");
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字列の入力
		String s = sc.next();
		sc.close();
		int len = s.length();
		String i18n = s.charAt(0) + Integer.toString(s.length()-2) + s.charAt(len-1);

		// 出力
		System.out.println(i18n);
	}

}


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

const int INF = 1001001001;
vector<int> to[100005];

int main(){
    int n, m;
    cin >> n >> m;
    rep(i,m){
        int a, b;
        cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
    }

    queue<int> q;
    vector<int> dist(n, INF);
    vector<int> pre(n, -1);
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : to[v]) {
            if (dist[u] != INF) continue;
            dist[u] = dist[v]+1;
            pre[u] = v;
            q.push(u);
        }
    }

    cout << "Yes" << endl;
    rep(i,n) {
        if (i == 0) continue;
        int ans = pre[i];
        ++ans;
        cout << ans << endl;
    }
    return 0;
}


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

const int N=(2e5)+7;
int n, res;
long long k;
int a[N];
bool vst[N];
vector< int > cycle;
deque< int > st;

void _dfs(int i){
    if(vst[i]){
        while(st.back()!=i){
            cycle.push_back(st.back());
            st.pop_back();
        }
        cycle.push_back(i);
        st.pop_back();
        return;
    }

    st.push_back(i);
    vst[i]=true;
    _dfs(a[i]);
}

void _input(){
    cin>>n>>k;
    for(int i=1; i<=n; ++i)
        cin>>a[i];
}

void _solve(){
    _dfs(1);
    reverse(cycle.begin(), cycle.end());

    if(k<(long long)st.size()){
        while(k>0){
            st.pop_front();
            --k;
        }
        res=st.front();
    }
    else{
        k-=(long long)st.size();
        res=cycle[k%((long long)cycle.size())];
    }
}

void _output(){
    cout<<res;
}

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

//    freopen("input.inp", "r", stdin);

    _input();
    _solve();
    _output();

    return 0;
}


Measured memory_bytes: 17528
import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++) {
            a[i] = sc.nextInt();
        }
        for(int i=0;i<n-1;i++)
            for(int j=0;j<n-i-1;j++)
                if(a[j]<a[j+1]) {
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
        int sum1 = 0;
        int sum2 = 0;
        int flag = 1;
        for(int i=0;i<n;i++,flag*=-1) {
            if(flag==1) {
                sum1+=a[i];
            }
            else sum2+=a[i];
        }
        System.out.println(sum1-sum2);
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define maxN 1000001
#define mod 1000000007
#define maxLL 1000000000000000000
typedef long long ll;

bool compared(int a,int b){
	return a < b;
}

int cmp(const void *a,const void *b){
	return(*(int*)b - *(int*)a);
}

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

ll a[maxN];

int main(){
	int n;
	ll res = 1;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i] == 0){
			puts("0");
			return 0;
		}
	}
	for(int i=0;i<n;i++){
		if(a[i] > maxLL/res){
			puts("-1");
			return 0;
		}
		res*=a[i];
	}
	if(res > maxLL){
		puts("-1");
	}
	else{
		cout<<res<<endl;
	}
	return 0;
}


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

int main() {
    int A;
    long int B, N;
    cin >> A >> B >> N;
    
    long int max = 0;
    long int x;
    
    if (B > N)
        x = N;
    else
        x = B - 1;
    
    if(B != 1) {
        for (; x <= N; x+=B) {
            long int total = floor(A*x/B) - floor(x/B)*A;
            if(max < total)
                max = total;
            }
    }
    
    cout << max << endl;
    
    return 0;
}



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

int main(){
    ll N,X,T;
    cin >> N >> X >> T;

    ll ans;

    if(N%X==0){
        ans = (N/X) * T;
    }
    else{
        ans = (N/X) * T + T;
    }


    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class C
{
	public static void Main()
	{
		string S = Console.ReadLine();

		int numZero = 0;
		int numOne = 0;
		for(int i = 0; i < S.Length; i++)
		{
			if(S[i] == '0')
				numZero++;
			else
				numOne++;
		}
		
		Console.WriteLine(2 * Math.Min(numZero, numOne));
	}	
}





Measured memory_bytes: 11232
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,v.size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define uniq(v)sort(all(v));v.erase(unique(all(v)),v.end())
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,T&&t,U&&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(T&&...t){_print(cout,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#else
template<class...T>void dprint(T&&...t){_print(cerr,t...);}
#endif
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>ostream&operator<<(ostream&o,const multiset<T>&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(10);
    int n;
    cin>>n;
    vi h(n);
    cin>>h;
    int ma=0;
    REP(i,n){
        int ii=i;
        while(i+1!=n && h[i]>=h[i+1])++i;
        chmax(ma, i-ii);
    }
    cout<<ma<<endl;
    return 0;
}


Measured memory_bytes: 640
import java.util.*;
public class Main {
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args) {
 
    int n = kbd.nextInt();
    int[] a = new int[n];
    int i = 0;
    for(; i<n; i++){
        a[i] = kbd.nextInt();
    }
    for(; i>0; i--){
        System.out.print(a[i-1]);
        if(i-1 != 0) System.out.print(" ");
        else System.out.println();
    }
    }
}

Measured memory_bytes: 19652
#include <stdio.h>

int main()
{
  int W, H, x, y, r;

  scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

  if ((x + r <= W) && (x - r >= 0)
      && (y + r <= H) && (y - r >=0)) {
	printf("Yes\n");
  }  else {
	printf("No\n");
  }

  return 0;
}
	



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

int main () {
  int D;
  cin >> D;
  if (D == 25) cout << "Christmas" << endl;
  else if (D == 24) cout << "Christmas Eve" << endl;
  else if (D == 23) cout << "Christmas Eve Eve" << endl;
  else cout << "Christmas Eve Eve Eve" << endl;
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)
// }}} 2

// numerous {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// systems }}} 2

// }}} 1


int main() {

    int n;
    ll t,a;
    ll ta=0, ao=0;
    ll up;

    Scd( n );

    Rep( i, n ){
        Scll2( t, a);
        if(ta < t && ao < a){
            ta = t; ao = a;
            continue;
        }
        if( ta < t ) ta = t;
        if( ao < a ) ao = a;
        up = max( (ta + t-1) / t, (ao + a-1) / a);
        ta = t * up; ao = a * up;
    }

    printf ("%llu\n", ta+ao);

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
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; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
int main() {
	int a, b;
	cin >> a >> b;
	cout << a * b << endl;
	return 0;
}

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

int main(void){
     int n;
     int s[103];
     while(cin >> n && n != 0){
	     for(int i=0; i<n;i++){
	     	cin >> s[i];
	     }
	     sort(s, s+n);
	     long long sum=0;
	     for(int i=1; i<n-1;i++){
	     	sum += s[i];
	     }
	     cout << sum/(n-2) << endl;
	}
	return 0;
}

Measured memory_bytes: 2976
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;

int main(){

    ll N;
    cin >> N;
    string S;
    cin >> S;

    ll ans = 0;
    ll t_ans = 0;
    for(ll i = 0; i < S.length(); i++){
        ans = max(ans, t_ans);
        if(S[i] == 'I'){
            t_ans++;
        }else if(S[i] == 'D'){
            t_ans--;
        }
    }
    ans = max(ans, t_ans);
    cout << ans << endl;

}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n,a[45][45];
char s[45];
ll f[45][45][45][45],g[45][45][45][45];
ll ask_f(int l1,int r1,int l2,int r2);
ll ask_g(int l1,int r1,int l2,int r2);
ll ask_f(int l1,int r1,int l2,int r2)
{
	if(f[l1][r1][l2][r2]!=-1)return f[l1][r1][l2][r2];
	f[l1][r1][l2][r2]=0;
	if(l1==r1&&l2==r2)return f[l1][r1][l2][r2]=a[l1][l2];
	if(l1==r1)
	{
		for(int i=l2+1;i<r2;i++)
		  if(a[l1][i])
		    f[l1][r1][l2][r2]+=ask_g(l2,i-1,i+1,r2);
		return f[l1][r1][l2][r2];
	}
	if(l2==r2)
	{
		for(int i=l1+1;i<r1;i++)
		  if(a[i][l2])
		    f[l1][r1][l2][r2]+=ask_g(l1,i-1,i+1,r1);
		return f[l1][r1][l2][r2];
	}
	for(int i=l1+1;i<r1;i++)
	  for(int j=l2+1;j<r2;j++)
	    if(a[i][j])
	      f[l1][r1][l2][r2]+=ask_g(l1,i-1,i+1,r1)*ask_g(l2,j-1,j+1,r2);
	return f[l1][r1][l2][r2];
}
ll ask_g(int l1,int r1,int l2,int r2)
{
	if(g[l1][r1][l2][r2]!=-1)return g[l1][r1][l2][r2];
	g[l1][r1][l2][r2]=0;
	if(l1>r1&&l2>r2)return g[l1][r1][l2][r2]=1;
	if(l1>r1||l2>r2)return g[l1][r1][l2][r2]=0;
	for(int i=l1;i<=r1;i++)
	  for(int j=l2;j<=r2;j++)
	    g[l1][r1][l2][r2]+=ask_f(l1,i,j,r2)*ask_g(i+1,r1,l2,j-1);
	return g[l1][r1][l2][r2];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=2*n;j++)
		  a[i][j]=s[j]-'0';
	}
	ll ans=0;
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	for(int i=2;i<=2*n;i++)
	{
		if(a[1][i])
		  ans+=ask_g(2,i-1,i+1,2*n);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 64256
#include <utility>
#include <vector>
#include <iostream>
#include <cstdlib>
#include<bits/stdc++.h>
#include <limits>
#include <set>
#include <map>
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
typedef long long ll;
ul gcd(ul a, ul b){return b? gcd(b, a%b):a;}
using namespace std;

bool graph[50][50];
bool visited[50];
int N;

void dfs(int v){
    visited[v] = true;
    for(int v2 = 0; v2 < N; ++v2){
        if(graph[v][v2] == false) continue;
        if(visited[v2] == true) continue;
        dfs(v2);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M;
    cin >> N >> M;
    int A[M], B[M];
    for(int i = 0; i < M; i++){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
        graph[A[i]][B[i]] = true;
        graph[B[i]][A[i]] = true;
    }
    int ans = 0;
    for(int i = 0; i < M; i++){
        graph[A[i]][B[i]] = graph[B[i]][A[i]] = false;
        for(int j = 0; j < N; j++){
            visited[j] = false;
        }
        dfs(0);
        bool bridge = false;
        for(int j = 0; j < N; j++){
            if(visited[j] == false){
                bridge = true;
            }
        }
        if(bridge){
            ans++;
        }
        graph[A[i]][B[i]] = graph[B[i]][A[i]] = true;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;

const int mod = 1000 * 1000 * 1000 + 7;
vector<vector<int>> dp;

int solve(int cur, int parent, int parent_value, const vector<vector<int>> &G) {
  int& ret = dp[cur][parent_value];
  if (ret == -1) {
    ret = 0;

    for (int value = 0; value < 2; ++value) {
      int cnt = 0;
      if (value + parent_value <= 1) {
        cnt = 1;
        for (int next : G[cur]) {
          if (next != parent) {
            int cnt_next = solve(next, cur, value, G);
            cnt = (1LL * cnt_next * cnt) % mod;
          }
        }
      }
      ret = (ret + cnt) % mod;
    }
  }

  return ret;
}

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

  vector<vector<int>> G(n);
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    x--; y--;

    G[x].push_back(y);
    G[y].push_back(x);
  }

  dp.resize(n);
  for (auto &v : dp) {
    v.resize(2);
    fill(v.begin(), v.end(), -1);
  }

  int ans = solve(0, -1, 0, G);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 20992
#include <bits/stdc++.h>
using namespace std;
//Author: Ezio Sam
/* Shorthands */
#define ll long long
#define pb push_back
#define em emplace_back
#define mp make_pair
#define sp " "
#define cs "Case "
#define fi first
#define sn second

/* STL */
#define mem(a,n) memset(a, n, sizeof(a));
#define all(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define sz(x)  (int)x.size()
#define mx(v)  *max_element(v.begin(),v.end())
#define mxi(v) distance(v.begin(),max_element(v.begin(),v.end()))
#define mxa(a) *max_element(a, a.size())
#define r(a)   reverse(a.begin(),a.end())
/* loops */
#define fa(i, a, b) for (auto (i) = (a); (i) < (b); ++(i))
#define fr(i,n)   for(__typeof(n) i=0;i<(n);i++)
#define fn(i,n)   for(__typeof(n) i=1;i<=(n);i++)
/*Special*/
#define Ezio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(something)  cerr<<#something<<" - "<<something<<"\n";

int main()
{

   Ezio
   ll t,m,n,x,a,b;
   string s;

   cin>>n;

   vector<ll>v(n);
   fr(i,n)cin>>v[i];
   a=1e9;
   for (ll i=-100;i<101;i++){
       b=0;
       fr(j,n){
         b+= ((i-v[j]) * (i-v[j]));
       }
       a=min(a,b);
   }

   cout<<a<<endl;
   return 0;
}


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

int main(){
  int N, M; cin >> N >> M;
  vector<P> vec(N);
  for(int i = 0; i < N; i++){
    cin >> vec[i].first >> vec[i].second;
  }
  sort(vec.begin(), vec.end());
  ll ans = 0;
  for(int i = 0; i < N; i++){
    if(M >= vec[i].second){
      ans += vec[i].first*vec[i].second;
      M -= vec[i].second;
    }
    else{
      ans += M*vec[i].first;
      M = 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
  long N,K,S;
  cin >> N>>K>>S;
  long B[N];

  if(K!=0){
  	for(int i=0; i<K; i++) B[i]= S ;
  	for(int i=K; i<N; i++){
      if(S!=1000000000) B[i]=S+1 ;
      else B[i]=S-1;
    }
  }
  else {
  	for(int i=0; i<N; i++){
      if(S!=1000000000) B[i]=S+1;
      else B[i]=S-1;
    }
  }
  
  cout << B[0];
  for(int i=1; i<N; i++) cout << " " << B[i]; 
  cout << endl;
    
}

Measured memory_bytes: 2048
N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = input().split()
    A.append(int(a))
    B.append(int(b))

for i in range(1, N + 1):
    count = 0
    for j in range(M):
        if A[j] == i or B[j] == i:
            count += 1
    print(count)

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

int main() {
    int counter = 1, temp = 0;
    bool count = true;
    for (int i = 0; i < 5; i++) {
        cin >> temp;
        if (count) {
            if (temp == 0) {
                count = false;
            } else {
                counter++;
            }
        }
    }
    cout << counter;
}

Measured memory_bytes: 3624
"""
二分探索木を構成する
"""
import copy

class Node:
    def __init__(self, node_id, parent=None, left=None, right=None):
        self.node_id = node_id
        self.parent = parent
        self.left = left
        self.right = right

class Tree:
    def insert_root_node(self, new_id):
        global root_node #途中でインスタンス化すると水の泡なんですよ
        root_node = Node(new_id)

    def insert_node(self, root_id, new_id): #new_idは追加するノード
        compare_node = root_node #はじめはrootから比較スタート
        new_node = Node(new_id) #インスタンス化
        while compare_node != None: #compare_nodeが存在するとき
            #この下の一行は最重要アイディア
            #親の可能性がある時，とりあえず代入して情報を記録しておく
            new_node.parent = compare_node 
            #右か左か
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        #compare_node == Noneの時，上の２つの分岐のどっちからきたかわからない
        #そのため，親と比較し直す必要がある
        if new_node.parent.node_id < new_id:
            new_node.parent.right = Node(new_id)
        else:
            new_node.parent.left = Node(new_id)

def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)


tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if root_node == None: #何も入ってない時
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(root_id, new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()





Measured memory_bytes: 105764