akhauriyash/Code-Regression huggingface dataset:
let rec power ( * ) e m n =
  if n <= 0 then e
  else power ( * ) (if n land 1 = 0 then e else m * e) (m * m) (n lsr 1)

let m = 1000000007
let ( +^ ) x y = (x + y) mod m
let ( -^ ) x y = x +^ (m - y)
let ( *^ ) x y = (x * y) mod m
let ( /^ ) x y = power ( *^ ) x y (m - 2)

let perm n k = Array.fold_left ( *^ ) 1 @@ Array.init k @@ ( + ) @@ n - k + 1

(* 全体の数nを固定して，選ぶ個数kを変えた時の組み合わせの数nCkを
   intと準同型な体の上でメモ化して計算する関数
   nを固定してk以下の全てのk'に対してnCk'を計算する時，
   時間計算量はO(k)，空間計算量はO(n) *)
let binom_memo :
  (* intからの準同型写像 *)
  of_int:(int -> 'a) ->
  (* 乗算 *)
  mul:('a -> 'a -> 'a) ->
  (* 除算 *)
  div:('a -> 'a -> 'a) ->
  (* 全体の数n *)
  int ->
  (* 選ぶ個数kを受け取って，組み合わせの数nCkを返す関数 *)
  (int -> 'a)
= fun ~of_int ~mul ~div n ->
  let i = ref 0 in
  (* 組み合わせの数を覚えておく配列
     !i以下の要素は既に組み合わせの数をメモしている *)
  let a = Array.make (n / 2 + 1) (of_int 1) in
  (* 途中までの計算結果をメモしつつ，組み合わせの数nCkを求める
     nを部分適用した関数を覚えておけば，途中までの計算結果はシェアされる *)
  let rec binom_memo_aux k =
    if k <= !i
    then a.(k)
    else begin
      incr i;
      a.(!i) <- div (mul a.(!i - 1) (of_int (n - !i + 1))) (of_int !i);
      binom_memo_aux k
    end in
  fun k -> binom_memo_aux @@ min k @@ n - k;;

let () = Scanf.scanf "%d %d" @@ fun n m ->
  let dp = Array.make (n + 1) (perm m n) in
  let binom = binom_memo ~of_int:Fun.id ~mul:( *^ ) ~div:( /^ ) n in
  let perms = Array.make (n + 2) 0 in (* (m-i)P(n-i) *)
  perms.(0) <- perm m n;
  for i = 0 to n do
    dp.(i) <- dp.(i) *^ perms.(i) *^ binom i;
    perms.(i + 1) <- perms.(i) /^ (m - i)
  done;
  Printf.printf "%d\n" @@
  Array.fold_right ( -^ ) dp 0


Measured memory_bytes: 21584
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char const* argv[])
{
	double a, b;

	cin >> a >> b;
	cout << (int)(a/b) << " " << (int)a%(int)b << " " << fixed << setprecision(5) << a/b << endl;

	return 0;
}


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

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

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

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

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n)
    {
        cin >> a[i];
        a[i]--;
    }
    vector<ll> b(n,0);
    REP(i,n){
        b[a[i]]++;
    }
    vector<ll> c(n);
    ll ans=0;
    REP(i,n){
        c[i]=b[i]*(b[i]-1)/2;
        ans+=c[i];
    }

    REP(i,n){
cout<<ans-c[a[i]]+(c[a[i]]*(b[a[i]]-2)/b[a[i]])<<endl;
    }
}

Measured memory_bytes: 7924
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int h, w;
  cin >> h >> w;
  vector<vi> c(10, vi(10));
  rep(i, 10) rep(j, 10) cin >> c[i][j];
  rep(k, 10) rep(i, 10) rep(j, 10) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
  int ans = 0;
  rep(i, h) rep(j, w) {
    int a;
    cin >> a;
    if(a == -1) continue;
    ans += c[a][1];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1000;

const int mod = 1e9+7;
struct mint {
    ll x;
    mint (ll x = 0) : x((x%mod+mod)%mod) {}
    mint operator -() const {return mint(-x);}
    mint& operator +=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator -=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator *=(const mint a) {(x *= a.x) %= mod; return *this;}
    mint operator +(const mint a) const {return mint(*this) += a;}
    mint operator -(const mint a) const {return mint(*this) -= a;}
    mint operator *(const mint a) const {return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {return pow(mod-2);}
    mint operator /=(const mint a) {return *this *= a.inv();}
    mint operator /(const mint a) {return mint(*this) /= a;}
};
istream& operator >>(istream &is, const mint &a) {return is >> a.x;}
ostream& operator <<(ostream &os, const mint &a) {return os << a.x;}

struct permutation {
    vector<mint> fact, ifact;
    permutation(int n) : fact(n+1), ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; i--) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[n-k];
    }
};

int k;
vvint g;
permutation pm(100005);

mint dfs(int v, int p = -1) {
    mint res;
    if (p == -1) res = pm(k,g[v].size()+1);
    else res = pm(k-2,g[v].size()-1);
    for (int n_v : g[v]) {
        if (n_v == p) continue;
        res *= dfs(n_v,v);
    }
    return res;
}

int main() {
    int n; cin >> n >> k;
    g.resize(n);
    rep(i,n-1) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cout << dfs(0) << endl;
}

Measured memory_bytes: 12032
import java.util.*;

public class Main {
  public static void main(String[] srgs) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    final int MAX = 100001;
    int[] a = new int[n];
    int[] number = new int[MAX];
    for(int i = 0; i < n; i++) {
      a[i] = Integer.parseInt(sc.next());
      if(a[i] != 0) number[a[i]-1]++;
      number[a[i]]++;
      if(a[i] != MAX) number[a[i]+1]++;
    }
    int ans = 0;
    for(int i = 0; i < MAX; i++) {
      ans = Math.max(ans, number[i]);
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 46180
from collections import deque

h, w = map(int, input().split())

a = [[False] * (w + 2)]
for y in range(h):
    a.append([False] + [x != '#' for x in input()] + [False])
a.append([False] * (w + 2))

s = deque()
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if not a[i][j]:
            s.append((i, j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i - 1][j]:
            a[i - 1][j] = False
            ns.append((i - 1, j))
        if a[i + 1][j]:
            a[i + 1][j] = False
            ns.append((i + 1, j))
        if a[i][j - 1]:
            a[i][j - 1] = False
            ns.append((i, j - 1))
        if a[i][j + 1]:
            a[i][j + 1] = False
            ns.append((i, j + 1))

    s = ns
    ans += 1

print(ans)


Measured memory_bytes: 98780
import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		boolean flag[]=new boolean[64];
		List<List<Integer>> mask=new ArrayList<>();
		int n=in.nextInt();
		for(int i=0;i<n;i++) {
			int k=Integer.parseInt(in.next());
			List<Integer> ls=new ArrayList<>();
			for(int j=0;j<k;j++)ls.add(Integer.parseInt(in.next()));
			mask.add(ls);
		}
		
		int m=in.nextInt();
		PrintWriter out=new PrintWriter(System.out);
		for(int i=0;i<m;i++) {
			int odr=Integer.parseInt(in.next());
			
			switch(odr){
				case 0:
					int index0=Integer.parseInt(in.next());
					out.println((flag[index0])? 1:0);
					break;
					
				case 1:
					int index1=Integer.parseInt(in.next());
					for(int j=0;j<mask.get(index1).size();j++)flag[mask.get(index1).get(j)]=true;
					break;
					
				case 2:
					int index2=Integer.parseInt(in.next());
					for(int j=0;j<mask.get(index2).size();j++)flag[mask.get(index2).get(j)]=false;
					break;
					
				case 3:
					int index3=Integer.parseInt(in.next());
					for(int j=0;j<mask.get(index3).size();j++)flag[mask.get(index3).get(j)]=(flag[mask.get(index3).get(j)])? false:true;
					break;
					
				case 4:
					int index4=Integer.parseInt(in.next());
					int cnt1=0;
					for(int j=0;j<mask.get(index4).size();j++)if(flag[mask.get(index4).get(j)])cnt1++;
					if(cnt1==mask.get(index4).size())out.println(1);
					else out.println(0);
					break;
					
				case 5:
					int index5=Integer.parseInt(in.next());
					int cnt2=0;
					for(int j=0;j<mask.get(index5).size();j++)if(flag[mask.get(index5).get(j)])cnt2++;
					if(cnt2>0)out.println(1);
					else out.println(0);
					break;
					
				case 6:
					int index6=Integer.parseInt(in.next());
					int cnt3=0;
					for(int j=0;j<mask.get(index6).size();j++)if(flag[mask.get(index6).get(j)])cnt3++;
					if(cnt3==0)out.println(1);
					else out.println(0);
					break;
					
				case 7:
					int index7=Integer.parseInt(in.next());
					int cnt4=0;
					for(int j=0;j<mask.get(index7).size();j++)if(flag[mask.get(index7).get(j)])cnt4++;
					out.println(cnt4);
					break;
					
				case 8:
					int index8=Integer.parseInt(in.next());
					long dec=0;
					for(int j=0;j<mask.get(index8).size();j++) {
						if(flag[mask.get(index8).get(j)]) {
							dec+=pow(mask.get(index8).get(j));
						}
					}
					out.println(Long.toUnsignedString(dec));
					break;
			}
		}
		out.flush();
	}
	
	static long pow(int p) {
		long res=1;
		for(int i=0;i<p;i++)res*=2;
		return res;
	}

}


Measured memory_bytes: 78988
s = input()
flg = 0
if s[0] != "A":
  flg = 1
if s[2:-1].count("C") != 1:
  flg = 1
else:
  l = s.index("C")
  s = s[1:l] + s[l+1:]
  if s.islower():
    pass
  else:
    flg = 1
if flg == 1:
  print("WA")
else:
  print("AC")

Measured memory_bytes: 3060
#include <stdio.h>
 
int main(void)
{   int a,b,i;
    char op;
    for(i=1;i>0;i++){
        scanf("%d %c %d",&a,&op,&b);
        if(op=='+')
        {printf("%d\n",a+b);
        }
        else if(op=='-')
        {printf("%d\n",a-b);
        }
        else if(op=='*')
        {printf("%d\n",a*b);
        }
        else if(op=='/'){
            printf("%d\n",a/b);
        }else if(op=='?') {
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  ll L, R; std::cin >> L >> R;
  std::vector<int> k(2019);

  for(ll i=L; i<=R; i++){
    ll m = i%2019;
    if (k[m] >= 3) break;
    k[m]++;
  }
  
  ll ans = std::numeric_limits<ll>::max();
  for(int i=0; i<2019; i++) {
    if ( k[i] == 0 ) continue;
    ll ansm = i;
    for(int j=0; j<2019; j++) {
      bool flag = false;
      if ( i == j ) {
        if ( k[j] >= 2 ) {
          ansm *= j;
          flag = true;
        }
      }
      else if ( k[j] != 0 ) {
        ansm *= j;
        flag = true;
      }
      if(flag) ans = std::min(ansm%2019, ans);
      ansm = i;
    }
  }

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

  return 0;
}


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

#define int long long
#define itn int
#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'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
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<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 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, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

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

    set<int> se;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            se.insert(i);
            se.insert(n / i);
        }
    }

    int nn = n - 1;
    se.insert(nn);
    for (int i = 1; i * i <= nn; i++) {
        if (nn % i == 0) {
            se.insert(i);
            se.insert(nn / i);
        }
    }

    int ans = 0;
    repall (e, se) {
        if (e == 1) continue;
        int tmp = n;
        while (tmp % e == 0) tmp /= e;
        if (tmp % e == 1) ans++;
    }
    print(ans);

    return 0;
}


Measured memory_bytes: 512
import math
import collections
from sys import exit
from itertools import product

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = list(input())
n = len(s)
ans = 0
for p in product((0,1), repeat=n):
    total = 0
    for i in range(n):
        if p[i] == 1:
            ans += total
            total = 0
        else:
            total = total*10 + int(s[i])
    ans += total
print(ans)

Measured memory_bytes: 9344
#include<stdio.h>
int main(void)
{
	int t,n,s,f,i,x;
	while(1){
		scanf("%d",&t);
		if(t==0)	break;
		scanf("%d",&n);
		x=0;
		for(i=1;i<=n;i++){
			scanf("%d %d",&s,&f);
			x=x+f-s;
		}
		if(x>=t)	printf("OK\n");
		else	printf("%d\n",t-x);
	}
	return 0;
}



Measured memory_bytes: 2032
#include <stdio.h>

int main(void)
{
	int n, old;
	int i;
	int ent[7];

	while (1) {
		scanf("%d", &n);
		if (n == 0) break;
		for (i = 0; i < 7; i++)
			ent[i] = 0;
		for (i = 0; i < n; i++) {
			scanf("%d", &old);
			if (old >= 0 && old <= 9)
				ent[0]++;
			else if (old >= 10 && old <= 19)
				ent[1]++;
			else if (old >= 20 && old <= 29)
				ent[2]++;
			else if (old >= 30 && old <= 39)
				ent[3]++;
			else if (old >= 40 && old <= 49)
				ent[4]++;
			else if (old >= 50 && old <= 59)
				ent[5]++;
			else if (old >= 60)
				ent[6]++;
		}
		for (i = 0; i < 7; i++)
			printf("%d\n", ent[i]);
	}
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
pair<int,int>x[1<<17],y[1<<17];int i,n,p[1<<17],s;
vector<pair<int,pair<int,int> > >G;
int f(int a){return p[a]-a?p[a]=f(p[a]):a;}
main()
{
	for(cin>>n;i++<n;x[i].second=y[i].second=p[i]=i)cin>>x[i].first>>y[i].first;
	sort(x+1,x+n+1),sort(y+1,y+n+1);
	for(i=0;++i<n;)
	{
		G.push_back(make_pair(abs(x[i].first-x[i+1].first),make_pair(x[i].second,x[i+1].second)));
		G.push_back(make_pair(abs(y[i].first-y[i+1].first),make_pair(y[i].second,y[i+1].second)));
	}
	sort(G.begin(),G.end());
	for(i=0;i<2*n-2;i++)
	{
		int x=G[i].second.first,y=G[i].second.second;
		if(f(x)-f(y))
		{
			s+=G[i].first;
			p[f(x)]=f(y);
		}
	}
	cout<<s<<endl;
}

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

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

int main() {
  int n,X,gcd,x0;
  cin >> n >> X >> x0;
  gcd = abs(x0-X);
  for(int i = 1;i < n;i++){
    int x;
    cin >> x;
    gcd = GCD(abs(x-X),gcd);
  }
  cout << gcd << endl;
}


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

int main() {
 ll N,K;
 cin >> N >> K;
 ll d = 1000000000 +7;
 vector<ll> A(N);
 for(ll i = 0;i<N;i++){
    cin >> A[i];
   }
 ll ans1 = 0;
  for(ll i = 0;i<N;i++){
    for(ll j = i+1;j<N;j++){
      if(A[i] > A[j]) ans1++;
    }
  }
  
  ans1 = ((ans1%d)*(K%d))%d;
  
  vector<pair<ll,ll>> p;
  for(ll i = 0;i<N;i++){
    ll c = 0;
    for(ll j = 0;j<N;j++){
      if(A[i] > A[j]) c++;
    }
    p.push_back(make_pair(A[i],c));
  }
  ll ans2 = ((K%d)*((K-1)%d)/2)%d;
  ll sum = 0;
  for(ll i = 0;i<N;i++){
    sum = (sum + p[i].second)%d;
  }
  ans2 = ((sum%d)*(ans2%d))%d;
   cout << (ans1 + ans2)%d << endl;
}

Measured memory_bytes: 384
import java.util.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int res = -1;
        
        for(double i = 1;i <= 50000;i++){
            if(Math.floor(i * 1.08) == N){
                res = (int)(Math.floor(i));
                break;
            }
        }
        
        if(res != -1){
            System.out.println(res);
        }else{
            System.out.println(":(");
        }
    }
}


Measured memory_bytes: 23876
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>  
#include<set>
#include<iterator>
#include<list>
#include<utility>
#include<cstdlib>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
#define PI  2*acos(0.0)
#define pb push_back

       
using namespace std;
using ll = long long;
using lli = long long int;
using ld = long double;



int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

ll n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)  cin>>a[i];

ll cnt=0;
sort(a,a+n);
for(int i=0;i<n-2;i++)
{
	for(int j=i+1;j<n-1;j++)
	{
		for(int k=j+1;k<n;k++)
		{
			if(a[i]+a[j]>a[k] && a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k] )
			{
				cnt++;
			}
			
		}
		
	}
	
}


cout<<cnt<<"\n";


	
	
	return 0;
	
	
	       /***Israil Hosen
	            Computer Science & Engineering
	         University Of Rajshahi.
	         ***/
	
	
	
}

Measured memory_bytes: 3132
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/

import math
import statistics

s = input()
length = 0
ans = 0
for ch in s:
    if ch in ('A','C','G','T'):
        length += 1
        ans = max(ans, length)
    else:
        length = 0
print(ans)


Measured memory_bytes: 5212
import sys
input = sys.stdin.readline

X,N=map(int,input().split())
P=set(map(int,input().split()))

if not (X in P):
    print(X)
else:
    ANS=-1
    for i in range(100):
        for to in [X-i,X+i]:
            if not(to in P):
                ANS=to
                break
        if ANS!=-1:
            break
    print(ANS)
    



Measured memory_bytes: 9188
#define _USE_MATH_DEFINES
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
using namespace std;

int main(){
	int n;
	long long int result = 1;
	cin >> n;
	for (; n > 0; --n) {
		result *= n;
	}
	cout << result << endl;
	return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <cmath>
#include <string>

using namespace std;

int main(void) {
    int x,res = 0;
    cin >> x;
    for(int i = 0;i < 1000;i++) {
        for(int ii = 2;ii < 12;ii++) {
            int t = pow(i,ii);
            if(t > x)
                break;
            else
                res = max(res,t);
        }
    }
    cout << res << endl;
    return 0;
}


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

namespace ABC092C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] aa = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int sum = Enumerable.Range(0, n-1).Select(i => Math.Abs(aa[i] - aa[i + 1])).Sum() + Math.Abs(aa[0]) + Math.Abs(aa[n - 1]);
            for (int i = 0; i < n; i++)
            {
                int ans = sum;
                if (i != 0 && i != n - 1)
                {
                    ans = ans - Math.Abs(aa[i] - aa[i - 1]) - Math.Abs(aa[i] - aa[i + 1]) + Math.Abs(aa[i - 1] - aa[i + 1]);
                }
                else if (i == 0)
                {
                    ans = ans - Math.Abs(aa[0]) - Math.Abs(aa[0] - aa[1]) + Math.Abs(aa[1]);
                }
                else if (i == n - 1)
                {
                    ans = ans - Math.Abs(aa[n - 1]) - Math.Abs(aa[n - 1] - aa[n - 2]) + Math.Abs(aa[n - 2]);
                }
                Console.WriteLine(ans);
            }
        }
    }
}


Measured memory_bytes: 26076
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void ReadInput(int *inputA, int *inputB, int *inputC, int *inputK)
{
    scanf("%d %d %d %d", inputA, inputB, inputC, inputK);
}

void CountA(int * inputA, int * inputK , int * outputVal)
{
    while(1)
    {
        if(*inputA == 0)
        {
            break;
        }
        else if (*inputK == 0)
        {
            break;
        }
        *inputA = *inputA - 1;
        *inputK = *inputK - 1;
        *outputVal = *outputVal + 1;
    }
}

void CountB(int *inputB, int * inputK, int *outputVal)
{
    while(1)
    {
        if(*inputB == 0)
        {
            break;
        }
        else if (*inputK == 0)
        {
            break;
        }
        
        *inputB = *inputB - 1;
        *inputK = *inputK - 1;
        *outputVal = *outputVal + 0;
    }
}

void CountC(int *inputC, int * inputK, int *outputVal)
{
    while(1)
    {
        if(*inputC == 0)
        {
            break;
        }
        else if (*inputK == 0)
        {
            break;
        }
        *inputC = *inputC - 1;
        *inputK = *inputK - 1;
        *outputVal = *outputVal + (-1);
    }
}
void FreeMemory(int *inputA, int *inputB,int *inputC, int * inputK)
{
    free(inputA);
    free(inputB);
    free(inputC);
    free(inputK);
}

int main(int argc, const char * argv[])
{
    int * inputA = malloc(100*sizeof(int));
    int *inputB = malloc(100*sizeof(int));
    int *inputC = malloc(100*sizeof(int));
    int *inputK = malloc(100*sizeof(int));
    int outputVal = 0;
    int * outputValP = &outputVal;
    
    ReadInput(inputA, inputB, inputC, inputK);
    CountA(inputA,inputK, outputValP);
    CountB(inputB,inputK, outputValP);
    CountC(inputC,inputK, outputValP);

    
    printf("%d \n",outputVal);
    
    return 0;
}


Measured memory_bytes: 1732
import sys;print("\n".join(["{:.3f}".format(int((e*c-b*f)/(a*e-b*d)*1000)/1000) + " " + "{:.3f}".format(int((-d*c+a*f)/(a*e-b*d)*1000)/1000) for x in sys.stdin for a, b, c, d, e, f in [[int(y) for y in x.split()]] ]))


Measured memory_bytes: 5628
#include <stdio.h>

int main(){
  int h,w;
  int i,j;

  while(1){
    scanf("%d %d",&h,&w);
    if(h==0 && w==0) break;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
        if(i==0 || i==h-1 || j==0 || j==w-1) printf("#");
        else{printf(".");}
      }
      printf("\n");
    }
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#define DIVCEIL(A,B) ((A+(B-1))/B)
#define LL long long
using namespace std;

const string YES = "Yes";
const string NO = "No";

void solve(std::string s, long long x, long long y){
    auto n = s.size();
    vector<LL> dxs, dys;
    int i=0;
    LL curr=0;
    for(auto c:s){
        if(c=='T'){
            if(i%2==0)dxs.emplace_back(curr);
            else dys.emplace_back(curr);
            i++;
            curr=0;
        }
        else curr++;
    }
    if(i%2==0)dxs.emplace_back(curr);
    else dys.emplace_back(curr);
    vector<LL> dp1(2*n+1, 0), dp2(2*n+1, 0);

    if(!dxs.empty()) {
        dp1[n + dxs[0]]++;
        dxs.erase(dxs.begin());
    }

    for(auto dx: dxs){
        for(LL j=0; j<=2*n; j++)dp2[j]=0;
        for(LL j=0; j<=2*n; j++){
            if(dp1[j]>0){
                if(j-dx >= 0)dp2[j-dx]++;
                if(j+dx <= 2*n)dp2[j+dx]++;
            }
        }
        swap(dp1, dp2);
    }

    if(dp1[n+x] == 0){
        cout << NO << endl;
        return;
    }

    for(LL j=0; j<=2*n; j++)dp1[j]=0;
    dp1[n]++;
    for(auto dy: dys){
        for(LL j=0; j<=2*n; j++)dp2[j]=0;
        for(LL j=0; j<=2*n; j++){
            if(dp1[j]>0){
                if(j-dy >= 0)dp2[j-dy]++;
                if(j+dy <= 2*n)dp2[j+dy]++;
            }
        }
        swap(dp1, dp2);
    }

    cout << (dp1[n+y] == 0 ? NO : YES) << endl;
}

int main(){
    std::string s;
    std::cin >> s;
    long long x;
    scanf("%lld",&x);
    long long y;
    scanf("%lld",&y);
    solve(s, x, y);
    return 0;
}


Measured memory_bytes: 640
import math
import sys
input = sys.stdin.readline


def main():
    sc = Scan()
    n = sc.intarr()[0]
    array = []
    for i in range(n):
        array.append(sc.intarr())
    d_sum = 0
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            distance = math.sqrt(
                (array[i][0] - array[j][0])**2 + (array[i][1] - array[j][1])**2)
            d_sum += distance
    comb = math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
    ans = d_sum * (n-1) / comb

    print(ans)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


Measured memory_bytes: 3064
(defun kth-term ()
  (let ((x '(1 1 1 2 1 2 1 5 2 2 1 5 1 2 1 14 1 5 1 5 2 2 1 15 2 2 5 4 1 4 1 51))
        (k (read)))
    (format t "~d~%" (nth (1- k) x))))


(kth-term)

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

int main() {
  int n;
  int check = 1;
  cin >> n;
  for (int i = 0; i < 10; i++) {
    if (n < check*2) {
      cout << check << endl;
      break;
    }
    else if(n >= check*2){
      check *= 2;
    }
  }
}  

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

int main() {
  int A,B,C;
  C=0;
  string S;
  cin>>A>>B;
  cin>>S;
  if(S.at(A)=='-'){
   C=20; 
  }
  for (int i = 0; i < A+B+1; i++) {
  if(S.at(i)!='-'){
    C=C+1;
  }
}
if(C==A+B+20){
cout << "Yes" << endl;
} else{
  cout <<"No"<< endl;
}
//  cout<<C<<endl;
//  cout<<S<<endl;
//  cout << S.at(0) << endl;
}

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

int		main(void)
{
	char a, b;
	cin >> a >> b;
	char ans;
	if (a == 'H')
		b == 'H' ? ans = 'H' : ans = 'D';
	if (a == 'D')
		b == 'H' ? ans = 'D' : ans = 'H';
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define rd read()
#define maxn 200001
#define gc getchar()
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define pb push_back
#define db double
#define pu puts(" ")
const int p=998244353;
int read() {
	int x=0,f=1;
	char ch=gc;
	while(!isdigit(ch)) {
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(isdigit(ch))x=x*10+ch-48,ch=gc;
	return x*f;
}
void print(int x) {
	if(x>9)print(x/10);
	putchar(x%10+48);
}

int main() {
    int n=rd,a=rd,b=rd;
    printf("%d %d\n",min(a,b),max(a+b-n,0));
	return 0;
}

Measured memory_bytes: 256
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
//10の1/2乗（ルート）pow(10, 0.5)
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int k,s;
  cin >> k >> s;
  int count = 0;
  for(int x=0;x<=k;x++){
    for(int y=0;y<=k;y++){
      int z = s - x - y;
      if(0 <= z && z <= k) count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
 
#define llong long long
#define inf 999999999
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<PP, int> PPP;
typedef struct data{
	int now;
	int cost;
}data;
int nh[4] = {1, 0, -1, 0};
int nw[4] = {0, 1, 0, -1};
 
 
 
 
 
int main(){
	vector<int> a;
	int n;
	cin >> n;
	int in;
	for(int i = 0; i < n; i++){
		cin >> in;
		a.pb(in);
	}
	sort(a.begin(), a.end());
	int ans1 = a[n-1];
	int ans2;
	double check = ans1/2.0;
	auto it = lower_bound(a.begin(), a.end(), check);

	int kouho1 = *it;
	int kouho2 = *it != check ? *(it-1) : *it;

	if(kouho1 == check){
		ans2 = kouho1;
	}else if(kouho1 == ans1){
		ans2 = kouho2;
	}else if(kouho1 - check < check - kouho2){
		ans2 = kouho1;
	}else{
		ans2 = kouho2;
	}


	cout << ans1 << " " << ans2 << endl;
 
	return 0;
}

Measured memory_bytes: 892
package main

import (
	"fmt"
)

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
func main() {
	var S string
	fmt.Scan(&S)
	maxl := 0
	for i := 0; i < len(S); i++ {
		for j := i; j < len(S)+1; j++ {
			s := S[i:j]
			ACGT := true
			for _, v := range s {
				if v != 'A' && v != 'G' && v != 'C' && v != 'T' {
					ACGT = false
					break
				}
			}
			if ACGT {
				maxl = max(maxl, len(s))
			}
		}
	}
	fmt.Println(maxl)

}


Measured memory_bytes: 512
#include <set>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, Sn;
int ch[N];

multiset<int> l, r;

int main() {
	
	cin >> n;
	Sn = 1 << n;
	
	int x;
	for (int i = 1; i <= Sn; ++i) {
		cin >> x;
		l.insert(x);	
	}
	
	r.insert(*(--l.end()));
	l.erase((--l.end()));
	
	int ok = 1;
	while (!l.empty()) {
		multiset<int> :: iterator it, en;
		
		int cnt = 0;
		for (it = r.begin(); it != r.end(); ++it) {
			en = l.lower_bound(*it);
			if (!l.empty() && en == l.begin()) { ok = 0; break; }
			ch[++cnt] = *(--en);
			l.erase(en);
		}
		if (!ok)	break;
		
		for (int i = 1; i <= cnt; ++i)	r.insert(ch[i]);
	}
	
	puts(ok ? "Yes" : "No");
	
	return 0;
}

Measured memory_bytes: 13056
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>

const int kN = 185 + 5;
int n, m;
char s[kN][kN];
int dp[kN][kN][kN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++ i) {
    scanf("%s", s[i] + 1);
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = m; j >= 1; -- j) {
      dp[i][j][j] = s[i][j] == s[i - 1][j] ? dp[i - 1][j][j] + 1 : 1;
      for (int k = j + 1; k <= m; ++ k) {
        dp[i][j][k] = s[i][k] == s[i][k - 1] ? std::min(dp[i][j][k - 1], dp[i][j + 1][k]) : 0;
      }
    }
  }
  if (dp[n][1][m] == n) return puts("0"), 0;

  for (int depth = 1; ; ++ depth) {
    for (int i = n; i >= 1; -- i) {
      for (int j = 1; j <= m; ++ j) {
        std::vector<int> tmp(m + 1);
        for (int k = j + 1, p = j; k <= m; ++ k) {
          while (p + 2 < k && dp[i][j][p] > dp[i][p + 1][k] && dp[i][j][p + 1] > dp[i][p + 2][k]) ++ p;
          tmp[k] = std::max(tmp[k], std::min(dp[i][j][p], dp[i][p + 1][k]));
          if (p + 2 <= k) {
            tmp[k] = std::max(tmp[k], std::min(dp[i][j][p + 1], dp[i][p + 2][k]));
          }
        }
        for (int k = j; k <= m; ++ k) {
          dp[i][j][k] = std::max(dp[i - dp[i][j][k]][j][k] + dp[i][j][k], tmp[k]);
        }
      }
    }
    if (dp[n][1][m] == n) {
      printf("%d\n", depth);
      break;
    }
  }
}


Measured memory_bytes: 26752
import java.util.Iterator;
import java.util.Scanner;

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

		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		
		String ans = "WA";
		if (s.charAt(0) == 'A') {
			int count = 0;
			int index = 0;
			for (int i = 2; i < s.length() - 1; i++) {
				if (s.charAt(i) == 'C') {
					count++;
					index = i;
				}
			}
			if (count == 1) {
				boolean flg = true; 
				for (int i = 1; i < s.length(); i++) {
					if (i == index) {
						continue;
					}
					
					if (Character.isUpperCase(s.charAt(i))) {
						flg = false;
						break;
					}
					
				}
				if (flg) {
					ans ="AC";
				}
			}
		}
		System.out.println(ans);
	}
}

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

namespace AGC006_A
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var s = Console.ReadLine();
            var t = Console.ReadLine();
            var N = s.Length;
            int r;
            //int ans = N * 2;
            int cnt = 0;
            int max = 0;

            for (int i = 0; i < N; i++)
            {
                cnt = 0;
                for (r = 0;  r < N; r++)
                {
                    if (i + r >=  N)
                    {
                        break;
                    }
                    if (s[i + r] == t[r])
                    {
                        cnt++;
                    }
                }
                max = Math.Max(cnt, max);
                
            }

            Console.WriteLine(N *2 - max);
        }
    }
}


Measured memory_bytes: 2776
A, B, C, X, Y = [int(i) for i in input().split()]

# A, B バラ買いパターン
total1 = A * X + B * Y

# A, B どちらか必要な量を超えるパターン
total2 = 2 * C * max(X, Y)

# 必要最小限の C セットを買い, 足りない分はバラ買いパターン
P = B if X < Y else A
total3 = 2 * C * min(X, Y) + P * abs(X - Y)

# 上記のうちで一番安いもの
ret = min(total1, min(total2, total3))
print(ret)


Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    string s,t,u;
    cin>>s>>t;
    int a,b;
    cin>>a>>b;
    cin>>u;
    if(u==s) a--;
    else b--;
    cout<<a<<' '<<b;
}

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

int main(){
    string s; cin >> s;
    bool flag = true;
    if(s.at(0) != 'A'){
        flag = false;
    }
    else{
        //3~size()-1文字までに大文字がCのみ
        int cnt = 0;
        for(int i=1;i<s.size();i++){
            if(i == 1 || i == s.size()-1){
                if(isupper(s.at(i))){ //i文字目が大文字
                    flag = false;
                    break;
                }
            }
            else{
                if(isupper(s.at(i))){ //i文字目が大文字
                    if(s.at(i) == 'C'){ //i文字目がC
                        cnt++;
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(cnt != 1){
            flag = false;
        }
    }
  string ans;
    if(flag){
        ans = "AC";
    }
    else{
        ans = "WA";
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};

int main(){
  int n,m; cin >> n >> m;
  vi a(n);
  rep(i,n) {
    cin >> a[i];
    a[i] /= 2;
  }

  ll X = a[0];
  rep(i,n) X = lcm(X,a[i]);
  rep(i,n) {
    if((X/a[i])%2 == 0){
      cout << 0 << endl;
      return 0;
    }
  }

  int ans = m/X;
  cout << ans - ans/2 << endl;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int n;
	int s=0;
	cin>>n;
	int i;
	int a[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		s^=a[i];
	}
	for(i=0;i<n;i++)
	cout<<(s^a[i])<<" ";
	cout<<endl;
	return 0;
}



Measured memory_bytes: 4444
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
vector<vector<ll> > v(200001);
bool maki[200001];
ll uni[200005];
ll root(ll u){
    if(uni[u]<0)return u;
    return uni[u]=root(uni[u]);
}

void connect(int a,int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(uni[a]<uni[b]){
        a^=b;
        b^=a;
        a^=b;
    }
    uni[a]+=uni[b];
    uni[b]=a;
    return;
}
ll size(ll u){
    return -uni[root(u)];
}

void dfs(ll n){
	if(v[n].size()==0)return;
	maki[n]=true;
	ll num=v[n][0];
	for(auto& i:v[n]){
		connect(i,num);
		if(maki[i]==0)dfs(i);
	}
	return;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    memset(uni,-1,sizeof(uni));
    memset(maki,0,sizeof(maki));
    ll n;
    cin>>n;
    ll a,b;
    for(int i=0;i<n-1;i++){
    	cin>>a>>b;
    	a--;b--;
    	v[a].pb(b);
    	v[b].pb(a);
    }
    dfs(0LL);
    ll c,d;
    for(int i=0;i<n;i++){
    	if(root(i)!=root(0LL)){
    		a=size(i);
    		b=size(0LL);
    		c=root(i);
    		d=root(0LL);
    		break;
    	}
    }
    bool niko;
    if(a<b){swap(a,b);swap(c,d);/*cout << "maki"<<endl;*/}
    niko=(b>ll(n/3));
    ll m1=1,m2=2,m3=3;
    ll ans[n];
    if(niko){
    	//cout << "i" <<endl;
    	for(int i=0;i<n;i++){
    		if(root(i)==c){
    			if(m1<=n){
    				ans[i]=m1;
    			    m1+=3;
    			}
    			else{
    				ans[i]=m3;
    				m3+=3;
    			}
    		}else{
    			if(m2<=n){
    				ans[i]=m2;
    				m2+=3;
    			}else{
    				ans[i]=m3;
    				m3+=3;
    			}
    		}
    	}
    }else{
    	/*cout << "j"<<endl;
    	cout << c<<endl;*/
    	for(int i=0;i<n;i++){
    		//cout << root(i) <<endl;
    		if(root(i)==c){//big
    			if(m1<=n){
    				ans[i]=m1;
    				m1+=3;
    			}else if(m2<=n){
    				ans[i]=m2;
    				m2+=3;
    			}else{
    				ans[i]=m3;
    				m3+=3;
    			}
    			
    		}else{
    			ans[i]=m3;
    			m3+=3;
    		}
    	}
    }
    for(int i=0;i<n;i++){
    	cout << ans[i]<<" ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 18408
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) (x).begin(), (x).end()

using namespace __gnu_pbds;
using namespace std;

using ull = unsigned long long;
using ll = long long;
using ld = long double;
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int inf = INT_MAX;
const int N = 3000 + 5;

int n, m, a[N][N];
ll dp[N][N][4];

ll recurse(int r, int c, int taken) {
    if (r == n and c == m) {
        if (taken + 1 <= 3)
            return a[r][c];
        return 0;
    }
    if (dp[r][c][taken] != -1)
        return dp[r][c][taken];

    ll ans = 0;
    if (a[r][c]) {
        if (taken + 1 <= 3) {
            if (r + 1 <= n)
                ans = max(ans, a[r][c] + recurse(r + 1, c, 0));
            if (c + 1 <= m)
                ans = max(ans, a[r][c] + recurse(r, c + 1, taken + 1));
        }
    }
    if (r + 1 <= n)
        ans = max(ans, recurse(r + 1, c, 0));
    if (c + 1 <= m)
        ans = max(ans, recurse(r, c + 1, taken));
    return dp[r][c][taken] = ans;
}

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

    int k;
    cin >> n >> m >> k;

    while (k--) {
        int x, y, val;
        cin >> x >> y >> val;
        a[x][y] = val;
    }

    memset(dp, -1, sizeof(dp));
    cout << recurse(1, 1, 0) << "\n";
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> price(30);
  vector<int> cost(30);
  vector<int> profit(30);
  int totalProfit = 0;
 
  for (int i; i < N; i++) cin >> price.at(i);
  for (int i; i < N; i++) cin >> cost.at(i);
  for (int i; i < N; i++) {
    profit.at(i) = price.at(i) - cost.at(i);
    if (profit.at(i) > 0) totalProfit += profit.at(i);
  }
  cout << totalProfit << endl;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;
using ll = long long;

#define X 1000000007

int main(){
    int n;
    cin>>n;
    ll a=1,b=1,c=1;
    for(int i = 0; i<n;i++){
        a = (a*10) % X;
        b = (b*9) % X;
        c = (c*8) % X;
    }
    cout<<(a-b*2+c+2*X) % X<<endl;
    return 0;
}  


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

using namespace std;

const int MAX = 1e5 + 10 ;
long long dp[MAX] ;
vector< vector<int> >adjlist ;
vector<bool>visited ;

void dfs(int node)
{
    visited[node] = true ;
    for(int i = 0 ; i < adjlist[node].size() ; ++i)
    {
        int child = adjlist[node][i] ;
        if(!visited[child])
            dfs(child);
        dp[node] = max(dp[node] , dp[child]+1);
    }
    return ;
}

int main()
{
    int n , m ;
    cin>>n>>m ;
    adjlist = vector< vector<int> >(n+1) ;
    visited = vector<bool>(n+1) ;
    for(int i = 0 ; i < m ; ++i)
    {
        int x , y ;
        cin>>x>>y ;
        adjlist[x].push_back(y) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        if(!visited[i])
            dfs(i) ;
    }
    long long ans = 0 ;
    for(int i = 1 ; i <= n ; ++i)
        ans = max(ans , dp[i]);
    return cout<<ans<<"\n" , 0 ;
}


Measured memory_bytes: 8576
#include<iostream>
#include<algorithm>
#include<vector>

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<int> data(N);
  for (int i=0; i<N; i++){
    std::cin >> data.at(i);
  }
  std::sort(data.rbegin(), data.rend());
  int sum=0;
  for (int i=0; i<K; i++) {
    sum += data.at(i);
  }
  std::cout << sum << std::endl;
}

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

// auto MOD int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


// combination MOD prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} comb(1000005);

int modPow(long long a, long long n) {
  if (n == 0) return 1; // 0乗にも対応する場合
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}

int main() {
    int S;
    cin >> S;
    mint ans = 0;
    int cnt = 0;
    while(1) {
        if (S<3) break;
        S-=3;
        cnt++;
        mint tmp = comb.fact[S+cnt-1];
        tmp/=comb.fact[S];
        tmp/=comb.fact[cnt-1];
        ans+=tmp;
        //cout << tmp << endl;
    }
    cout << ans << endl;

}


Measured memory_bytes: 18640