akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}

namespace MCF {
	// required <string.h> <vector> <queue> <algorithm>
	#define MAXN 2500
	#define MAXM 30000
	#define wint int
	#define cint long long
	const wint wEPS = 0;
	const wint wINF = 1001001001;
	const cint cEPS = 0;
	const cint cINF = inf;
	int n, m, ptr[MAXN], Next[MAXM], zu[MAXM];
	wint capa[MAXM], tof;
	cint cost[MAXM], toc, d[MAXN], pot[MAXN];
	int vis[MAXN], pree[MAXN];
	void init(int _n) {
		n = _n; m = 0; memset(ptr, ~0, n * 4);
	}
	void ae(int u, int v, wint w, cint c) {
		Next[m] = ptr[u]; ptr[u] = m; zu[m] = v; capa[m] = w; cost[m] = +c; ++m;
		Next[m] = ptr[v]; ptr[v] = m; zu[m] = u; capa[m] = 0; cost[m] = -c; ++m;
	}
	bool solve(int src, int ink, wint flo = wINF) {
		int i, u, v;
		wint f;
		cint c, cc;
		memset(pot, 0, n * sizeof(cint));
		//*
		for (bool cont = 1; cont; ) {
			cont = 0;
			for (u = 0; u < n; ++u) for (i = ptr[u]; ~i; i = Next[i]) if (capa[i] > wEPS) {
				if (pot[zu[i]] > pot[u] + cost[i] + cEPS) {
					pot[zu[i]] = pot[u] + cost[i]; cont = 1;
				}
			}
		}
		//*/
		for (toc = 0, tof = 0; tof + wEPS < flo; ) {
			typedef pair<cint,int> node;
			priority_queue< node,vector<node>,greater<node> > q;
			for (u = 0; u < n; ++u) { d[u] = cINF; vis[u] = 0; }
			for (q.push(make_pair(d[src] = 0, src)); !q.empty(); ) {
				c = q.top().first; u = q.top().second; q.pop();
				if (vis[u]++) continue;
				for (i = ptr[u]; ~i; i = Next[i]) if (capa[i] > wEPS) {
					cc = c + cost[i] + pot[u] - pot[v = zu[i]];
					if (d[v] > cc + cEPS) { q.push(make_pair(d[v] = cc, v)); pree[v] = i; }
				}
			}
			if (!vis[ink]) return 0;
			f = flo - tof;
			for (v = ink; v != src; v = zu[i ^ 1]) { i = pree[v]; f=min(f,capa[i]); }
			for (v = ink; v != src; v = zu[i ^ 1]) { i = pree[v]; capa[i] -= f; capa[i ^ 1] += f; }
			tof += f;
			toc += f * (d[ink] - pot[src] + pot[ink]);
			for (u = 0; u < n; ++u) pot[u] += d[u];
		}
		return 1;
	}
}

int main(){
	int a;scanf("%d",&a);
	MCF::init(2500);
	int S=2*a+4;
	int T=2*a+5;
	int s=0;
	for(int i=0;i<a;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);s+=z;
		MCF::ae(S,i,z,0LL);
		MCF::ae(i,2*a,z,x+y);
		MCF::ae(i,2*a+1,z,-x+y);
		MCF::ae(i,2*a+2,z,x-y);
		MCF::ae(i,2*a+3,z,-x-y);
	}
	for(int i=0;i<a;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		MCF::ae(a+i,T,z,0LL);
		MCF::ae(2*a+3,a+i,z,x+y);
		MCF::ae(2*a+2,a+i,z,-x+y);
		MCF::ae(2*a+1,a+i,z,x-y);
		MCF::ae(2*a,a+i,z,-x-y);
	}
	MCF::solve(S,T,s);
	printf("%lld\n",-MCF::toc);
}

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

int main() {
    string S;
    cin >> S;
    int max_length = 0;
    int part_length = 0;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') {
            part_length++;
        } else {
            max_length = max(max_length, part_length);
            part_length = 0;
        }
    }
    max_length = max(max_length, part_length);
    cout << max_length << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int people = scan.nextInt();
		int day = scan.nextInt();
		int remainder = scan.nextInt();
		
		int[] eatDay = new int[people];
		
		int sum = people;
		for (int i = 0; i < people; i++) {
			eatDay[i] = scan.nextInt();
			int count = 0;
			for (int j = 1;; j++) {
				count = j * eatDay[i] + 1;
				if (count <= day) {
					sum++;
				} else {
					break;
				}
			}
		}
		
		System.out.println(sum + remainder);
		
	}
}


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

int gcd(int x,int y){
  if(y==0){
    return x;
  }

  return gcd(y,x%y);
}

int main(){
  int x,y;
  cin >> x >> y;

  int ans=x+y+1-gcd(x,y);
  cout << ans << endl;
}



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

int count(long long int *num){
  int a=0;
  while(1)
    if((*num) % 10 == 0){
      a++;
      *num /= 10;
    }
    else 
      return a;
}

int main(){
  long long int n;
  
  while(cin >> n){
    if(n==0)
      break;
    
    long long int a, b, ans;
    for(a=1,ans=0;n>1;n--){
      a *= n;
      for(;a%10==0;a/=10)
	ans++;
      if((b=a/100000) != 0)
	a -= b*100000;
    }
    
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
long long int f(long long int x,int r,int D){
  return x*r-D;
}
int main(){
  int x,r,D;
  cin>>r>>D>>x;
  for(int i=0;i<10;i++){
    x=f(x,r,D);
    cout<<x<<endl;
  }
}

Measured memory_bytes: 256
// G++ MACRO.CPP -STD=C++17
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
template <class T = ll>
T IN(){T x;cin>>x;return (x);}
 
template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
  VECCIN(head);
  VT2(move(tail)...);
}
 
template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
  seco[head]=IN();
  VT3(head,move(tail)...);
}
 
#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc
 
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision; // cpp_int
 
#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>
 
#define pb(a) push_back(a)
#define mp make_pair
 
int main(){
  CIN(n);
  ll val = 1;
  FOR(i,1,n+1){
    val*=i;val%=MOD;
  }
  COUT(val);

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir [] = {
	{ 1,0 },{ 0,1 }
};



signed main() {
	char s[10000];
	
	
	scnaf("%*s%s%*s", s);
	printf("A%cC\n", s[0]);


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define xrep(i,x,n) for(ll i = (ll) x; i < (ll) n; i++)
#define vl vector<long long>
#define vs vector<string>
#define SORT(A) sort(A.begin(), A.end())

int main() {
    ll x;
    cin >> x;

    cout << x / 500 * 1000 + x % 500 / 5 * 5 << endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void){
  ll n,x,m; cin>>n>>x>>m; --n;
  vector<bool> c(m,false);
  ll res=x;
  while(n-->0){
    x=x*x%m;
    if(c[x]==false) res+=x,c[x]=true;
    else{
      ll cnt=0,cnt2=0;
      vector<bool> d(m,false);
      while(d[x]==false){
        cnt+=x;
        d[x]=true;
        x=x*x%m;
        ++cnt2;
      }
      res+=cnt*(n/cnt2);
      n-=n/cnt2*cnt2;
      while(n-->=0) res+=x,x=x*x%m;
    }
  }
  cout<<res;
  return 0;
}


Measured memory_bytes: 3644
//ALDS 1_9_C
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main(){
	
	priority_queue<int> S;
	string cmd;
	int key;

	while(1){
		cin>>cmd;

		if(cmd == "insert"){
			cin>>key;
			S.push(key);
		}

		if(cmd == "extract"){
			cout<<S.top()<<endl;
			S.pop();
		}

		if(cmd == "end")
			break;
	}

	return 0;
}

Measured memory_bytes: 6508
#include <bits/stdc++.h>
using namespace std;
#define rep for(int i = 0;i<n;i++)
#define ll long long
 
//const int INF = 1e8;
typedef pair<int,int>P;
int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};
queue<P> que;

int main(){
    int n;cin >> n;
    int a[n+2];a[0] = 0;a[n+1] = 0;
    ll sum = 0;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        sum += abs(a[i]-a[i-1]);
    }
    sum += abs(a[n+1]-a[n]);
    //cout << sum << endl;
    for(int i = 1;i<=n;i++){
        cout << sum - abs(a[i+1]-a[i])-abs(a[i]-a[i-1]) + abs(a[i+1]-a[i-1]) << endl;
    }
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Main mainObj = new Main();
		mainObj.solve();
	}
	
	public void solve() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		int nowVal = 1;
		int ans = 0;
		
		for(int i = 0; i < n; i++) {
			if(arr[i] == nowVal) {
				nowVal++;
			}else {
				ans++;
			}
		}
		
		if(ans == n) {
			System.out.println(-1);
		}else {
			System.out.println(ans);
		}
	}

}


Measured memory_bytes: 85236
s = list(input())
n = len(s)
ans = "Yes"
for i in range(n//2):
    if s[i] != s[-i-1]:
        ans = "No"
for i in range((n-1)//4):
    if s[i] != s[(n-1)//2-1-i]:
        ans = "No"
    if s[i+(n+3)//2-1] != s[n-1-i]:
        ans = "No"
print(ans)

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys


def solve(S: str):
    def is_valid(s):
        for c in s:
            if not c in 'AGTC':
                return False
        return True
    n = len(S)
    ret = ''
    for i in range(n):
        for j in range(i, n):
            if is_valid(S[i:j + 1]) and j - i + 1 > len(ret):
                ret = S[i:j + 1]
    print(len(ret))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

int main() {
    string S; cin >> S;
    int p = 0, m = 0;
    for(int i = 0; i < 4; i++) {
        if(S[i] == '+') {
            p++;
        } else {
            m++;
        }
    }
    cout << p - m << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define inf 0x3f3f3f3f
#define endl "\n"
#define MP(x,y) (make_pair(x,y))
#define pll pair<int,int>
#define pi 3.1415926535
using namespace std;
int main(){
    int n;
    cin>>n;
    ll sum = 0;
    for(int i=1;i<=n;i++){
        if(i%3 && i%5) sum+=i;//,cout<<i<<endl;
    }
    cout<<sum<<endl;
    return 0;
}


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

using namespace std;

int main(void)
{
    int N, M, X=0;

    cin >> N;
    string s[N];
    for(int i=0; i<N; i++){
        cin >> s[i];
    }
    cin >> M;
    string t[M];
    for(int i=0; i<M; i++){
        cin >> t[i];
    }

    for(int i=0; i<N; i++){
        int cntn=0;
        for(int j=0; j<N; j++){
            if(s[i] == s[j]){
                cntn++;
            }
        }
        for(int j=0; j<M; j++){
            if(s[i] == t[j]){
                cntn--;              
            }
        }
        if(cntn > 0 && cntn > X){
            X = cntn;
        }
    }
    
    for(int i=0; i<M; i++){
        int cntt=0;
        for(int j=0; j<N; j++){
            if(t[i] == s[j]){
                cntt++;
            }
        }
        for(int j=0; j<M; j++){
            if(t[i] == t[j]){
                cntt--;
            }
        }
        if(cntt > 0 && cntt > X){
            X = cntt;
        }
    }

    cout << X << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

int h,w,x;
char s[1000][1000];
bool visited [1000][1000];
pair<int,int> start,goal;
queue<pair<int,pair<int,int>>> q;
vector<pair<int,int>> ino;

int main(){
  int a,b,c;cin>>a>>b>>c;
  bool same = false;
  if(a==b&&a==2)same = true;
  if((a==1||a==3||a==5||a==7||a==8||a==10||a==12)&&(b==1||b==3||b==5||b==7||b==8||b==10||b==12))same = true;
  if((a==4||a==6||a==9||a==11)&&(b==4||b==6||b==9||b==11))same = true;
  cout << (same?"Yes":"No");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
	char c = getchar();
	bool f = false;
	for (x = 0; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = true;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	if (f) {
		x = -x;
	}
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
	read(x), read(y...);
}
const int N=3e3+10;
int n,p;
int head[N],A[N];
struct Edge {
  int to,last;
  Edge () {}
  Edge (int a,int b) :to(a),last(b) {}
}edge[N<<1];
void ADD(int a,int b) {
  edge[++p]=Edge(b,head[a]); head[a]=p;
  edge[++p]=Edge(a,head[b]); head[b]=p;
}
bool DFS(int u,int f) {
  for(int i=head[u];i;i=edge[i].last) {
    int v=edge[i].to;
    if(v!=f&&A[u]>A[v]) {
      if(!DFS(v,u)) return true;
    }
  }
  return false;
}
//#define rua
int main() {
//	ios::sync_with_stdio(false);
#ifdef rua
	freopen("GG.in","r",stdin);
#endif
  read(n);
  for(int i=1;i<=n;++i) read(A[i]);
  for(int i=1;i<n;++i) {
    int u,v; read(u,v);
    ADD(u,v);
  }
  for(int i=1;i<=n;++i) {
    if(DFS(i,0)) printf("%d ",i);
  }
  return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int N; cin >> N;
  vector<int> a(N); cin >> a;
  int max = *max_element(all(a));
  int min_diff = inf;
  int min_idx = -1;
  rep(i, a.size()) {
    if(a[i] != max && minimize(min_diff, abs(max/2 - a[i]))) {
      min_idx = i;
    }
  }
  cout << max << " " << a[min_idx] << "\n";
}


Measured memory_bytes: 640
D, G = map(int, input().split())
ps, cs = [], []
for _ in range(D):
    p, c = map(int, input().split())
    ps.append(p)
    cs.append(c)

min_count = float("inf")
for ptn in range(2**D):
    completed = []
    for i in range(D):
        if (ptn >> i) & 1 == 1:
            completed.append(i)

    score = 0
    count = 0
    for i in completed:
        score += 100*(i+1)*ps[i] + cs[i]
        count += ps[i]
    if score < G:
        selected_prob = max([i for i in range(D)
                             if i not in completed])
        if (selected_prob+1)*100*(ps[selected_prob]-1) < G - score:
            continue
        if (G-score) % ((selected_prob+1)*100) == 0:
            count += (G-score)//((selected_prob+1)*100)
        else:
            count += (G-score)//((selected_prob+1)*100)+1

    if count < min_count:
        min_count = count
print(min_count)


Measured memory_bytes: 43356
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    double T = cin.nextDouble();
    double X = cin.nextDouble();

    double res = T/X;

    System.out.println(res);

  }

}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<vector<int>> dp(2,vector<int>(n,0));
    vector<vector<int>> v(2,vector<int>(n));
    rep(i,2){
        rep(j,n) cin >> v[i][j];
    }

    dp[0][0] = v[0][0];

    rep(i,2){
        rep(j,n){
            if(i==0 && j==0) continue;
            else if(i==0) dp[i][j] = dp[i][j-1] + v[i][j];
            else if(i==1 && j==0) dp[i][j] = dp[i][j] = dp[i-1][j] + v[i][j];
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1] ) + v[i][j];
        }        
    }

    cout << dp[1][n-1] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) (int)v.size()
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; 
#define prl cerr<<"called: "<< __LINE__<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}


int32_t main(){
  fastio;
  string s,t;
  cin >> s >>t;
  int res = 1e9;
  for(int i=0;i+sz(t)-1<sz(s);i++){
    int cur=0;
    for(int j = 0;j<sz(t);j++){
      if(t[j]!=s[i + j])cur++;
    }
    res = min(res,cur);
  }
  cout << res << endl;
  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 100100;
 
struct dsu {
    vector<int> p;
    int n;
 
     dsu(int _n) : n(_n) {
        p.resize(n);
        int num=0;
        for (int i=0;i<n;i++) p[i]=num++;
     }
 
    int get(int x) {
        return (x==p[x] ? x : (p[x] = get(p[x])));
    }
 
    bool unite(int x,int y) {
        //cout<<x<<" "<<y<<" "<<get(x)<<" "<<get(y)<<endl;
        x = get(x);
        y = get(y);
        if (x!=y) {
            p[x]=y;
            return true;
        }
        return false;
    }
};
 
int a[maxn],n,m;
long long res;
vector<int> all[maxn];
vector<int> min2;
 
int main() {
 //   freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>a[i];
    dsu T(n);
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        T.unite(x,y);
    }
    for (int i=0;i<n;i++) {
        all[T.get(i)].push_back(a[i]);
       // cout<<i<<" "<<T.get(i)<<endl;
    }
    int cnt=0;
    for (int i=0;i<n;i++) cnt+=(!all[i].empty());
    if (cnt<=1) {
        cout<<0;
        return 0;
    }
   // cout<<cnt;
    for (int i=0;i<n;i++)
        if (!all[i].empty()) {
            sort(all[i].begin(), all[i].end());
            res+=all[i][0];
           // cout<<all[i][0]<<endl;
            for (int j=1;j<all[i].size();j++) min2.push_back(all[i][j]);
        }
    if (min2.size() < cnt-2) {
        cout<<"Impossible";
        return 0;
    }
    sort(min2.begin(),min2.end());
    for (int i=0;i<cnt-2;i++) res+=min2[i];
    cout<<res;
}

Measured memory_bytes: 6528
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)
#define fcout cout << fixed << setprecision(10)

using namespace std;

int A, B;

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

    cin >> A >> B;
    if (A + B == 15) {
        cout << "+" << endl;

    } else if (A * B == 15) {
        cout << "*" << endl;

    } else {
        cout << "x" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reve(a) reverse(a.begin(), a.end())
typedef long long ll;
const ll MOD = 1e9+7;

/*ll gcd(ll a, ll b){
  if(b==0) return a;
  return gcd(b, a%b);
}*/
/*ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}*/

/*ll lcm(ll a, ll b){
  ll g = gcd(a, b);
  b /= g;
  a *= b;
  return a;
}*/

/*int dfs(vector<int> &T, vector<int> &C, int i, int sum, int g, int count){
   
}*/

int main(){
  int n, a; cin >> n;
  vector<int> A(n);
  set<int> B; int ch = 0;
  if(n%3!=0){
    rep(i, n){
      cin >> A[i];
      if(A[i]!=0){
        cout << "No" << endl;
        ch = 1;
        break;
      }
    }
    if(ch==0) cout << "Yes" << endl;
  }
  else{
  rep(i,n) {cin >> A[i]; B.insert(A[i]);}
  Sort(A);
  if(B.size()>3) cout << "No" << endl;
  else if(B.size()==1){
    bitset<32> d(A[0]);
    if((d^d^d)==0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  else if(B.size()==3){
    int m1=A[n/3-1], m2=A[n/3], m3=A[n*2/3-1], m4=A[n*2/3];
    if(m1!=m2&&m3!=m4){
      bitset<32> d(m1);
      bitset<32> e(m2);
      bitset<32> f(m4);
      bitset<32> g(0);
      //bitset<32> h = d^e;
      if((d^e^f)==g) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    else cout << "No" << endl;
  }
  else {
    int m1=A[n/3-1], m2=A[n/3], m3=A[n*2/3-1], m4=A[n*2/3];
    if(m3!=m4){
      bitset<32> d(m3);
      bitset<32> e(m4);
      //bitset<32> f(m3);
      bitset<32> g(0);
      //bitset<32> h = d^e;
      if((d^e^d)==g) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    else if(m1!=m2){
      bitset<32> d(m1);
      bitset<32> e(m2);
      //bitset<32> f(m3);
      bitset<32> g(0);
      //bitset<32> h = d^e;
      if((d^e^e)==g) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    else cout << "No" << endl;
  }  
  }
}

Measured memory_bytes: 4224
#include <iostream>

using namespace std;

bool IsPrimer(int num)
{
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    
    return true;
}

int main()
{
    int num_cnt = 0;
    int tmp = 0;
    int result = 0;
    
    cin >> num_cnt;
    for (int i = 0; i < num_cnt; i++)
    {
        cin >> tmp;
        if (true == IsPrimer(tmp))
        {
            result++;
        }
    }
    
    cout << result << endl;
    
    return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};

int w,h,ans=0;
bool c[55][55];

void bfs(int y,int x)
{
    c[y][x]=0;
    REP(i,8) 
    {
        int ny=y+dy[i];int nx=x+dx[i];
        if(c[ny][nx]&&ny>=0&&ny<h&&nx>=0&&nx<w)bfs(ny,nx);
    }
}

int main()
{

    while(cin>>w>>h,w>0)
    {
        REP(i,h)REP(j,w)cin>>c[i][j];
        ans=0;c[55][55]={};
        REP(i,h)REP(j,w)if(c[i][j]){bfs(i,j);ans++;}
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 3164
#include<stdio.h>
 int linersearch(int*,int,int);
 #define N 10000
 int main() {
   int i,n,m,key,A[N+1],c=0;
   scanf("%d",&n);
   for (i = 0; i < n; i++){
     scanf("%d",&A[i]);
   }
   scanf("%d",&m);
   for (i = 0; i < m; i++) {
     scanf("%d",&key);
     if(linersearch(A,key,n)){
       c++;
     }
   }
   printf("%d\n",c);
   return 0;
 }
 int linersearch(int *a,int k,int x){
   int j=0;
   a[x]=k;
   while(a[j] != k){
     j++;
   }
   return j != x;
 }

Measured memory_bytes: 636
n,k=map(int,input().split())
def expe(n):
  return (n+1)/2
p=[expe(int(x)) for x in input().split()]
l,r=[p[0]]*(n+1),[p[n-1]]*(n+1)
for i in range(n-1):
  l[i+1]=l[i]+p[i+1]
  r[n-2-i]=r[n-1-i]+p[n-2-i]
r[n],l[n]=0,sum(p)
su=sum(p)
ans=max(su-r[k],su-l[n-k-1])
for i in range(1,n-k-1):
  sumk=su-l[i-1]-r[i+k]
  ans=max(sumk,ans)
print(ans)
  


Measured memory_bytes: 23876
n=int(input())
s=[input() for _ in range(n)]
a=[]
b=[]
ab=[]
c=[]
for t in s:
    if t[0]=="B" and t[-1]=="A":
        ab.append(t)
    elif t[-1]=="A":
        a.append(t)
    elif t[0]=="B":
        b.append(t)
    else:
        c.append(t)
        
res=[]
ta,tb=0,0
if len(a)>0:
    res.append(a[ta])
    ta+=1
for t in ab:
    res.append(t)
if len(b)>0:
    res.append(b[tb])
    tb+=1

while(len(a)>ta and len(b)>tb):
    res.append(a[ta])
    res.append(b[tb])
    ta+=1
    tb+=1
for i in range(ta,len(a)):
    res.append(a[i])
for i in range(tb,len(b)):
    res.append(b[i])

for t in c:
    res.append(t)
ans="".join(res)
j= ans[0]=="A"
count=0
for i in range(1,len(ans)):
    if j:
        if ans[i]=="A":
            j=True
        elif ans[i]=="B":
            j=False
            count+=1
        else:
            j=False
    else:
        if ans[i]=="A":
            j=True
        else:
            j=False
print(count)

Measured memory_bytes: 46424
#include<bits/stdc++.h>
using namespace std;
int N, M;
int A[10];
int dp[100001];

bool Check(int k)
{
  fill_n(dp, 100001, -1);
  dp[0] = 0;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j <= M; j++) {
      if(dp[j] >= 0) {
        dp[j] = k;
      } else if(j < A[i] || dp[j - A[i]] <= 0) {
        dp[j] = -1;
      } else {
        dp[j] = dp[j - A[i]] - 1;
      }
    }
  }
  return(dp[M] >= 0);
}


int main()
{
  while(cin >> N >> M, N) {
    for(int i = 0; i < N; i++) {
      cin >> A[i];
    }
    sort(A, A + N, greater< int >());
    int low = 0, high = M;
    while(high - low > 0) {
      int mid = (low + high) >> 1;
      if(Check(mid)) high = mid;
      else low = mid + 1;
    }
    cout << low << endl;
  }
}

Measured memory_bytes: 1568
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

    int ans = 0;
    string s = to_string(N);
    while (N / 10 > 0)
    {
        ans += N % 10;
        N /= 10;
    }
    ans += N;

    if (ans == 1)
    {
        cout << 10 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1000000000;

int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int length = 0;
    length += (h2*60) + (m2) - (h1*60) - (m1) - k;

    cout << length  << endl;

}

Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main(){
    int N,i=1;
    long long A,M=1;
    cin >> N;
    while(cin >> A){
        if(A==0){
            M=0;
            break;
        }else if(A<=1000000000000000000/M && M>0)M=M*A;
        else M=-1;
        i++;
        if(i>N) break;   
    }
        cout << M << endl;
    return 0;
}

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

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

  long long n = s.size();
  vector<long long> c(30, 0);
  for (int i = 0; i < n; ++i) {
    c[s[i] - 'a']++;
  }

  long long ans = n * (n + 1) / 2 + 1;
  for (int i = 0; i < c.size(); ++i) {
    ans -= c[i] * (c[i] + 1) / 2;
  }

  cout << ans << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;

	int mul_k = 0;
	for (int i = 1; i <= n; ++i) {
		if (i % k == 0) {
			++mul_k;
		}
	}

	long long ans = (long long) mul_k * mul_k * mul_k;
	if (k & 1) {
		cout << ans << "\n";
	} else {
		int mul_half = 0;
		for (int i = 1; i <= n; ++i) {
			if (i % k == k / 2) {
				++mul_half;
			}
		}
		
		ans += (long long) mul_half * mul_half * mul_half;
		cout << ans << "\n";
	}

	return 0;

}

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

int main() {
  int N; cin >> N;
  string S; cin >> S;
  int x = 0;
  int tmp = 0;
  string tmpS;
  for (int i=0; i<S.length(); i++){
    tmpS = S[i];
    if (tmpS == "I") tmp++;
    else tmp--;
    x = max(x, tmp);
  }

  cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    vector<ll> a(M,0);
    vector<ll> b(M,0);
    for(ll i=0;i<M;++i){cin>>a[i]>>b[i];a[i]--;b[i]--;}
    vector<vector<bool>> G(N, vector<bool>(N, 0));
    for(ll i=0;i<M;++i){
        G[a[i]][b[i]]=1;
        G[b[i]][a[i]]=1;
    }
    vector<ll> ord(N,0);
    iota(ord.begin(), ord.end(), 0);
    ll count=0;
    do{
        bool ok=1;
        for(ll i=1;i<N;++i){
            if(!G[ord[i-1]][ord[i]]){ok=0;break;}
        }
        if(ok)count++;
    }while(next_permutation(ord.begin()+1, ord.end()));

    prt(count)

    return 0;
}


Measured memory_bytes: 256
N = int(input())
ans = set()

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k

for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        ans.add(k)
        ans.add((N-1)//k)
    if N%k==0:
        if check(N, k):
            ans.add(k)
        if check(N, N//k):
            ans.add(N//k)

ans.remove(1)
print(len(ans))

Measured memory_bytes: 9324
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	var x []byte
	fmt.Scan(&x)

	var cnt int
	for i := range x {
		if x[i] == '1' {
			cnt++
		}
	}
	ms := make([]int, 0)
	ms = append(ms, cnt+1)
	if cnt > 1 {
		ms = append(ms, cnt-1)
	}
	as := make([][]int, n)
	for i := range as {
		as[i] = make([]int, len(ms))
		if i == n-1 {
			for j := range ms {
				as[i][j] = 1
			}
		}
	}
	rs := make([]int, len(ms))
	for i := range ms {
		rs[i] = 0
	}

	for i := n - 1; i >= 0; i-- {
		for j := range ms {
			mod := ms[j]
			if x[i] == '1' {
				rs[j] += as[i][j]
				rs[j] %= mod
			}
			if i > 0 {
				as[i-1][j] = (as[i][j] * 2) % mod
			}
		}
	}

	for i := range x {
		if x[i] == '1' {
			if ms[0] == 2 {
				fmt.Println(0)
				continue
			}
			num := (rs[1] - as[i][1]) % ms[1]
			if num < 0 {
				num += ms[1]
			}
			fmt.Println(calc(num) + 1)
		} else {
			num := (rs[0] + as[i][0]) % ms[0]
			fmt.Println(calc(num) + 1)
		}
	}
}

func calc(num int) int {
	if num == 0 {
		return 0
	}
	cn := num
	var cnt int
	for i := 0; i < 20; i++ {
		if cn%2 == 1 {
			cnt++
			cn -= cn % 2
		}
		cn /= 2
		if cn == 0 {
			break
		}
	}
	return calc(num%cnt) + 1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


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


const int MAX = 10000;
const int NIL = -1;

struct Node {
    int p;
    int l;
    int r;
};

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d){
    if (u == NIL) return;
    D[u] = d;
    setDepth(T[u].l, d+1);
    setDepth(T[u].r, d+1);
}

int setHeight(int u){
    int h1 = 0, h2 = 0;
    if(T[u].l != NIL) h1 = setHeight(T[u].l) + 1;
    if(T[u].r != NIL) h2 = setHeight(T[u].r) + 1;
    return H[u] = max(h1, h2);
}

int getDegree(int u){
    int degree = 0;
    if(u == NIL) return NIL;
    if(T[u].l != NIL) degree++;
    if(T[u].r != NIL) degree++;
    return degree;
}

int getSibling(int u){
    int p = T[u].p;
    if( p == NIL ) return NIL;
    if(T[p].r != NIL && T[p].l != NIL) return T[p].l + T[p].r - u;
    else return NIL;
}


void print(int u){
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "sibling = " <<  getSibling(u) << ", ";
    cout << "degree = " << getDegree(u) << ", ";
    cout << "depth = " << D[u] << ", ";
    cout << "height = " << H[u] << ", ";

    if(T[u].p == NIL) cout << "root\n";
    else if(T[u].l == NIL && T[u].r == NIL) cout << "leaf\n";
    else cout << "internal node\n";
}


int main(){
    int v, l, r, root = 0;
    cin >> n;

    for(int i=0; i<n; i++) T[i].p = NIL;

    for(int i=0; i<n; i++){
        cin >> v >> l >> r;
        T[v].l = l;
        T[v].r = r;
        if(l != NIL) T[l].p = v;
        if(r != NIL) T[r].p = v;
    }

    for(int i=0; i<n; i++) {
        if(T[i].p == NIL) root = i;
    }
    
    setDepth(root, 0);
    setHeight(root);

    for(int i=0; i<n; i++) print(i);
    



    return 0;
}

Measured memory_bytes: 1168
#include <iostream>
#include <vector>
#include <tuple>
#include <complex>
#include <ios>
#include <iomanip>
#include <cmath>

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using point = std::complex<long double>;

constexpr long double EPS = 1e-7;
constexpr long double INF = 200200;
constexpr long double pi = std::acos(-1.0);

point rotate (const point &e, long double theta) {
	const long double x = e.real(), y = e.imag();
	long double a = x * std::cos(theta) - y * std::sin(theta);
	long double b = x * std::sin(theta) + y * std::cos(theta);
	return point(a, b);
}

std::pair<point, point> f (const point &p1, long double r1, const point &p2, long double r2) {
	long double d = std::sqrt(std::norm(p2 - p1));
	long double rc = (r1 * r1 + std::norm(p2 - p1) - r2 * r2) / (2.0 * d);
	long double rs = std::sqrt(r1 * r1 - rc * rc);
	point e1 = (p2 - p1) / d, e2 = rotate(e1, pi / 2.0), e3 = rotate(e1, -pi / 2.0);
	point a = p1 + (e1 * rc) + (e2 * rs);
	point b = p1 + (e1 * rc) + (e3 * rs);
	return std::make_pair(a, b);
}

bool cross (const point &a, long double r1, const point &b, long double r2) {
	return ((r1 + r2) * (r1 + r2) + EPS > (std::norm(a - b)));
}

bool is_inner (const point &a, long double r1, const point &b, long double r2) {
	return (std::norm(a - b) < (r2 - r1) * (r2 - r1) + EPS);
}

int main() {
	std::size_t n;
	int k;
	std::cin >> n >> k;
	std::vector<point> p(n);
	std::vector<long double> c(n);
	for (std::size_t i = 0; i < n; i++) {
		long double a, b;
		std::cin >> a >> b >> c[i];
		p[i] = point(a, b);
	}
	
	auto solve = [&](long double t) -> bool {
		std::vector<point> dat = p;
		for (std::size_t i = 0; i < n; i++) {
			for (std::size_t j = i + 1; j < n; j++) {
				long double r1 = t / c[i], r2 = t / c[j];
				if (not cross(p[i], r1, p[j], r2)) continue;
				if (is_inner(p[i], r1, p[j], r2)) continue;
				point a, b;
				tie(a, b) = f(p[i], r1, p[j], r2);
				dat.emplace_back(a);
				dat.emplace_back(b);
			}
		}
		
		for (const point & cp : dat) {
			int niku = 0;
			for (std::size_t i = 0; i < n; i++) {
				long double r = t / c[i], d = (std::norm(cp - p[i]));
				if (r * r + EPS >= d) niku++;
			}
			if (niku >= k) return true;
		}
		
		return false;
	};
	
	long double ng = 0, ok = INF;
	for (int i = 0; i < 100; i++) {
		long double x = (ok + ng) / 2.0;
		if (solve(x)) ok = x;
		else ng = x;
	}
	
	std::cout << std::fixed << std::setprecision(10) << ok << '\n';
	
	return 0;
}


Measured memory_bytes: 472
import java.util.*;
import java.io.*;

public class Main {

    private static int solver(int a, int b){
        if(a == b){
            return a+b;
        }else{
            int max = Math.max(a,b);
            return max + max - 1;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        // int t = in.nextInt(); // Scanner has functions to read ints, longs, strings, chars, etc.
        for (int i = 1; i <= 1; ++i) {
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.println(solver(n, m));
        }
    }
}


Measured memory_bytes: 23764
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        前処理 = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod


N, P = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append(a%2)
cnt1 = A.count(1)
cnt0 = N - cnt1
C = Combination(cnt1)
if P==1:
    res = sum(C(cnt1,i) for i in range(1,cnt1+1,2))*pow(2,cnt0)
else:
    res = sum(C(cnt1,i) for i in range(0,cnt1+1,2))*pow(2,cnt0)
print(res)

Measured memory_bytes: 62232
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int64_t calc(int64_t a, int64_t m) {
  int64_t r = 1;
  for (int64_t i = 1; i < m * 2; ++i) {
    r *= a;
    r %= m;
    if (r == 1) return i;
  }
  return 0;
}

int64_t gcd(int64_t x, int64_t y){
  if(x<y)return gcd(y,x);
  if(y==0)return x;
  return gcd(y,x%y);
}

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

int main() {
  while(1){
    int a[3],m[3];
    scanf("%d%d%d%d%d%d",a,m,a+1,m+1,a+2,m+2);
    if(!a[0])break;
    int64_t k[3];
    REP(i,3){
      k[i]=calc(a[i],m[i]);
    }
    cout << lcm(k[0],lcm(k[1],k[2])) << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
#define int LL
typedef long long LL;
const int INF = 2002002002;

struct DATA {
	int minx, miny, maxx, maxy;
};

struct STAR {
	int x, y, b;
	bool operator < (const STAR &t) const {
		return b < t.b;
	}
};

int n, d;
STAR star[1 << 19];

int N;
DATA data[1 << 20];


void init(int n)
{
	for (N = 1; N < n; N <<= 1);
	fill(data, data + (1 << 20), (DATA){INF, INF, -INF, -INF});
}

void update(int i, STAR s)
{
	i += N - 1;
	data[i] = (DATA){s.x, s.y, s.x, s.y};
	while (i > 0){
		i = (i - 1) / 2;
		data[i].minx = min(data[i * 2 + 1].minx, data[i * 2 + 2].minx);
		data[i].miny = min(data[i * 2 + 1].miny, data[i * 2 + 2].miny);
		data[i].maxx = max(data[i * 2 + 1].maxx, data[i * 2 + 2].maxx);
		data[i].maxy = max(data[i * 2 + 1].maxy, data[i * 2 + 2].maxy);
	}
}

DATA query(int a, int b, int k, int l, int r)
{
	//printf("%d %d %d %d %d\n", a, b, k, l, r);
	if (r <= a || b <= l) return (DATA){INF, INF, -INF, -INF};
	if (a <= l && r <= b) return data[k];
	DATA vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
	DATA vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
	return (DATA){min(vl.minx, vr.minx), min(vl.miny, vr.miny), max(vl.maxx, vr.maxx), max(vl.maxy, vr.maxy)};
}

signed main()
{
	scanf("%d %d", &n, &d);
	init(n);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d %d", &star[i].x, &star[i].y, &star[i].b);
		//star[i].x; star[i].y;
	}
	for (int i = n; i < 1 << 19; i++){
		star[i].b = INF;
	}
	
	sort(star, star + n);
	
	for (int i = 0; i < n; i++){
		update(i, star[i]);
	}
	
	//printf("%lld\n", (LL)INF * INF);
	
	int pr = 0;
	LL res = 0;
	for (int l = 0; star[l].b != INF; ){
		int r = pr;
		while (star[r].b - star[l].b <= d) r++;
		if (r == pr){
			l++;
			continue;
		}
		pr = r;
		
		DATA q = query(l, r, 0, 0, N);
		LL t = (LL)(q.maxx - q.minx) * (q.maxy - q.miny);
		res = max(res, t);
		
		do {
			l++;
		} while (star[l - 1].b == star[l].b);
	}
	
	printf("%lld\n", res);
	
	return 0;
}

Measured memory_bytes: 46268
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr ll INF = (1LL << 55);
int main(){
  string s, t;
  cin >> s >> t;
  
  int n = sz(s), m = sz(t);
  vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (s[i] == t[j]) dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j]);
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
    }
  }
  string res = "";
  int i = n, j = m;
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i-1][j]) i--;
    else if (dp[i][j] == dp[i][j-1]) j--;
    else {
      res += s[i-1];
      i--, j--;
    }
  }
  reverse(res.begin(), res.end());
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 37632
# ABC156 D

n,a,b=map(int,input().split())
p=10**9+7



def nCr_init(L,p):
    for i in range(L+1):
        if i<=1:
            inv[i]=1
        else:
            inv[i]=(p-inv[p%i]*(p//i))%p


def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p


nck=[0]*(b+10)
inv=[1]*(b+15)
nck[0]=1

nCr_init(b+10,p)
for i in range(b+5):
    nck[i+1]=(nck[i]*(n-i)*inv[i+1])%p

print((pow_k(2,n,p)-nck[a]-nck[b]-1)%p)

Measured memory_bytes: 88316
N=int(input())
list=[]
for x in range(N):
    list.append(input())
count=0
acount=0
bcount=0
abcount=0
for c in range(N):
    count=count+list[c].count('AB')
    if list[c][0]=='B':
        bcount=bcount+1
        if list[c][-1]=='A':
            abcount=abcount+1
    if list[c][-1]=='A':
        acount=acount+1
xx=min(acount,bcount)
if abcount==acount==bcount:
    if abcount==0:
        print(count+xx)
    else:
        print(count+xx-1)
else:
    print(count+xx)


Measured memory_bytes: 3700