akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
void Store_A(int A[100][100], int n, int m)
{
    int i,j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
		    scanf("%d", &A[i][j]);
		}
	}
}

void Store_b(int* b, int m)
{
    int i;
	for (i = 0; i < m; i++)
	{
	    scanf("%d", b+i);
	}
}

void Print_Ans(int* Ans, int n, int m, int A[100][100], int* b)
{
    int i,j;
    
    for (i = 0; i < n; i++)
    {
		for (j = 0; j < m; j++)
		{
		    *(Ans+i) += A[i][j] * b[j];
		}
	}
	
	for (i = 0; i < n; i++)
	{
		printf("%d\n", *(Ans+i));
	}
    
}

int main()
{
	int A[100][100], b[100], Ans[100]={0};
	int n, m;

	scanf("%d%d", &n, &m);
	Store_A(A, n, m);
    Store_b(b, m);
    Print_Ans(Ans, n, m, A, b);
	return 0;
}


Measured memory_bytes: 2084
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

max_sum = 0
min_sum = 0


ans = 0
for i in range(0, N+1):
    max_sum += N-i
    min_sum += i 
    if i >= K-1:
        ans += (max_sum - min_sum + 1) % MOD
print(ans%MOD)

Measured memory_bytes: 9184
def BFS(i,A):
  dist=[0]*N
  d=[-1]*N
  d[i]=0#未訪問ならd=-1,訪問済みならiからの距離
  que=[i]
  dist=1
  while que:
    for j in range(len(que)):
      label=que.pop(0)
      for i in range(len(A[label])):
        if d[A[label][i]]==-1:
          d[A[label][i]]=dist
          que+=[A[label][i]]
    dist+=1
  return(d)

N=int(input())
ab=[]
for i in range(N-1):
  ab.append(list(map(int, input().split())))
A=[ [] for i in range(N) ]
for i in range(N-1):
  A[ab[i][0]-1]+=[ab[i][1]-1]
  A[ab[i][1]-1]+=[ab[i][0]-1]
 
 
dist1=BFS(0,A)
dist2=BFS(N-1,A)
Fe=0
Su=0
for i in range(N):
  if dist1[i]<=dist2[i]:
    Fe+=1
  else:
    Su+=1
if Fe>Su:
  print("Fennec")
else:
  print("Snuke")

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

const static ll MOD = (1e+9)+7;

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

int main(){
    ll N,K;cin>>N>>K;
    vector<ll>A(N,0);
    rep(i,N)cin>>A[i];
    ll G = A[0];
    ll MAX = A[0];
    rep1(i,N-1){
        G = gcd(G,A[i]);
        MAX = max(MAX,A[i]);
    }
    if(MAX >= K && K%G == 0){
        cout<<"POSSIBLE"<<endl;
    }else{
        cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x,y,z,k;
    cin>>x>>y>>z>>k;
    ll a[x],b[y],c[z];
    vector<ll> d;
    for(int i=0;i<x;i++)cin>>a[i];
    for(int i=0;i<y;i++)cin>>b[i];
    for(int i=0;i<z;i++)cin>>c[i];
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            d.pb(a[i]+b[j]);
        }
    }
    sort(be(d));
    reverse(be(d));
    vector<ll> ans;
    ll maki=min(k,x*y);
    for(int i=0;i<maki;i++){
        for(int j=0;j<z;j++){
            ans.pb(d[i]+c[j]);
        }
    }
    sort(be(ans));
    reverse(be(ans));
    for(int i=0;i<k;i++){
        cout << ans[i]<<endl;
    }
    return 0;
}



Measured memory_bytes: 42980
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<stack>
#include<algorithm>

using namespace std;

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

vector<int> mise;

int main(){
	while(1){
		int d,m,n;
		scanf("%d",&d);
		if(d==0)break;
		scanf("%d",&n);
		scanf("%d",&m);
		
		mise.clear();
		mise.push_back(0);
		mise.push_back(d);
		
		rep(i,n-1){
			int a;
			scanf("%d",&a);
			mise.push_back(a);
		}
		
		sort(mise.begin(),mise.end());
		
		int ans=0;
		
		rep(j,m){
			int a;
			scanf("%d",&a);
			vector<int>::iterator p = lower_bound(mise.begin(),mise.end(),a);
			
			int val1,val2;
			val1=*p-a;
			val2=a-*(p-1);
			
			if(val1<0)val1*=-1;
			if(val2<0)val2*=-1;
			
			ans+=min(val1,val2);
		}
		
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 1440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//最大公約数
ll gcd(ll a,ll b)
{
    if(a%b == 0)
        return b;
    else
        return gcd(b, a % b);
}

double arr[10];
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int ans = 99999;
    
    for (int i = 0; i < n - 2;i++)
    {
        int a = (s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i+2] - '0') * 1;
        //cout << a<< endl;
        if(abs(a-753)<ans)
            ans = abs(a - 753);
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<vector<int>> flg;
    vector<string> s(n);
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++){
        flg.push_back(vector<int>(26));
        for(int j=0;j<s[i].size();j++){
            flg[i][s[i][j]-'a']++;
        }
    }
    vector<int> res(26);
    for(int i=0;i<26;i++){
        int ans=1e9;
        for(int j=0;j<n;j++){
            ans=min(ans,flg[j][i]);
        }
        res[i]=ans;
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<res[i];j++)printf("%c",'a'+i);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder.BC081
{
    public class B
    {
        public static void Main()
        {
            Console.ReadLine();
            var c = 0;
            var nums = Console.ReadLine().Split(" ").Select(n => int.Parse(n)).ToArray();

            while (nums.All(n => n % 2 == 0))
            {
                c++;
                for (int i = 0; i < nums.Length; i++)
                {
                    nums[i] = nums[i] / 2;
                }
            }
            Console.WriteLine(c);
        }
    }
}

Measured memory_bytes: 28612
using System;
 
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
      string[] str=Console.ReadLine().Split(' ');
      int a=int.Parse(str[0]);
      int b=int.Parse(str[1]);
      
      if(a>b){
        for(int i=1;i<=a;i++){
          Console.Write(b);
        }
      }else{
        for(int j=1;j<=b;j++){
          Console.Write(a);
        }
      }
}
  }
}

Measured memory_bytes: 11092
#include <iostream>

using namespace std;

int main() {

	int h[1000], w[1000];
	int end_of_input;

	for (int i = 0;; i++) {
		cin >> h[i] >> w[i];
		if (h[i] == 0 && w[i] == 0) {
			end_of_input = i;
			break;
		}
	}
	
	for (int i = 0; i < end_of_input; i++) {
		for (int j = 0; j < h[i]; j++) {
			for (int k = 0; k < w[i]; k++) {
				
				//?????????????????????????????????????????????????????¨??????
				if (j == 0 || j == h[i]-1 || k == 0 || k == w[i]-1) {
					cout << "#";
				}
				else {
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;

}

Measured memory_bytes: 3008
N,Q=map(int,(input()).split())
S=input()
l_list=[]
r_list=[]
for i in range(Q):
  l,r=input().split()
  l_list.append(int(l))
  r_list.append(int(r))
count=0
AC_count=[0]
for i in range(1,N+2):
  if S[i-1:i+1]=="AC":
    count+=1
  AC_count.append(count)
AC_count.append(count)
k=0
for j in range(Q):
  k=AC_count[r_list[j]-1]-AC_count[l_list[j]-1]
  print(k)


Measured memory_bytes: 14232
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;
    cin>>N>>X;
    vector<int>D(N+1);
    D[0]=0;
    for(int i=0;i<N;i++){
        int x;
        cin>>x;
        D[i+1]=D[i]+x;
    }
    int ans=0;
    for(int i=0;i<=N;i++){
        if(D[i]<=X){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
from collections import deque
import sys

sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())

g = tuple(set() for _ in range(n))
for _ in range(m):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)


def choose_an_edge():
    for a, st in enumerate(g):
        if st:
            for b in st:
                return a, b


a, b = choose_an_edge()

dq = deque()
dq.append(a)
dq.append(b)

used = [False] * n
used[a] = True
used[b] = True


def dfs(v, add_prev=False) -> None:
    for u in g[v]:
        if used[u]:
            continue
        if add_prev:
            dq.appendleft(u)
        else:
            dq.append(u)
        used[u] = True
        dfs(u, add_prev=add_prev)
        return


# print(a, b)

dfs(a, add_prev=True)
# print(*map(lambda x: x + 1, dq))

dfs(b, add_prev=False)

print(len(dq))
print(*map(lambda x: x + 1, dq))


Measured memory_bytes: 118024
/*
─────────────────────
───────────████████──
──────────███▄███████
──────────███████████
──────────███████████
──────────██████─────
──────────█████████──
█───────███████──────
██────████████████───
███──████AJ████──█───
███████████████──────
███████████████──────
─█████████████───────
──███████████────────
────████████─────────
─────███──██─────────
─────██────█─────────
─────█─────█─────────
─────██────██────────
─────────────────────
*/

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

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long

int N;
const int maxN = 401;
ll dp[maxN][maxN];
ll a[maxN];

ll getMax(int start, int end) {
	if (start == end) return 0;
	if (dp[start][end] != -1) return dp[start][end];

	ll result = LLONG_MAX;
	ll sum = 0;
	for (int i = start; i <= end; i++) {
		sum += a[i];
	}
	for (int i = start; i < end; i++) {
		ll r1 = getMax(start, i);
		ll r2 = getMax(i + 1, end);
		result = min(result, r1 + r2 + sum);
	}

	return dp[start][end] = result;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	memset(dp, -1, sizeof(dp));
	ll res = getMax(0, N - 1);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 4916
#include "iostream"
#include "stdio.h"
// using namespace std;

int main(int argc, char const *argv[]) {

  int a, b;
  std::string op;
  std::cin >> a >> op >> b;


  if(op == std::string("+"))
  {
      std::cout << a+b << '\n';
  }
  else
  {
    std::cout << a-b << '\n';
  }

  return 0;
}

Measured memory_bytes: 256
//
// Created by Mahmoud Rashad on 11/27/19.
//

#include <bits/stdc++.h>


using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<ii, ii>> vii;


bool check(int x, int k, int n, vector<int> &arr) {
    vector<int> reminders;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int rem = arr[i] % x;
        if (rem) {
            reminders.push_back(rem);
            sum += rem;
        }
    }
    sort(reminders.begin(), reminders.end());
    if (reminders.empty())
        return true;
    long long a = 0;
    for (int i = 0; i < (int)reminders.size(); ++i) {
        a += reminders[i];
        long long b = 1LL * ((int)reminders.size() - i - 1) * x - (sum - a);
        if (a == b && a <= k) {
            return true;
        }
    }
    return false;
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    int sum = 0;
    for (int &x : arr) {
        cin >> x;
        sum += x;
    }

    int ans = 0;
    for (int i = 1; i * i <= sum; ++i) {
        if (sum % i == 0) {
//            cout << i << '\n';
            if (check(i, k, n, arr))
                ans = max(ans, i);
            if (check(sum / i, k, n, arr))
                ans = max(ans, sum / i);
        }
    }

    cout << ans << '\n';

    return 0;
}

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

using namespace std;
typedef long long ll;

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

  ll a[100];
  a[0] = 2, a[1] = 1;
  for (int i = 2; i <= n; i++) {
    a[i] = a[i - 1] + a[i - 2];
  }
  cout << a[n] << endl;

  return 0;
}

Measured memory_bytes: 256
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


s = list(S())
t = list(S())
# s' はなるべく辞書順で前に来るように， t' はなるべくあとに来るように並び替えて比べる
ns = ''.join(sorted(s))
nt = ''.join(sorted(t)[::-1])
if ns < nt:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 8968
def nCr(n,r):
  dividend,divisor = 1,1
  for i in range(r):
    dividend *= n-i
    divisor *= 1+i
    dividend %= MOD
    divisor %= MOD

  return (dividend * pow(divisor, MOD-2, MOD)) % MOD

X,Y = map(int,input().split())
INF = 10**15
MOD = 10**9+7

if (X+Y)%3!=0:
  print(0)
  exit()

n = (-X + 2*Y) // 3
m = (2*X - Y) // 3

if n<0 or m<0:
  print(0)
  exit()

print(nCr(n+m, n))

Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

template <class M> class segment_tree{
public:
	typedef typename M::value_type value_type;
	size_t n;
	vector<value_type> v;
	value_type e = M::unit();
	segment_tree(size_t size){
		n = 1;
		while(n < size) n <<= 1;
		v.resize(2*n, e);
		for(size_t i=1; i<n+size; ++i) v[i] = e;
	}
	segment_tree(vector<value_type> a){
		size_t size = a.size();
		n = 1;
		while(n < size) n <<= 1;
		v.resize(2*n, e);
		for(size_t i=0; i<size; ++i) v[n+i] = a[i];
		for(size_t i=n-1; i>0; --i) v[i] = M::operate(v[2*i], v[2*i+1]);
	}
	void point_update(size_t k, value_type val){
		k += n;
		v[k] = val;
		k >>= 1;
		while(k > 0){
			v[k] = M::operate(v[2*k], v[2*k+1]);
			k >>= 1;
		}
	}
	void point_operate(size_t k, value_type lval){
		k += n;
		v[k] = M::operate(lval, v[k]);
		k >>= 1;
		while(k > 0){
			v[k] = M::operate(v[2*k], v[2*k+1]);
			k >>= 1;
		}
	}
	value_type range_get(size_t l, size_t r){ // [l, r)
		value_type lres = e;
		value_type rres = e;
		l += n;
		r += n;
		while(l < r){
			if(l & 1){
				lres = M::operate(lres, v[l]);
				++l;
			}
			if(r & 1){
				--r;
				rres = M::operate(v[r], rres);
			}
			l >>= 1;
			r >>= 1;
		}
		return M::operate(lres, rres);
	}
	value_type operator[](size_t k){
		return v[k+n];
	}
};
struct plus_monoid{
	using value_type = Int;
	static value_type unit(){
		return 0;
	}
	static value_type operate(value_type l, value_type r){
		return l + r;
	}
};
struct min_monoid{
	using value_type = Int;
	static value_type unit(){
		return 1e9;
	}
	static value_type operate(value_type l, value_type r){
		return min(l, r);
	}
};


int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	Int n, m; cin >> n >> m;
	string s; cin >> s;
	vector<Int> a(n+1, 1e9);
	a[n] = 0;
	segment_tree<min_monoid> st(a);
	for(Int i=n-1; i>=0; --i)
		if(s[i] == '0'){
			a[i] = st.range_get(i+1, min(i+m+1, n+1)) + 1;
			st.point_update(i, a[i]);
		}
	if(a[0] > 1e8){
		cout << -1 << "\n";
		return 0;
	}
//	for(Int i=0; i<=n; ++i)
//		cout << i << " " << a[i] << "\n";
	vector<Int> ans;
	for(Int i=0; i<=n; ++i){
		for(Int j=1; j<=m&&i+j<=n; ++j){
			if(a[i]-1 == a[i+j]){
				ans.push_back(j);
				i = i+j-1;
				break;
			}
		}
	}
	for(size_t i=0; i<ans.size(); ++i)
		cout << ans[i] << " \n"[i+1==ans.size()];
}

Measured memory_bytes: 5232
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		int strN = 1; // 文字列を何行受け取るか
		for (int i = 0; i < strN; i++) {
			line += br.readLine() + " ";
		}
		String[] param = line.split(" ");

		TableSlide(param);
	}

	static void TableSlide(String[] param) {
		int W = Integer.parseInt(param[0]);
		int a = Integer.parseInt(param[1]);
		int b = Integer.parseInt(param[2]);

		if (a < b) {
			int slide = b - (a + W);
			if (slide < 1) {
				System.out.println("0");
			} else {
				System.out.println(slide);
			}
		} else {
			int slide = a - (b + W);
			if (slide < 1) {
				System.out.println("0");
			} else {
				System.out.println(slide);
			}
		}

	}

}

Measured memory_bytes: 21076
import sys
sys.setrecursionlimit(500000)

N, A, B, C = map(int, input().split())
L = [int(input()) for i in range(N)]

kumi = []
abcx = ['A', 'B', 'C', 'X']

def dfs(arr: list):
    if len(arr) == N:
        kumi.append(arr[:])
        return
    for k in ['A', 'B', 'C', 'X']:
        arr.append(k)
        dfs(arr)
        arr.pop()

dfs([])

ans = float('inf')
for k in kumi:
    if set(k) & set(['A', 'B', 'C']) != set(['A', 'B', 'C']):
        continue
    tmp = 0
    a = 0
    b = 0
    c = 0
    for i in range(N):
        if k[i] == 'A':
            if a > 0:
                tmp += 10
            a += L[i]
        elif k[i] == 'B':
            if b > 0:
                tmp += 10
            b += L[i]
        elif k[i] == 'C':
            if c > 0:
                tmp += 10
            c += L[i]
    tmp += abs(A-a)
    tmp += abs(B-b)
    tmp += abs(C-c)
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 63852
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i+=1)
#define reps(i,a,b) for(int i=a;i>=b;i-=1)
#define vi vector<int>
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define in(x) int x; cin>>x;
#define inn(x, y) int x, y; cin>>x>>y;
#define mi unordered_map<int,int>
#define mem(x) memset(x, 0, sizeof(x))
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int32_t main(void){
	IOS;
	
	inn(n, m);
	int arr[n+1];
	rep(i, 1, n+1) cin>>arr[i];
	vector<vi> v(n+1);
	
	rep(i, 0, m)
	{
		inn(x, y);
		v[x].pb(y);
		v[y].pb(x);
	}
	
	int ans = 0;
	rep(i, 1, n+1)
	{
		if(v[i].size() == 0) ans+=1;
		else
		{
			bool res = true;
			rep(j, 0, v[i].size())
			{
				if(arr[i] <= arr[v[i][j]])
				{
					res = false;
					break;
				}
			}
			if(res) ans += 1;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 9800
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int quickpow(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)
		res = res * a;
		a *= a;
		b >>= 1;
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	printf("%d",quickpow(n,3));
	return 0;
}

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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 60;
map<ll, ll> d[N];

ll fnd(int n, ll msk) {
	if (!msk) {
		return 1ll << n;
	}
	if (d[n].find(msk) != d[n].end()) {
		return d[n][msk];
	}
	forn(i, N) {
		if (msk & (1ll << i)) {
			ll res = fnd(n, msk ^ (1ll << i));
			ll res1 = 0ll;
			forn(j, N) {
				if (res & (1ll << j)) {
					res1 |= (1ll << (j % i));
				}
			}
			return d[n][msk] = (res | res1);
		}
	}
	assert(0);
	return -1;
}

int a[N];
int b[N];

int main () {
	//std::ios::sync_with_stdio(false);
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	int n;
	cin >> n;
	forn(i, n) {
		cin >> a[i];
	}
	forn(i, n) {
		cin >> b[i];
	}
	ll tekmsk = 0ll;
	ford(i, 1, 51) {
		ll ostmsk = (1ll << i) - 2;	
		bool ok = 1;
		forn(j, n) {
			ll res0 = fnd(a[j], tekmsk);
			bool fnd1 = 0;
			forn(k, N) {
				if (res0 & (1ll << k)) {
					ll res1 = fnd(k, ostmsk);	
					if (res1 & (1ll << b[j])) {
					 	fnd1 = 1;
					 	break;
					}
				}
			}
			if (!fnd1) {
				ok = 0;
				break;	
			}
		}
		if (!ok) {
			tekmsk |= (1ll << i);
		}
	}
	forn(j, n) {
		ll res0 = fnd(a[j], tekmsk);
		if (!(res0 & (1ll << b[j]))) {
			puts("-1");
			return 0;
	 	}
	}
	cout << tekmsk << endl;



	return 0;
}

Measured memory_bytes: 3840
import scala.io.Source.stdin

object Main {
  val r = Array(2,3,5,7)

  def twoPow(d:Int,s:Int):(Int,Int) = {
    if(d%2 == 1) (d,s)
    else twoPow(d>>1,s+1)
  }

  def maybePrime(i:Int,d:Int,s:Int, n:Int):Boolean = {
    if(i>3) true
    else {
      val a = r(i)
      val x = BigInt(a).modPow(d,n).toLong

      if(x==1 || x==n-1) maybePrime(i+1,d,s,n)
      else repeat(s-1,BigInt(x).modPow(2,n).toLong, i, d, s, n)
    }
  }

  def repeat(j:Int, x:Long, i:Int, d:Int, s:Int, n:Int):Boolean = {
    if(j==0) false
    else if(x==1) false
    else if(x==n-1) maybePrime(i+1,d,s,n)
    else repeat(j-1,BigInt(x).modPow(2,n).toLong,i,d,s,n)
  }

  def isPrime(n:Int):Boolean = {
    if(n==2 || n==3 || n==5 || n==7) true
    else if(n%2==0) false
    else {
      val (d,s) = twoPow(n-1,0)
      maybePrime(0,d,s,n)
    }
  }

  def main(args:Array[String]) = {
    println(stdin.getLines.count{ x => isPrime(x.toInt) })
  }
}

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

using ll = long long;

class convex_hull_trick {
    using T = long long;

    bool check(int f1, int f2, T aa, T bb) {
        return (a[f2] - a[f1]) * (bb - b[f2]) >= (b[f2] - b[f1]) * (aa - a[f2]);
    }
    bool check(int f1, int f2, int f3) {
        return (a[f2] - a[f1]) * (b[f3] - b[f2]) >= (b[f2] - b[f1]) * (a[f3] - a[f2]);
    }

    T f(int idx, T x) {
        return a[idx] * x + b[idx];
    }

public:
    convex_hull_trick() = default;
    // a : sorted sequence
    convex_hull_trick(std::vector<T> const& a_, std::vector<T> const& b_) {
        assert(a_.size() == b_.size());
        for(int i = 0; i < a_.size(); ++i) {
            add_f(a_[i], b_[i]);
        }
    }

    void add_f(T aa, T bb) {
        while(a.size() >= 2 && check(a.size() - 2, a.size() - 1, aa, bb)) {
            a.pop_back();
            b.pop_back();
        }
        a.push_back(aa);
        b.push_back(bb);
    }
    T min(T x) {
        assert(a.size() > 0);
        while(a.size() >= 2 && f(0, x) >= f(1, x)) {
            a.pop_front();
            b.pop_front();
        }
        return a[0] * x + b[0];
    }

    bool empty() const {
        return a.size() == 0;
    }

private:
    std::deque<T> a, b; // functions
};

int main() {
    int N, T;
    cin >> N >> T;
    // (f, t, p)
    vector<tuple<ll, ll, ll>> songs;
    for(int i = 0; i < N; ++i) {
        ll t, p, f;
        cin >> t >> p >> f;
        if(t > T) {
            continue;
        }
        songs.emplace_back(f, t, p);
    }
    N = songs.size();
    sort(songs.begin(), songs.end());

    vector<vector<ll>> dp(N + 1, vector<ll>(T + 1));
    vector<convex_hull_trick> cht(T + 1);
    ll res = 0;
    for(int i = 0; i < N; ++i) {
        ll fi, ti, pi;
        tie(fi, ti, pi) = songs[i];
        for(int j = T; j >= ti; --j) {
            if(cht[j - ti].empty()) {
                continue;
            }
            dp[i][j] = -cht[j - ti].min(fi) - fi * fi + pi;
            res = max(res, dp[i][j]);
            cht[j].add_f(-2 * fi, -dp[i][j] + fi * fi);
        }
        dp[i][ti] = max(dp[i][ti], pi);
        res = max(res, dp[i][ti]);
        cht[ti].add_f(-2 * fi, -dp[i][ti] + fi * fi);
    }
    cout << res << endl;
}


Measured memory_bytes: 121400
#include <bits/stdc++.h>
using namespace std;
#define int                     long long int
#define ld                      long double
#define pb                      push_back
#define MOD                     1000000007
#define inf                     3e18
#define vi                      vector<int>
#define vld                     vector<ld>
#define pii                     pair<int,int>
#define mii                     map<int,int>
#define fi                      first
#define se                      second
#define fastIO                  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << " "<< name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}

void inp_out()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
    #endif
}

int32_t main()
{
	fastIO
	inp_out();
	ld a,b;
	cin>>a>>b;
	ld res=a*b;
	int ans=res;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3736
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 100001;
static const ll MOD = 1000000007;
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; }
template<class T> inline bool int_ceil(T a, T b) { T res = a / b; if(a % b != 0) res++; return res; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif

int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	int n; cin >> n;
	int a, b; cin >> a >> b;
	vector<int> v(3);
	rep(i, n){
		int c; cin >> c;
		if(c <= a){
			v[0]++;
		}
		else if(a < c && c <= b){
			v[1]++;
		}
		else{
			v[2]++;
		}
	}
	// print(v);

	cout << min(v[0], min(v[1], v[2])) << endl;

	return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h> 
#include <time.h>
#define F(i,a,b) for(long long i=a;i<=(b);++i)
#define dF(i,a,b) for(long long i=a;i>=(b);--i) 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-10
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 1e5+10;
const int N = 1e5+10;
const int E = 1e6+10;  
int n,m;
vector<int> g[maxn];
int ans[maxn];
void bfs(){
	queue<int> Q;
	Q.push(1);
	while(!Q.empty()){
		int u = Q.front();Q.pop();
		for(int i=0;i<g[u].size();i++){
			int k = g[u][i];
			if(ans[k]) continue;
			ans[k] = u;
			Q.push(k);
		}	
	}
}

int main(){
	cin>>n>>m;
	int a,b;
	F(i,1,m){
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	bfs();
	bool flg = 1;
	F(i,2,n){
		if(!ans[i]) flg = 0;
	}
	if(flg){
		printf("Yes\n");
		F(i,2,n){
			cout<<ans[i]<<endl;
		}
	}
	else{
		printf("No\n");	
	}
}

Measured memory_bytes: 10336
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    vector<ll> dp(1<<n, INF<ll>);
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        int val = 0;
        for (int j = 0; j < b[i]; ++j) {
            int x;
            scanf("%d", &x);
            val += (1 << (x-1));
        }
        dp[val] = min(dp[val], (ll)a[i]);
    }
    for (int i = 0; i < (1<<n); ++i) {
        for (int j = i&(i-1); j != i; j = i&(j-1)) {
            dp[j] = min(dp[j], dp[i]);
        }
    }
    for (int i = 0; i < (1<<n); ++i) {
        for (int j = i&(i-1); j != i; j = i&(j-1)) {
            dp[i] = min(dp[i], dp[j]+dp[i^j]);
        }
    }
    cout << (dp.back() >= INF<ll> ? -1 : dp.back()) << "\n";
    return 0;
}

Measured memory_bytes: 256
// class point	の練習（クラスの高度な実装）
#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;



int main() {
	int a, b;
	char op[2] = "+";
	while (1) {
		cin >> a >>  op[0]  >> b;
		if (strcmp(op, "?") == 0) {
			break;
		}
		else if (strcmp(op, "+") == 0)cout << a + b << endl;
		else if (strcmp(op, "-") == 0)cout << a - b << endl;
		else if (strcmp(op, "*") == 0)cout << a * b << endl;
		else if (strcmp(op, "/") == 0)cout << a / b << endl;
	}
	


	return 0;
}



Measured memory_bytes: 3064
n,h = map(int,input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i],b[i] = map(int,input().split())

ama = max(a)
b.sort(reverse=True)
c = 0
i = 0
while(h > 0):
    if(i >= n):break
    if(b[i] > ama):
        c += 1
        h -= b[i]
        i += 1
    else:
        break
h = max(0,h)
c += h // ama
if(h % ama != 0):c += 1
print(c)

Measured memory_bytes: 11312
N=int(input())
B = [int(i) for i in input().split()] 
A=[0]*N
A[0]=B[0]
for i in range(N-2):
    A[i+1]=B[i]
    if B[i+1]>=B[i]:
        A[i+2]=B[i+1]
    else:
        A[i+1]=B[i+1]
if B[N-2]<=B[N-3]:
    A[N-1]=B[N-2]
ans=sum(A)
print(ans)

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

const int nmax = 8;
vector<vector<bool>> graph(nmax, vector<bool>(nmax, false));
vector<bool> visited(nmax, false);

int dfs(int v, int n, vector<bool> &visited){
    
    bool all_visited = true;
    
    for (int i = 0; i < n; i++){
        if (!visited[i]) all_visited = false;
    }
    
    if (all_visited) return 1;
    
    int res = 0;
    
    for (int i = 0; i < n; i++){
        if (!graph[v][i]) continue;
        if (visited[i]) continue;
        
        visited[i] = true;
        res += dfs(i, n, visited);
        visited[i] = false;
    }
    return res;
}

int main(){
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        
        a--, b--;
        
        graph[a][b] = true;
        graph[b][a] = true;
    }
    
    visited[0] = true;
    cout << dfs(0, n, visited) << endl;
}

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

using namespace std;
using ll = long long;

vector<int> sieve_of_eratosthenes(int n) {
    vector<int> primes(n);
    for (int i = 2; i < n; ++i)
        primes[i] = i;
    for (int i = 2; i*i < n; ++i)
        if (primes[i])
        for (int j = i*i; j < n; j+=i)
            primes[j] = 0;
    return primes;
}

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

    ll n;

    cin >> n;

    vector<int> primes = sieve_of_eratosthenes(static_cast<int>(sqrt(n + 1)));
    primes.erase(remove(primes.begin(), primes.end(), 0), primes.end());

    vector<ll> q;
    int i = 0;
    bool next = false;

    while(n != 1) {
        if(i == primes.size()) {
            q.emplace_back(1);
            break;
        }
        if(n % primes.at(i) == 0) {
            if(!next) {
                q.emplace_back(1);
                n /= primes.at(i);
                next = true;
            } else {
                q.back()++;
                n /= primes.at(i);
            }
        } else {
            ++i;
            next = false;
        }
    }

    int ans = 0;

    for(int i: q) {
        for(int j = 1; true; ++j) {
            i -= j;
            if(i >= 0) ++ans;
            else break;
        }
    }

    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 7160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC159D
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            string[] Ainput = Console.ReadLine().Split(' ');
            long[] A = new long[N];
            for(int i = 0; i < N; i++)
            {
                A[i] = long.Parse(Ainput[i]);
            }
            long[] kosuu = new long[N];
            for (int i = 0; i < N; i++)
            {
                kosuu[A[i] - 1] += 1;
            }
            long[] erabi = new long[N];
            long goukei = 0;
            for(int i = 0; i < N; i++)
            {
                if (kosuu[i] > 1)
                {
                    erabi[i] = kosuu[i] * (kosuu[i] - 1) / 2;
                    goukei += erabi[i];
                }
            }
            for(int k=0; k < N; k++)
            {
                long Ai = A[k];
                if (kosuu[Ai - 1] == 1)
                {
                    Console.WriteLine(goukei);
                }
                else
                {
                    long ans = goukei - erabi[Ai - 1] + (kosuu[Ai - 1] - 1) * (kosuu[Ai - 1] - 2) / 2;
                    Console.WriteLine(ans);
                }

            }
        }
    }
}


Measured memory_bytes: 53960
//  Mayank Agarwal
//  IIIT Hyderabad



#include<bits/stdc++.h>
using namespace std;
const long long int M = 1000000007; 
#define ll long long int
#define ld double
#define pb push_back
#define mp make_pair
ll power(ll x, ll y,  ll p) 
{ 
    ll res = 1;      
    x = x % p;   
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;x = (x*x) % p; 
    } return res%p; 
} 
ll modinver(ll a,ll b)
{
    return (power(a,1,M)*power(b,M-2,M))%M;
}
void SieveOfEratosthenes(int n) 
{   
    bool prime[10005]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
} 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    ll n;
    cin>>n;
    cin>>s;
    // s.length();
    if(n%2)
    {
        cout<<"No"<<'\n';
        return 0;
    }
    for (int i = 0; i < n/2; ++i)
    {
        if(s[i]!=s[i+n/2])
        {
            cout<<"No"<<'\n';
            return 0;
        }
    }
    cout<<"Yes"<<'\n';
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// 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("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

// {{{ BIT
struct BIT{
    vector<int> data;
    int leng;
    BIT( int n ){
        init(n);
    }
    void init(int n){
        leng = n;
        data.assign(n,0);
        for(int i = 0; i < n; i++ ){
            data[i] = 0;
        }
    }
    int sum(int i){
        int s = 0;
        for( ; i>0; i -= i & -i ){
            s += data[i];
        }
        return s;
    }
    void add(int i, int x){
        for( ; i<=leng ; i += i & -i ){
            data[i] += x;
        }
    }
};
// }}}

int main() {

    int N;
    Scd(N);
    vi a(N);
    Rep(i,N) Scd(a[i]);
    vi ca(a.begin(),a.end());
    sort(ca.begin(),ca.end());

    int l = 0;
    int r = N;
    int cc;
    int c;
    vi b(N+1);
    BIT bit(N*2+20);
    // (l,r]
    while( r-l > 1 ){
        cc = (r+l)/2;
        c = ca[cc];
        Rep(i,N) b[i+1] = a[i]>=c?1:-1;
        Rep(i,N){
            b[i+1] += b[i];
        }
        ll sum = 0;
        bit.init(N*2+20);
        Rep(i,N+1){
            sum += bit.sum(b[i]+N+3);
            bit.add(b[i]+N+3,1);
        }
        // printf ("%d:%lld\n", c, sum );
        if( sum >= (1ll*N*(N+1)/2+1)/2 ) l = cc;
        else r = cc;
    }

    printf ("%d\n", ca[l] );

    return 0;
}

// 3
//   -1  1 -1
// 0 -1  0 -1


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll c[3][3];
    ll sum=0;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >>c[i][j];
            sum+=c[i][j];
        }
    }
    if(sum%3!=0){
        puts("No");
        return 0;
    }
    sum/=3;
    vector<ll>a(3);
    vector<ll>b(3);
    a[1]=c[1][0]+c[1][1]+c[0][1]+c[2][1]+c[1][2]-sum;
    b[0]=c[1][0]-a[1];
    b[1]=c[1][1]-a[1];
    b[2]=c[1][2]-a[1];
    a[0]=c[0][1]-b[1];
    a[2]=c[2][1]-b[1];
    bool flg=true;
    if(c[0][0]!=a[0]+b[0])flg=false;
    if(c[0][2]!=a[0]+b[2])flg=false;
    if(c[2][0]!=a[2]+b[0])flg=false;
    if(c[2][2]!=a[2]+b[2])flg=false;
    if(flg)puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <list>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define crep(i) for(char i='a';i<='z';i++)
typedef long long ll;
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
#define MOD 1000000007
#define EPS 10e-8

ll d[100007],p;

int  depth(ll k[],ll parent[],ll i){
    if(parent[i]==-1){
        return 0;
    }
    else if(d[i]!=0){
        return d[i];
    }
    else{
        p = depth(k,parent,parent[i])+1;
        d[i] = p; 
        return p;
    }
}

int main(){
    ll N,k[100007],t,x,parent[100007];
    rep(i,100007){
        parent[i]=-1;
    }
    cin >> N;
    vector<vector<ll>> root(100007);
    rep(i,N){
        cin >> x;
        cin >> k[x];
        rep(j,k[x]){
            cin >> t;
            parent[t] = x;
            root[x].push_back(t);
        }
    }
    rep(i,N){
        // 節点番号
        printf("node %d: ",i);

        // 親
        if(parent[i]==-1){
            printf("parent = -1, ");
        }
        else{
            cout << "parent = "  << parent[i] << ", " ;
        }

        // 深さ
        printf("depth = %d, ",depth(k,parent,i));

        // 種類
        if(parent[i]==-1){
            printf("root, ");
        }
        else if(k[i]>0){
            printf("internal node, ");
        }
        else{
            printf("leaf, ");
        }

        // 子
        cout << "[";
        rep(j,k[i]){
            cout << root[i][j];
            if(j!=k[i]-1){
                cout << ", ";
            }
        }
        cout << "]";

        cout << endl;
    }
}


Measured memory_bytes: 9032
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace PastQuestions
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new Input(Console.In));
        }

        public void Solve(Input input)
        {
            var answer = Solve2(input);
            Console.Write($"{answer[0]} {answer[1]} {answer[2]}");
        }
        public int[] Solve2(Input input)
        {
            var n = input.ReadInt;
            var y = input.ReadInt;

            var answer = new int[3] { -1, -1, -1 };
            for (var i = 0; i <= n; i++)
            {
                var total = 10000 * i;
                var temp = total;
                for (var j = 0; j <= n - i; j++)
                {
                    total = temp;
                    total += 5000 * j;
                    
                    var k = n - i - j;
                    total += 1000 * k;
                    if (y == total)
                    {
                        answer[0] = i;
                        answer[1] = j;
                        answer[2] = k;
                        return answer;
                    }
                }
            }
            return answer;
        }
    }

    public class Input
    {
        private TextReader Stream { get; }
        private char Separator { get; }
        private Queue<string> InputStream { get; }

        public Input(TextReader stream, char separator = ' ')
        {
            Stream = stream;
            Separator = separator;
            InputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if (InputStream.Count != 0) return InputStream.Dequeue();
                string[] tmp = Stream.ReadLine().Split(Separator);
                for (int i = 0; i < tmp.Length; ++i)
                    InputStream.Enqueue(tmp[i]);
                return InputStream.Dequeue();
            }
        }

        public string ReadLine => Stream.ReadLine();
        public int ReadInt => int.Parse(Read);
        public long ReadLong => long.Parse(Read);
        public double ReadDouble => double.Parse(Read);
        public int[] ReadIntArray => Stream.ReadLine().Split(Separator).Select(i => int.Parse(i)).ToArray();
        public long[] ReadLongArray => Stream.ReadLine().Split(Separator).Select(l => long.Parse(l)).ToArray();
    }
}


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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int A, B;
  cin >> A >> B;
  if (abs(A - B) <= 1)
    cout << "Yay!" << endl;
  else
    cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef long long ll;
const ll INF=1e9+7;

ll max(ll a,ll b){
	if(a>b)return a;
	return b;
}

int main(){
	int n;
	cin>>n;
	int f[n][5][2],p[n][11];
	rep(i,n){
		rep(j,5){
			rep(k,2){
				cin>>f[i][j][k];
			}
		}
	}
	rep(i,n){
		rep(j,11){
			cin>>p[i][j];
		}
	}
	ll ans=-INF;
	loop(i,1,1<<10){
		int hmt[n];
		fill(hmt,hmt+n,0);
		rep(k,n){
			rep(j,10){
				int dow=j/2,time=j%2,josino=i&(1<<j);
				if(f[k][dow][time]&&josino)hmt[k]++;
			}
		}
		ll sum=0;
		rep(k,n){
			sum+=p[k][hmt[k]];
		}
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int n;
    cin >> n;
    vector<ll> a(n*3);
    rep(i, n*3) cin >> a[i];
    sort(all(a));
    reverse(all(a));
    ll ans = 0;
    for (int i = 1; i < n*3-n; i+=2) {
        ans += a[i];
    }

    cout << ans << endl;

    return 0;
}

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

#define ll long long
#define SZ 1000

void solve()
{
    string s;
    cin >> s;
    ll ans = 0;
    for(int i=0; i<3; i++)
        if(s[i] == 'R')
            ans = 1;
    if(s[0] == 'R' and s[1] == 'R' and s[2] == 'R')
        ans = 3;
    else if(s[0] == 'R' and s[1] == 'R')
        ans = 2;
    else if(s[2] == 'R' and s[1] == 'R')
        ans = 2;

    cout << ans << endl;
}

int main()
{
    int tc = 1;
    //cin >> tc;
    while(tc--)
    {
        solve();
    }

    return 0;
}




Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define LOWBIT(x) x & (-x)
#define Pair pair<int,int>
#define LL long long
using namespace std;

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

int main ()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if (n>m) swap(n,m);
	if (m-n>=2)
	{
		cout<<0<<endl;
		return 0;
	}
	LL ans=1;
	for (int i=1;i<=n;i++) ans=(ans*i)%MOD;
	for (int i=1;i<=m;i++) ans=(ans*i)%MOD;
	if (n==m) ans=(ans*2)%MOD;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int dp[101][4][2];
int find(string str,int tight,int cnt,int n,int pos,int g)
{  if(pos==n)
{
    if(cnt==g)
    {
        return 1;
    }
    else
        return 0;
}
if(cnt>g)
    return 0;
if(dp[pos][cnt][tight]!=-1)
    return dp[pos][cnt][tight];

    int x=str[pos]-'0';
    if(tight==0)
        x=9;
        int val=0;
for(int i=0;i<=x;i++)
{if(i==0)
{
    val+=find(str,tight&(str[pos]==i+'0'),cnt,n,pos+1,g);
}
else
   val+=find(str,tight&(str[pos]==i+'0'),cnt+1,n,pos+1,g);
}
dp[pos][cnt][tight]=val;
return val;

}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string str;
cin>>str;
int k;
cin>>k;
for(int i=0;i<101;i++)
{
    for(int j=0;j<4;j++)
    {
        for(int k=0;k<2;k++)
            dp[i][j][k]=-1;
    }
}
int n=str.size();


int ans=find(str,1,0,n,0,k);

cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,m,x,i,c1=0,c2=0,j;
	int s[100];
	scanf("%d%d%d",&n,&m,&x);
	for(i=0; i<m; i++)
		scanf("%d",&s[i]);
	if(n>=1&&n<=100&&m>=1&&m<=100&&x>=1&&x<=n-1)
	{
		for(j=x-1; j>0; j--)
		{
			for(i=0; i<m; i++)
				if(j==s[i])
				c1++;
		}
		for(j=x+1; j<n; j++)
		{
			for(i=0; i<m; i++)
				if(j==s[i])
				c2++;
		}
		if(c1<c2)
			printf("%d\n",c1);
		else
			printf("%d\n",c2);
	}
	return 0;
}

Measured memory_bytes: 128