akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define eps 1e-7
using namespace std;

#define MAX 100005
#define NIL -1
struct Node { int p, l, r; };
Node T[MAX];
int n, D[MAX];
void print(int u) {
	int i, c;
	cout << "node " << u << ": ";
	cout << "parent = " << T[u].p << ", ";
	cout << "depth = " << D[u] << ", ";
	if (T[u].p == NIL) cout << "root, ";
	else if (T[u].l == NIL) cout << "leaf, ";
	else cout << "internal node, ";
	cout << "[";
	for (int i = 0, c = T[u].l; c != NIL; ++i, c = T[c].r) {
		if (i) cout << ", ";
		cout << c;
	}
	cout << "]" << endl;
}
void rec(int u, int p) {
	D[u] = p;
	if (T[u].r != NIL) rec(T[u].r, p);
	if (T[u].l != NIL) rec(T[u].l, p + 1);
}
int main() {
	int d, v, c, l, r;
	cin >> n;
	for (int i = 0; i < n; ++i) T[i].p = T[i].l = T[i].r = NIL;
	for (int i = 0; i < n; ++i) {
		cin >> v >> d;
		for (int j = 0; j < d; ++j) {
			cin >> c;
			if (!j) T[v].l = c;
			else T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}
	for (int i = 0; i < n; ++i) if (T[i].p == NIL) r = i;
	rec(r, 0);
	for (int i = 0; i < n; ++i) print(i);
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef string str;

#define f(i, begin, end) for (auto i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define trav(v) for (auto &x : v)
#define dis(v) trav(v) cout << x << " ";
#define deb(x) cerr << #x << ":" << x << "\n"
#define debv(v) trav(v) cerr << x << " ";
#define all(v) v.begin(), v.end()
#define nl cout << "\n"

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        ll a, b, n, m, i, j, k;
        str s1, s2;
        ll ch1, ch2;
        // cin >> n;
        cin >> ch1 >> ch2;
        cout << 6 - (ch1 + ch2) << "\n";
        // cin >> n;
        // vector<ll> v(n);
        // f(i, 0, n) cin >> v[i];
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define ALL(a) a.begin(), a.end()
typedef long long ll;
const int INF = 100100100;
using namespace std;

class UnionFind {
  public:
    // 親の番号を格納する。親の場合 -1 になる
    vector<int> Parent;

    // 宣言されたとき Parent の値はすべて -1 にする
    UnionFind(int N) { Parent = vector<int>(N, -1); }

    // 与えられた値 x がどの親であるか調べる
    int root(int x) {
        // x が親だったとき
        if (Parent[x] < 0)
            return x;
        // 辺の縮約をいっしょにおこなう
        return Parent[x] = root(Parent[x]);
    }

    // 木の全体の数を返す
    int size(int x) {
        // マイナスがついているのは root
        // 以下の数をマイナスの値で管理しているから
        return -Parent[root(x)];
    }

    // 2つの引数を同じ親にする
    bool merge(int x, int y) {
        x = root(x);
        y = root(y);

        // 同じ親の場合くっつけない
        if (x == y)
            return false;

        // x のほうが必ず大きな size にしたい
        if (size(x) < size(y))
            swap(x, y);
        Parent[x] += Parent[y];
        Parent[y] = x;
        return true;
    }
};

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

    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    REP(i, M) cin >> A[i] >> B[i];

    UnionFind uni(N + 1);
    vector<ll> ans(M);
    ans[M - 1] = (ll)N * (N - 1) / 2;

    RREP(i, M - 2) {
        ans[i] = ans[i + 1];
        if (uni.root(A[i + 1]) != uni.root(B[i + 1])) {
            ans[i] -= (ll)uni.size(A[i + 1]) * uni.size(B[i + 1]);
            uni.merge(A[i + 1], B[i + 1]);
        }
    }

    REP(i, M) cout << ans[i] << "\n";

    return 0;
}

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

char s[110];
int n, sol = 110;

int chk( char c ){
	
	int ret = 0;
	int last = -1;
	s[n] = c;
	for ( int i = 0; i <= n; i++ )
		if ( s[i] == c ){
			ret = max(ret, i - last - 1);
			last = i;
		}
	
	return (last < 0) ? 110 : ret;
}

int main(){
	scanf("%s", s);
	n = strlen(s);
	for ( char c = 'a'; c <= 'z'; c++ )
		sol = min(sol, chk(c));
	
	printf("%d\n", sol);
	
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

int main(){
	string s;
	cin>>s;
	int n=0,m=0;
	int flg[s.size()];
	rep(i,s.size()){
		if(s[i]!='C' && s[i]!='F')flg[i]=false;
		else flg[i]=true;
	}
	string ans="";
	rep(i,s.size()){
		if(flg[i])ans+=s[i];
	}
	if(ans.size()==0){
		cout<<"No"<<endl;
		return 0;
	}
	bool check=false;
	rep(i,ans.size()-1){
		string alt="";
		alt+=ans[i];
		alt+=ans[i+1];
		if(alt=="CF"){
			check=true;
			break;
		}
	}
	cout<<((check)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;

int main(){
	int a , b, c;
	cin >> a >> b >> c;

	if(a >= b && a >= c) cout << b+c << endl;
	else if(b >= a && b >= c) cout << a+c << endl;
	else cout << a+b << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <float.h>
#include <iostream>
#include <map>
using namespace std;

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

	bool bFind = false;
	for (int nA = 1; nA < 10; nA++)
	{
		if (0 != nN%nA)
			continue;

		int nB = nN/nA;
		if (1 > nB || nB > 9)
			continue;

		bFind = true;
		break;
	}

	if (true == bFind)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
constexpr int MOD = 998244353;

template <int N>
struct Eratosthenes
{
    int w[N + 1];
    char sieve[N + 1];
    constexpr Eratosthenes() : w(), sieve()
    {
        w[0] = 0;
        w[1] = 1;
        for (int i = 2; i <= N; i++)
            w[i] = MOD - 1LL * w[MOD % i] * (MOD / i) % MOD;
        for (int p = 2; p <= N; p++)
        {
            if (sieve[p] == 0)
            {
                for (int k = N / p; k > 1; --k)
                {
                    sieve[k * p] = 1;
                    w[k * p] -= w[k];
                    if (w[k * p] < 0)
                    {
                        w[k * p] += MOD;
                    }
                }
                w[p] -= w[1];
            }
        }
    }
};

int main()
{
    constexpr int M = 1000000;
    constexpr auto prime = Eratosthenes<M>();
    long long N, ans = 0;
    int a[1000001] = {};
    cin >> N;
    for (int i = 0, j; i < N; i++)
    {
        cin >> j;
        if ((a[j] += j) >= MOD)
            a[j] -= MOD;
        if ((ans -= j) < 0)
            ans += MOD;
    }
    for (int p = 2; p <= M; p++)
        if (prime.sieve[p] == 0)
            for (int k = M / p; k > 0; --k)
                if ((a[k] += a[k * p]) >= MOD)
                    a[k] -= MOD;
    for (int i = 1; i <= M; i++)
    {
        ans += 1LL * a[i] * a[i] % MOD * prime.w[i] % MOD;
    }
    ans %= MOD;
    if (ans & 1)
        ans = (ans + MOD) >> 1;
    else
        ans = ans >> 1;
    cout << ans << endl;
}


Measured memory_bytes: 9088
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p == NIL) printf("root, ");
  else if(T[u].l == NIL) printf("leaf, ");
  else printf("internal node, ");
  
  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");
  
}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].r != NIL) calcDepth(T[u].r, p);
  if(T[u].l != NIL) calcDepth(T[u].l, p+1);
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;
  
  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);

  //出力 (output)
  for(i=0; i<n; i++) print(i);
  
  return 0;
}



Measured memory_bytes: 6380
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
			　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <memory>
#include <iomanip>
#include <type_traits>

#define rep(i, n) for(Int (i) = 0; (i) < (n); ++(i))
#define all(n) std::begin(n), std::end(n)
#define debug(var) std::cout << #var << ": " << var << "\n"
using Int = int64_t;
constexpr Int INF = INT_MAX;
constexpr Int mod = 1e9 + 7;


void calc() {

	Int N; std::cin >> N;
	std::vector<Int> A(N - 1);
	std::vector<Int> boss(N, 0);
	rep(i, N - 1) {
		Int A; std::cin >> A;
		A--; boss[A]++;
	}
	rep(i, N) {
		std::cout << boss[i] << "\n";
	}

}


int main() {

	calc();

	return 0;
}

Measured memory_bytes: 6372
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb emplace_back
typedef pair<int,int> pi;

int n, vis[100005], out[100005], maxi;
vector<int> g[100005];
vector<pi> edges;
map<pi,int> ans;

void dfs(int x, int p, int col) {
	if (vis[x]) return;
	vis[x] = 1;
	int cnt = 1;
	for (auto i: g[x]) {
		if (i == p) continue;
		int now = (col + cnt) % maxi;
		++cnt;
		// cout << "x: " << x << " i:" << i << ' ' << " col: " << now << '\n';
		ans[pi(x, i)] = now;
		ans[pi(i, x)] = now;
		dfs(i, x, now);
	}
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;	
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
		++out[u], ++out[v];
		edges.pb(u, v);
	}
	for (int i = 1; i <= n; ++i) maxi = max(maxi, out[i]);
	dfs(1, 1, 0);
	cout << maxi << '\n';
	for (auto i: edges) {
		cout << ans[i] + 1<< '\n';
	}
	return 0;
}


Measured memory_bytes: 22904
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>
using namespace std;

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

#define max_n 100

int N;
//vector<int> A;

vector<int> B;


int main() {

	cin >> N;

	rep(i, N) {
		int j;
		cin >> j;
		B.push_back(j);
	}


	int ans = 0;

	ans = B.at(0);

	for (int i = 1; i < N; i++)
	{
		ans += min(B.at(i-1),B.at(i));
	}

	cout << ans <<endl;

	return 0;	
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right)
{
	int n1 = mid - left;
	int n2 = right - mid;
	for( int i = 0; i< n1; i++)	L[i] = A[left+i];
	for( int i = 0; i< n2; i++) R[i] = A[mid+i];
	L[n1] = R[n2] = SENTINEL;
	int i = 0, j = 0;
	for (int k = left; k < right; ++k)
	{
		cnt++;
		if (L[i]<=R[j])
		{
			A[k] = L[i++];
		}
		else
		{
			A[k] = R[j++];
		}
	}
}
void mergeSort( int A[], int n, int left, int right)
{
	if (left+1 < right)
	{
		int mid = (left + right)/2;
		mergeSort(A, n, left, mid);
		mergeSort(A, n, mid, right);
		merge(A, n, left, mid, right);
	}
}


int main(int argc, char const *argv[])
{
	int A[MAX];
	int n;
	cnt = 0;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d",&A[i]);
	}
	mergeSort(A,n,0,n);
	for (int i = 0; i < n; ++i)
	{	
		if(i) cout<<" ";
		cout<<A[i];
	}
	cout<<endl<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 7072
use std::fmt::Debug;
fn read_line() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).expect("No Line");
    buffer
}
fn read_values<T: std::str::FromStr>() -> Vec<T> {
    read_line().trim().split(' ').map(|x| x.parse().ok().expect("Can't Parse")).collect::<Vec<T>>()
}
fn read_multi_line<T: std::str::FromStr>(count: usize) -> Vec<T> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for i in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(buffer.parse().ok().expect("Can't Parse"));
    }
    vec
}

macro_rules! ignore {
    ($id:ident) => {};
}
macro_rules! assign {
    (let $($id:ident),* = $value:expr) => {
        let ($($id), *) = {
            let mut iter = $value.into_iter();
            ($({ignore!($id); iter.next().unwrap()}), *)
        }
    };
}
fn inspect<T: Debug>(vec: &Vec<T>) -> () {
    if let Some(first) = vec.first() {
        println!("Vec({:?}", first);
        for i in 1..vec.len() {
            println!(", {:?}", vec[i]);
        }
        println!(")");
    }else {
        println!("Vec()");
    }
}

fn main() {
    let n = read_line();
    if n.contains('7') {
        println!("Yes");
    }else {
        println!("No");
    }
}


Measured memory_bytes: 2176
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
#include <map>

using namespace std;


int p[200005];
int q[200005];
int r[200005];
int s[200005];

map<pair<int,int>, int>mp;

vector<int>E[2][200005];
int color[200005][2];

int visit[200005];

void dfs(int pos,int c,int type){
	if(visit[pos]==1){return;}

	visit[pos]=1;

	color[pos][type]=c;

	int i;

	for(i=0;i<E[type][pos].size();i++){
		dfs(E[type][pos][i],c,type);
	}
}

int main(){

	int N,K,L;

	scanf("%d %d %d",&N,&K,&L);

	int i;

	for(i=1;i<=K;i++){
		scanf("%d %d",&p[i],&q[i]);
		E[0][p[i]].push_back(q[i]);
		E[0][q[i]].push_back(p[i]);
	}
	for(i=1;i<=L;i++){
		scanf("%d %d",&r[i],&s[i]);
		E[1][r[i]].push_back(s[i]);
		E[1][s[i]].push_back(r[i]);
	}
	int cnt=1;
	for(i=1;i<=N;i++){
		dfs(i,cnt,0);
		cnt++;
	}
	cnt=1;
	memset(visit,0,sizeof(visit));
	for(i=1;i<=N;i++){
		dfs(i,cnt,1);
		cnt++;
	}

	for(i=1;i<=N;i++){
	mp[make_pair(color[i][0],color[i][1])]++;
	}
	for(i=1;i<=N-1;i++){
	cout<<mp[make_pair(color[i][0],color[i][1])]<<" ";
	}
	cout<<mp[make_pair(color[N][0],color[N][1])]<<endl;

	return 0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int kotae=0,a,b,c,x,i,j,k;
  cin>>a>>b>>c>>x;
  for(i=a;i>=0;i--){
    for(j=b;j>=0;j--){
      for(k=c;k>=0;k--){
        if(x-500*i-100*j==50*k){
          kotae++;
        }
      }
    }
  }
  cout<<kotae;
}

Measured memory_bytes: 256
class BinaryTree:
    def __init__(self, left, right, parent):
        self.left = left
        self.right = right
        self.parent = parent
        self.key = None
        self.root = False
        

def insert(T, z):
    global root
    
    y = -1
    try:
        x = root
    except:
        x = -1
        root = z
        T[z].root = True
    
    while x != -1:
        y = x
        if T[z].key < T[x].key:
            x = T[x].left
        else:
            x = T[x].right
    T[z].parent = y
    
    if y == -1:
        pass
    
    elif T[z].key < T[y].key:
        T[y].left = z
        
    else:
        T[y].right = z
    
def preParse(u):
    if u == -1:
        return 0
    print(" " + str(T[u].key), end="")
    preParse(T[u].left)
    preParse(T[u].right)

def inParse(u):
    if u == -1:
        return 0
    inParse(T[u].left)
    print(" " + str(T[u].key), end="")
    inParse(T[u].right)

m = int(input().rstrip())

z = 0
T = []
for _ in range(m):
    T.append(BinaryTree(-1, -1, -1))

for _ in range(m):
    command = input().rstrip()
    if command =="print":
        inParse(root)
        print()
        preParse(root)
        print()
    else:
        T[z].key = int(command.split(" ")[-1])
        insert(T, z)
        z += 1



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


int main() {

    vector<int>  pos(5);
    cin>>pos.at(0)>>pos.at(1)>>pos.at(2)>>pos.at(3)>>pos.at(4);

    int k;
    cin>>k;

    bool flg=true;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(i!=j&&abs(pos.at(i)-pos.at(j))>k){
                flg=false;
                break;
            }
        }
    }

    if(flg)
        cout<<"Yay!"<<endl;
    else
        cout<<":("<<endl;


    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n;
	long tmp, sum = 0;

	scanf("%d", &n);
	int ball[n + 1], count[n + 1];
	for(int i = 1; i <= n; i++){
		count[i] = 0;
	}

	for(int i = 1; i <= n; i++){
		scanf("%d", &ball[i]);
		count[ball[i]] += 1;
	}

	for(int i = 1; i <= n; i++){
		if(count[i] > 1){
			tmp = count[i];
			sum += tmp * (tmp - 1) / 2;
		}
	}

	for(int i = 1; i <= n; i++){
		tmp = sum;
		if(count[ball[i]] > 2){
			tmp -= count[ball[i]] * (count[ball[i]] - 1) / 2;
			tmp += (count[ball[i]] - 1) * (count[ball[i]] - 2) / 2;
		}else if(count[ball[i]] == 2){
			tmp -= 1;
		}
		printf("%ld\n", tmp);
	}
}


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

int main(){
    int N;
    cin >> N;
    long long L[100];
    L[0] = 2;
    L[1] = 1;

    if(N == 0){
        cout << L[0] << endl;
    }

    if(N == 1){
        cout << L[1] << endl;
    }

    for(int i = 2; i <= N; i++){
        L[i] = L[i-1] + L[i-2];
        if(i == N){
            cout << L[i] << endl;
        }
    }

}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=30001;

int n,m;
bool vis[N];
vector<int> vc;

void init() {
	for(int i=1;i<N;i++) {
		if(i*2<N/2) vis[i*2]=1;
		if(i*3<N/2) vis[i*3]=1;
		if(i*5<N/2) vis[i*5]=1;
	}
	for(int i=1;i<N/2;i++) {
		if(vis[i]) {
			vc.push_back(i);
		}
	}
	m=vc.size();
}

int main() {
	init();
	scanf("%d",&n);
	if(n==3) {
		printf("2 3 25\n");
	}
	else {
		for(int i=0;i<n/2;i++) {
			printf("%d %d ",vc[i],N-vc[i]-1);
		}
		if(n&1) {
			printf("15000\n");
		}
	}
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <bits/stdc++.h>

using namespace std;
int K,A,B;

int main() {
  int i;

  cin >> K >> A >> B;

  for (i=1; i*K<=B; i++) {
    if (i*K>=A) {
      printf("OK\n");
      return 0;
    }
  }
  printf("NG\n");

  return 0;
}


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

int n;
vector<long long> a;
vector<vector<long long>> DP;
vector<vector<long long>> sum;
const long long inf = (long long)1e18 + 5;

int main()
{
	cin >> n;
	a.resize(n + 1);
	for (int i = 1; i < n + 1; i++)
		cin >> a[i];

	// I spent a lot of time thinking about how to represent the data after merge
	// the key idea is to never use input array after initialization
	// got the idea of 2D DP from Errichto
	// DP[i][j] can store: 
	// total energy generated by merging from i to j
	// also need sum of elements from i to j (used to calculate energy for future merges
	// i 1 ... n, j 1 ... n
	DP.resize(n + 1); sum.resize(n + 1);
	for (int i = 0; i < n + 1; i++)
	{
		DP[i].resize(n + 1);
		sum[i].resize(n + 1,0);
	}

	for (int i = 1; i < n + 1; i++)
	{
		for (int j = i; j < n + 1; j++)
		{
			sum[i][j] = sum[i][j-1]+a[j];
		}
	}

	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j< n + 1; j++)
		{
			if (j < i)
				continue;
			if (j == i) // update the sum, no energy generated
			{
				DP[i][j] = 0;
			}
			else
			{
				DP[i][j] = inf;
				for (int k = i; k < j; k++)
					DP[i][j] = min(DP[i][j], DP[i][k] + DP[k + 1][j] + sum[i][j]);
			}
		}
	}
	cout << DP[1][n] << endl;
}

Measured memory_bytes: 6108
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <functional>
#include <algorithm>
#include <climits>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)

struct Edge
{
	int to;
	int cost;
};

struct Node
{
	int city_index;
	int total_cost;
	int current_life;

	bool operator >(const Node &a) const
	{
		if (total_cost == a.total_cost)
		{
			return current_life < a.current_life;
		}
		return total_cost > a.total_cost;
	}
};

int main()
{
	int city_count, initial_life, cooler_count, road_count, start_index, goal_index;
	while (cin >> city_count >> initial_life >> cooler_count >> road_count >> start_index >> goal_index,
		city_count)
	{
		// input
		vector<int> is_cooler(city_count, false);
		REP(i, cooler_count)
		{
			int cooler_index;
			cin >> cooler_index;
			is_cooler[cooler_index] = true;
		}
		vector<vector<Edge>> roads(city_count);
		REP(i, road_count)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			roads[from].push_back({ to, cost });
			roads[to].push_back({ from, cost });
		}

		// dijkstra
		vector<vector<int>> d(city_count, vector<int>(initial_life + 1, INT_MAX)); // [city_index][current_life] => total_cost
		d[start_index][initial_life] = 0;
		priority_queue<Node, vector<Node>, greater<Node> > pq;
		pq.push({ start_index, 0, initial_life });
		while (true)
		{
			if (pq.empty())
			{
				cout << "Help!" << endl;
				break;
			}
			auto current_node = pq.top(); pq.pop();
			if (current_node.city_index == goal_index)
			{
				cout << current_node.total_cost << endl;
				break;
			}
			if (is_cooler[current_node.city_index])
			{
				REP(i, initial_life - current_node.current_life + 1)
				{
					int life = current_node.current_life + i;
					int cost = current_node.total_cost + i;
					int city_index = current_node.city_index;
					if (cost < d[city_index][life])
					{
						d[city_index][life] = cost;
						pq.push({ city_index, cost, life });
					}
				}
			}
			
			for (auto &road : roads[current_node.city_index])
			{
				int life = current_node.current_life - road.cost;
				if (life < 0)
				{
					continue;
				}
				int cost = current_node.total_cost + road.cost;
				if (cost < d[road.to][life])
				{
					d[road.to][life] = cost;
					pq.push({ road.to, cost, life });
				}
			}

		}
	}

	return 0;
}

Measured memory_bytes: 1464
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
ll n,T; vector<pair<ll,ll> > vc;
bool comp(const pair<ll,ll>&a,const pair<ll,ll>&b){
	if(a.fs!=b.fs) return a.fs<b.fs;
	else return a.sc>b.sc;
}
ll dp[3001][3001];
ll maxval(ll i,ll time_left){
	if(time_left<=0) return 0;
	if(i==n){
		return 0;
	}
	if(dp[i][time_left]!=-1){
		return dp[i][time_left];
	}

	ll a,b;
	a=maxval(i+1,time_left);
	b=maxval(i+1,time_left-vc[i].fs)+vc[i].sc;
	return dp[i][time_left]=max(a,b);
}
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l;
	cin>>n>>T;
	for(i=1;i<=n;i++){
		cin>>k>>l;
		vc.ps({k,l});
	}
	sort(all(vc),comp);
	memset(dp,-1,sizeof(dp));
	ll an=maxval(0,T);
	cout<<an;
	return 0;
}

Measured memory_bytes: 71040
s=input().strip()
K=int(input().strip())
minst='z'
for i in range(len(s)):
    if s[i]<minst:
        minst=s[i]
stset=[]
for i in range(len(s)):
    for j in range(K):
        if i+j<=len(s)-1:
            stset.append(s[i:i+j+1])
stset.sort()
kst=''
ct=0
for i in range(len(stset)):
    if kst!=stset[i]:
        ct+=1
        kst=stset[i]
    if ct==K:
        break
print(kst)

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

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

int main() {
 int N,M,K;
 cin>>N>>M>>K;
 int sum=0;
 ll ans,j;
 

vector<ll> vecN(N);
vector<ll> vecM(M);
rep(i,N)cin>>vecN[i];
rep(i,M)cin>>vecM[i];
vector<ll> a(1),b(1);

rep(i,N){
    a.push_back(a[i]+vecN[i]);
}

rep(i,M){
    b.push_back(b[i]+vecM[i]);
}

  j=M; 
  ans=0;
 rep(i,N+1){
     if(K<a[i])break;
     while(K<a[i]+b[j]){
       j--;  
     }
     ans=max2val(ans,i+j);
 }
    cout<<ans<<endl;

 }



Measured memory_bytes: 11116
N,K = map(int,raw_input().split())
a = map(int,raw_input().split())
b = []
for i in range(N-K+1):
  k_1 = a[i+K-1]-a[i]+abs(a[i])
  k_2 = a[i+K-1]-a[i]+abs(a[i+K-1])
  if k_1<k_2:
    b.append(k_1)
  else:
    b.append(k_2)
print(min(b))



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

namespace atcoder.abc174.b
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] paramArray = getIntParams();
            int ret = 0;
            for (int i = 0; i < paramArray[0]; i++)
            {
                long[] itemArray = getLongParams();
                if (Math.Pow(paramArray[1], 2) >= Math.Pow(itemArray[0], 2) + Math.Pow(itemArray[1], 2))
                {
                    ret++;
                }
            }
            Console.WriteLine(ret);
        }

        //↓↓↓ shared function ↓↓↓
        static int getIntParam()
        {
            return int.Parse(Console.ReadLine());
        }
        static int[] getIntParams()
        {
            return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        }
        static long getLongParam()
        {
            return long.Parse(Console.ReadLine());
        }
        static long[] getLongParams()
        {
            return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
        }
        static string getStringParam()
        {
            return Console.ReadLine();
        }
        static string[] getStringParams()
        {
            return Console.ReadLine().Split(' ');
        }
    }
}


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

typedef struct{
  int left;
  int right;
  int child;
  int p;
  int s;
  int d;
  int h;
}DATA;

DATA id[25];

int depthsearch(int, int);
int heightsearch(int, int);

int main(){
  int i, j, n, idtemp, l, r, maxd;
  
  scanf("%d", &n);
  if(n >= 1 && n <= 25){
    for(i = 0; i < n; i++) {
      id[i].p = -1;
      id[i].s = -1;
    }
    for(i = 0; i < n; i++){
      scanf("%d", &idtemp);
      scanf("%d %d", &l, &r);
      id[idtemp].child = 0;
      id[idtemp].left = l;
      id[idtemp].right = r;
      if(l != -1 && r != -1){
	id[l].p = idtemp;
	id[r].p = idtemp;
	id[l].s = r;
	id[r].s = l;
	id[idtemp].child = 2;
      }else if(l == -1 && r != -1){
	id[r].p = idtemp;
	id[idtemp].child = 1;
      }else if(r == -1 && l != -1){
	id[l].p = idtemp;
	id[idtemp].child = 1;
      }
    }

    for(i = 0; i < n; i++){
      id[i].d = depthsearch(0, i);
    }

    for(i = 0; i < n; i++){
      printf("node %d: parent = %d, sibling = %d, ", i, id[i].p, id[i].s);
      id[i].h = heightsearch(0, i);
      printf("degree = %d, depth = %d, height = %d, ", id[i].child, id[i].d, id[i].h);
      
      if(id[i].p == -1) printf("root\n");
      else if(id[i].left != -1 || id[i].right != -1) printf("internal node\n");
      else printf("leaf\n");
    }

  }
  return 0;
}

int depthsearch(int d, int ids){
  
  if(id[ids].p == -1) return d;
  
  ids = id[ids].p;
  d = depthsearch(d + 1, ids);
 
  return d;
}

int heightsearch(int h, int ids){
  int h1, h2;
  h1 = h2 = 0;
  if(id[ids].right != -1)
    h1 = heightsearch(h, id[ids].right) + 1;
  if(id[ids].left != -1)
    h2 = heightsearch(h, id[ids].left) + 1;

  if(h1 > h2)return h1;
  return h2;
}



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

class Program
{
  public static void Main(string[] args)
  {
    int n = int.Parse(Console.ReadLine());
    int[,] s = new int[n+1, 3];
    s[0,0] = 0;
    s[0,1] = 0;
    s[0,2] = 0;
    for (int i = 1; i <= n; i ++) {
      int[] t = Console.ReadLine().Split().Select(int.Parse).ToArray();
      s[i,0] = t[0];
      s[i,1] = t[1];
      s[i,2] = t[2];
      int time = s[i,0] - s[i-1,0];
      int x = Math.Max(s[i,1], s[i-1,1]) - Math.Min(s[i,1], s[i-1,1]);
      int y = Math.Max(s[i,2], s[i-1,2]) - Math.Min(s[i,2], s[i-1,2]);
      int length = x + y;
      if (time < length) {
        Console.WriteLine("No");
        break;
      }
      else {
        while(true) {
          if (time == length) break;
          time -= 2;
          if (time < length) {
            Console.WriteLine("No");
            goto end;
          }
        }
      }
      if (i == n) Console.WriteLine("Yes");
    }
    end:;
  }
}


Measured memory_bytes: 16316
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5])
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // get a integer
        int start = sc.nextInt();
        // get two integers separated with half-width break
        int end = sc.nextInt();
        
        int base = 0;

         //special case where the start and end are the same.
        if (start == end) {
            System.out.println(0);
            return;
        }
        
        //special case where the sign is different.
        if (start == -1 * end) {
            System.out.println(1);
            return;
        }
        
        
        base = Math.abs(Math.abs(start) - Math.abs(end));
        
        if (start >= 0)
        {
            if (end >= 0)
            {
                if (start > end)
                {
                    if (end == 0)
                    {
                        base = base + 1;
                    }
                    else
                    {
                          //e.g 7 -> 5   7 -> -7 -> -5 -> 5
                    base = base + 2;
                    }
                  
                }
                else
                {
                    //e.g. 5 -> 7
                    base = base;
                }
                
            }
            else
            {
                //start is above 0, end is less than 0
                 if (Math.abs(start) > Math.abs(end))
                {
                    //e.g 5 -> -2   5 -> -5 ->  -2
                    base = base + 1;
                }
                else
                {
                    //e.g. 5 -> -7  5 -> 7 -> -7
                    base = base +1;
                }
            }
            
        }
        else //start less than 0
        {
            if (end > 0)
            {
                if (Math.abs(start) > Math.abs(end))
                {
                    //e.g -7 -> 5   -7 -> -5 -> 5
                    base = base + 1;
                }
                else
                {
                    //e.g. -7 -> 9   -7 -> +7 -> 9
                    base = base + 1;
                }
            }
            else
            {
                if (Math.abs(start) > Math.abs(end))
                {
                    //e.g -7 -> -5   
                    base = base;
                }
                else
                {
                    //e.g. -7 -> -9  
                    base = base + 2;
                }
            }
        }

        // outputxx
        System.out.println(base);
    }
}


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

#define ll long long
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n, m) for (int (i) = (n); (i) < (m); (i)++)
#define debug(x) cerr << #x << ": " << x << endl;
#define line() cerr << "---------------" << endl;

int N, K;
int sumB[1111][1111]; // 黒の累積和？
int sumW[1111][1111]; // 白の累積和？

int main() {
   cin >> N >> K;
   rep (i, 0, N) {
      int x, y;
      char c;
      cin >> x >> y >> c;

      int tmp = x/K + y/K;
      x %= K, y%= K;
      if (tmp&1) {
         if (c=='B') {
            c='W';
         } else {
            c = 'B';
         }
      }
      if (c=='B') {
         sumB[y+1][x+1]++;
      } else {
         sumW[y+1][x+1]++;
      }
   }

   // 累積和を取る
   rep (i, 0, K) {
      rep (j, 0, K) {
         sumB[i+1][j+1]+=sumB[i][j+1]+sumB[i+1][j]-sumB[i][j];
         sumW[i+1][j+1]+=sumW[i][j+1]+sumW[i+1][j]-sumW[i][j];
      }
   }

   int ans = 0;
   rep (i, 0, K+1) {
      rep (j, 0, K+1) {
         int tmp = 0;
         tmp += sumB[i][j];
         tmp += sumB[K][K]-sumB[i][K]-sumB[K][j]+sumB[i][j];
         tmp += sumW[K][j]-sumW[i][j];
         tmp += sumW[i][K]-sumW[i][j];
         ans = max(ans, tmp);
         ans = max(ans, N-tmp);
      }
   }
   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 1e5 +5;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

int main(){
  fio();
  double r; cin>>r;
  cout<<fixed;
  cout<<setprecision(10);
  cout<<(2*M_PI*r)<<endl;
  return 0;
}


Measured memory_bytes: 3804
-- ABC 137 B
import Data.Maybe
import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  [k, x] <- getIntList
  let as = unwords . map show . take (2*k-1) $ [x-k+1..]
  putStrLn as

readInt :: BS.ByteString -> Int
readInt = fst . fromJust . BS.readInt

getInt :: IO Int
getInt = readInt <$> BS.getLine

getIntList :: IO [Int]
getIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

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

using namespace std;

int memo[3005][3005];   /// ... for storing DP values ...

string a,b; /// ... Two Strings ...

int call(int len1,int len2){
    /// if two string come to the end then there are no substring can create ... so we return Zero.
    if(len1 == (int)a.size() || len2 == (int)b.size()) return 0;
    /// ... if the value is saved before then return it ...
    if(memo[len1][len2] != -1) return memo[len1][len2];
    /// ... if two charecture is matched ... then the length is increased by one and we go to the next phase
    /// (i + 1, j + 1) ...
    if(a[len1] == b[len2]){
        return memo[len1][len2] = 1 + call(len1 + 1, len2 + 1);
    }
    /**
        if not then we go to either by removing charecture of first or form second.
        then we collect the maximun the two function returns and saves it.
    **/
    else return memo[len1][len2] = max(call(len1 + 1,len2),call(len1, len2 + 1));
}

/// ... printing LCS ...
vector <char> res;
void PrintLCS(int len1, int len2){
    if(len1 == (int)a.size() || len2 == (int)b.size()) return;
    if(a[len1] == b[len2]){
        cout << a[len1];
        PrintLCS(len1 + 1,len2 + 1);
    }
    else{
        if(memo[len1 + 1][len2] > memo[len1][len2 + 1]) PrintLCS(len1 + 1,len2);
        else PrintLCS(len1,len2 + 1);
    }
}

int main(){
    memset(memo, -1, sizeof(memo));
    cin >> a >> b;
    call(0,0);
    PrintLCS(0,0);
}


Measured memory_bytes: 35840
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
typedef long long ll;
using namespace std;

int A, B, Dy[3010], ans = 0;
pair<int, int> D[3010];

int main()
{
	int N, T; scanf("%d%d", &N, &T);
	for (int i = 0; i < N; i++)
		scanf("%d%d", &D[i].first, &D[i].second);
	sort(D, D + N);
	for (int i = 0; i < N; i++) {
		A = D[i].first; 
		B = D[i].second;
		for (int j = T - 1; j >= 0; j--) {
			if (ans < Dy[j] + B) ans = Dy[j] + B;
			if (j + A >= T) continue;
			if (Dy[j + A] < Dy[j] + B)Dy[j + A] = Dy[j] + B;
		}
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 128
import sys
s=input()
a=["R","U","D"]
b=["L","U","D"]
for i in range(len(s)):
    if i%2==0:
        if s[i] not in a:
            print("No")
            sys.exit()
    else:
        if s[i] not in b:
            print("No")
            sys.exit()
print("Yes")

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

int main(){
    int A,B,C;
    cin >> A >> B;
    if((A == 1 && B == 2) || (A == 2 && B == 1)){
        cout << "3" << "\n";
    }else if ((A == 2 && B ==3) || (A == 3 && B ==2)){
        cout << "1" << "\n";
    }else{
        cout << "2" << "\n";
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        
        long c = n / (a+b);
        long d = n % (a+b);
        long e = Math.min(a, d);
        System.out.println(c * a + e);
    }
}


Measured memory_bytes: 35808
#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int n, m;
    char rus[51][51];
    int nw[51] = {0}, nb[51] = {0}, nr[51] = {0};
    int ans[1000001] = {0};
    int sub = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> rus[i];
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            if (rus[i][k] != 'W') {
                nw[i]++;
            }
            if (rus[i][k] != 'B') {
                nb[i]++;
            }
            if (rus[i][k] != 'R') {
                nr[i]++;
            }
        }
    }

    for (int x = 1; x < n; x++) {
        for (int y = 1; y < n; y++) {
            if (n-x-y > 0) {
                for (int i = 0; i < x; i++) {
                    ans[sub] += nw[i];
                }
                for (int i = x; i < y + x; i++) {
                    ans[sub] += nb[i];
                }
                for (int i = x + y; i < n; i++) {
                    ans[sub] += nr[i];
                }
                sub++;
            }
        }
    }

    sort(ans, ans + sub);

    cout << ans[0] << endl;

}



Measured memory_bytes: 7068
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

import math

def C(d):
    sum = 0
    for i in range(n):
        sum += math.ceil(max(h[i] - b * d, 0) / (a - b))
    return sum <= d

lb = -1
ub = 10 ** 9 + 1
while (ub - lb) > 1:
    mid = (lb + ub) // 2
    if C(mid):
        ub = mid
    else:
        lb = mid
print(ub)


Measured memory_bytes: 7072
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define pb(a) push_back(a)
#define pr(a) cout<<(a)<<endl
#define PR(a,b) cout<<(a)<<" "<<(b)<<endl
#define F first
#define S second
#define ll long long
bool check(int n,int m,int x,int y){return (x<0||x>=n||y<0||y>=m)?false:true;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
typedef pair<int,int> P;

#define MAX_V 100001
struct edge{ int to,cap,rev; };  
int V,E;
vector<edge> G[MAX_V];
int level[MAX_V],iter[MAX_V];
  
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}
  
void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> Q;
  level[s] = 0;
  Q.push(s);
  while(!Q.empty()){
    int v = Q.front(); Q.pop();
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
        level[e.to] = level[v] + 1;
        Q.push(e.to);
      }
    }
  }
}
  
int dfs(int v,int t,int f){
  if(v == t) return f;
  for(int &i = iter[v] ; i < (int)G[v].size() ; i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    bfs(s);
    if(level[t] < 0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f = dfs(s,t,MAX)) > 0){
      flow += f;
    }
  }
}

int main() {
  int n,m;
  while(cin >> n >> m && (n||m)) {
    rep(i,MAX_V) G[i].clear();
    int a[n],b[m];
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    rep(i,n) {
      rep(j,m) {
	if(__gcd(a[i],b[j])!=1) add_edge(i+1,j+n+1,1);
      }
    }
    rep(i,n) add_edge(0,i+1,1);
    rep(i,m) add_edge(n+1+i,n+m+1,1);
    pr(max_flow(0,n+m+1));
  }
  return 0;
}


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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

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

// -------------------------------------------------------------------
// sort 1 2 3 4

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vec a(n);
    init(a);

    int neg = 0;
    int mi = INF * 2;
    int idx = -1;
    rep (i, n) {
        if (a[i] < 0) neg++;
        if (abs(a[i]) < mi) {
            mi = min(mi, abs(a[i]));
            idx = i;
        }
    }

    int sum = 0;
    if (neg % 2 == 0) {
        repall (i, a)
            sum += abs(i);
        print(sum);
        return 0;
    }
    rep (i, n) {
        if (i != idx)
            sum += abs(a[i]);
        else
            sum -= abs(a[i]);
    }
    print(sum);

    return 0;
}


Measured memory_bytes: 1024
#include"bits/stdc++.h"
using namespace std;
int main(){
	string s;
	cin>>s;
	bool ch=true;
	if(s[0]!='A')
		ch=false;
	int cnt=0;
	for(int i=2;i!=s.size()-1;++i){
		if(s[i]=='C')
			++cnt;
		else if(isupper(s[i]))
			ch=false;
	}
	if(isupper(s[1]) || isupper(s.back()))
		ch=false;
	if(cnt!=1)
		ch=false;
	cout<<(ch ? "AC":"WA");
}




Measured memory_bytes: 256
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define all(v) v.begin(),v.end()
#define pb push_back
#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;
typedef pair<ll,ll> pll;

int main(){
	ll d,g;
	cin>>d>>g;
	pll pro[d];
	vector<pll> ans;
	rep(i,d)cin>>pro[i].first>>pro[i].second;
	for(int i=0;i<(1<<d);i++){
		pll tmp=pll(0,0);
		rep(j,d){
			if(i&(1<<j)){
				tmp.first+=pro[j].first;
				tmp.second+=100*(j+1)*pro[j].first+pro[j].second;
			}
		}
		for(int j=d-1;j>=0;j--){
			if(!(i&(1<<j))){
				int num=0;
				while(num<pro[j].first&&tmp.second<g){
					num++;
					tmp.first++;
					tmp.second+=100*(j+1);
				}
			}
		}
		ans.pb(tmp);
	}
	sort(all(ans));
	cout<<ans[0].first<<endl;
	return 0;
}

Measured memory_bytes: 256
h,w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))

hw = [['0' for i in range(w)] for j in range(h) ]

index = 0
for i in range(h):
  for j in range(w):
    if i % 2 == 0:
      hw[i][j] = str(index+1)
        
    else:
      hw[i][w-j-1] = str(index+1)
      
    a[index] -= 1
    if a[index] == 0:
      index += 1
        
for i in range(h):
  print(' '.join(hw[i]))

Measured memory_bytes: 3700
a, b, k = map(int, input().split())
for i in range(1, k+1):
    # 高橋君の番
    if i % 2 == 1:
        if a % 2 == 1:
            a -= 1
        a, b = a//2, b+a//2
    # 青木君の番
    else:
        if b % 2 == 1:
            b -= 1
        a, b = a+b//2, b//2
print(a, b)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string s;
    cin>>s;
    bool ans[3];
    for(int i=0;i<3;i++)ans[i]=false;
    for(int i=0;i<3;i++)ans[s[i]-'a']=true;
    for(int i=0;i<3;i++){
        if(!ans[i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
a.sort(key=lambda x:x[1])
for i in range(1,len(a)):
    a[i][0]+=a[i-1][0]
for i in a:
    if i[0]>i[1]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 88792