akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <math.h>
#include <cstdlib>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 1e9 + 5;

int main()
{
    ll a,b,c,k,sum=0;
    cin>>a>>b>>c>>k;
 if(k<=a){
        cout<<k;
    }
    else{
        if(k<=a+b){
            cout<<a;
        }
        else{
            cout<<a - (k - a - b);
        }
    }

    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
#include <stdio.h>
#define int long long
using namespace std;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int mypow(int x, int y) {
	if (y == 0)return 1;
	if (y % 2)return mypow(x, y - 1)*x;
	else return mypow(x, y / 2)*mypow(x, y / 2);
}
int Max(int x, int y) {
	if (x > y)return x;
	else return y;
}
int Min(int x, int y) {
	if (x < y)return x;
	else return y;
}
int kai(int x) {
	int y = 1;
	for (int i = 1; i <= x; i++)y *= i;
	return y;
}
inline void shoki()
{
	srand((unsigned int)time(NULL));
}
int two(int x) {
	int cnt = 0;
	if (x == 0)return 1;
	while (x > 1) {
		x /= 2;
		cnt++;
	}
	return cnt;
}
int combi(int x, int y) {
	int cnt = 1;
	for (int i = x; x - i < y; i--)cnt *= i;
	return cnt / kai(y);
}
/*Library End!*/

signed main() {
	int n, m, x[105], y[105],X,Y;
	cin >> n >> m >> X >> Y;
	for (int i = 0; i < n; i++)cin >> x[i];
	for (int i = 0; i < m; i++)cin >> y[i];
	sort(x, x + n);
	sort(y, y + m);
	if (x[n-1] < y[0]) {
		for (int i = x[n - 1]+1; i <= y[0]; i++) {
			if (X < i&&i <= Y) {
				cout << "No War" << endl;
				goto end;
			}
		}
	}
	cout << "War" << endl;
end:;
	system("PAUSE");
	return 0;
}



Measured memory_bytes: 504
# -*- coding: utf-8 -*-
import sys

X,N = list(map(int, input().rstrip().split()))
p_list = list(map(int, input().rstrip().split()))
#-----

p_set = set(p_list)
delta = 0

while True:
    for d in [-delta, delta]:
        n = X + d
        
        if n in p_set:
            continue
        else:
            print(n)
            sys.exit()
    
    delta += 1


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

#define REP(i,a,b) for (int i = a; i < b; i++)
#define MAX 2002
// #define mdfs
int N,K;
int B[MAX][MAX];
int S[MAX][MAX];
const int INF = 1<<30;

int query(int x1,int y1,int x2,int y2){
  // return sum(x1<=x<=x2,y1<=y<=y2)
  if(x1>x2||y1>y2) return 0;
  else return S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
}

int main(void){
    // Your code here!
    cin >> N >> K;
    

    REP(i,0,N){
        int tx,ty;
        char tc;
        cin >> tx >> ty >> tc;
        if (tc == 'W') {
            ty += K; //Kを足すとBlackとみなせる
        }
        B[tx%(2*K)+1][ty%(2*K)+1] += 1;
        // cout << tx%(2*K) << ":" << ty%(2*K) << ":" << B[tx%(2*K)][ty%(2*K)] << endl;
        
    }
    
    // prepare
    REP(i,1,2*K+2){
        REP(j,1,2*K+2){
            S[i][j] = B[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
            // cout << i << ":" << j << ":" << B[i][j] << endl;
        }
    }
    
    int ans = -INF;
    REP(x,1,K+1) REP(y,1,K+1){
    int temp = query(x,y,x+K-1,y+K-1) + query(x+K,y+K,2*K,2*K) + query(1,1,x-1,y-1)
               + query(x+K,1,2*K,y-1) + query(1,y+K,x-1,2*K);
    ans = max(ans,max(temp,N-temp));
    }
    cout << ans << endl;
    



}


Measured memory_bytes: 31488
import scala.io.StdIn.readLine

object Main extends App {
  val Array(a, b, k) = readLine().split(' ').map(_.toInt)
  
  val aDivisors = (1 to a).filter(x => a % x == 0).toSet
  val bDivisors = (1 to b).filter(x => b % x == 0).toSet
  val commonDivisors = aDivisors.intersect(bDivisors).toSeq.sorted.reverse
  println(commonDivisors(k - 1))
}

Measured memory_bytes: 55164
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
  	int N;
  	string S;
  	cin >> N >> S;
  	int cnt = 0;
  	
  	for(int i=0;i<N-2;i++){
  		if(S[i]=='A' && S[i+1]== 'B' && S[i+2]== 'C') cnt++;
  	}
  	cout << cnt <<endl;
  	return 0;
}

Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int n, a, b, ans;

int Sum(int num) {
  int res = 0;
  while (num) {
    res += num % 10;
    num /= 10;
  }
  return res;
}

int main() {
  scanf("%d %d %d", &n, &a, &b);
  for (int i = 1; i <= n; i++) {
    if (Sum(i) >= a && Sum(i) <= b) {
      ans += i;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define MP make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int MOD = 1e9 + 7;

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> M(N);
    ll sum = 0;
    rep(i, N) {
        cin >> M[i];
        sum += M[i];
    }
    sort(All(M));
    X -= sum;
    int res = 0;
    res += N;
    res += X / M[0];
    cout << res << endl;
    return 0;
}

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

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

    map<string, long long int> a;
    vector<char> tmp(10);
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < 10; j++) {
            tmp[j] = str[j];
        }
        sort(tmp.begin(), tmp.end());
        for (int j = 0; j < 10; j++) {
            str[j] = tmp[j];
        }
        a[str]++;
    }

    long long int output = 0;

    for (auto num : a) {
        output += num.second * (num.second - 1) / 2;
    }

    cout << output << endl;

    return 0;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define INF 1e9

using vi=vector<int>;
using vvi=vector<vi>;

vvi matmul(vvi a,int p){
	int n=a.size();
	auto r=a;
	rep(_,p-1){
		auto d=vvi(n,vi(n,0));
		rep(i,n)rep(j,n)rep(k,n){
			d[i][j]|=r[i][k]*a[k][j];
		}
		r=d;
	}
	return r;
}

int main(){
	int n,m,a[3];
	while(cin>>n>>m>>a[0]>>a[1]>>a[2]){
		vvi z(n,vi(n,0));
		auto e=z;
		rep(_,m){
			int p,q; cin>>p>>q;
			e[p-1][q-1]=1;
		}

		vector<vvi> d(3);
		auto f=e;
		rep(p,3){
			d[p]=matmul(e,a[p]);
		}
		
		vi g(n,0);
		g[n-1]=1;
		rep(t,1000){
			bool next=0;
			vi ng(n,0);
			rep(i,n) if(!g[i]){
				bool ok=1,r;
				rep(p,3) [&]{r=0; rep(j,n) r|=(g[j] and d[p][i][j]); ok&=r;}();
				if(ok) ng[i]=next=1;
			}
			if(!next){
				cout<<"IMPOSSIBLE"<<endl;
				break;
			} else if(ng[0]){
				cout<<t+1<<endl;
				break;
			}
			rep(i,n)g[i]|=ng[i];
		}
	}
	return 0;
}



Measured memory_bytes: 3244
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int n,v[100000];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>v[i];
    map<int,int>e,o;
    for(int i=0;i<n;i++)
        if(i%2)
            o[v[i]]++;
        else
            e[v[i]]++;
    int o1=0,o2=0,e1=0,e2=0,oo,ee;
    for(auto x:o){
        if(x.second>=o1){
            swap(x.second,o1);
            oo=x.first;
        }
        if(x.second>=o2)
            o2=x.second;
    }
    for(auto x:e){
        if(x.second>=e1){
            swap(x.second,e1);
            ee=x.first;
        }
        if(x.second>=e2)
            e2=x.second;
    }
    if(oo!=ee)
        cout<<n-(o1+e1)<<endl;
    else
        cout<<n-max(o1+e2,o2+e1)<<endl;
}


Measured memory_bytes: 7296
function Input()
    str = readline()
    return str
end

function CtoI(sym::Char)
    a = parse(Int, sym)
    return a
end

str = Input()
total = 0
for c in str
    c2 = CtoI(c)
    global total = (total + c2) % 9
end

if total % 9 == 0
    println("Yes")
else
    println("No")
end


Measured memory_bytes: 163040
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cfenv>
#include <cmath>

using namespace std;

int main() {
  string s,t;
  cin>>s>>t;
  int ss = 1;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]) ss=0;
  }
  
  if(ss==1 && s.size()+1 == t.size())
  cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const ::std::uint_fast64_t MOD = 1e9+7;

class mint
{
private:
    using value_type = ::std::uint_fast64_t;
    value_type n;
public:
    mint():n(0){}
    mint(::std::int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ::std::ostream& operator<<(::std::ostream &os, const mint &a){
		return os << a.n;
	}
    friend ::std::istream& operator>>(::std::istream &is, mint &a){
        value_type temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    mint operator==(const mint &m) const {return n==m.n;}
    mint operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(value_type b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k; cin>>n>>k;
	vector<vi> adj(n);
	rep(i,n-1){
		int a,b; cin>>a>>b; a--; b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	queue<pi> que;
	que.emplace(0,-1);
	mint ans=k;
	while(!que.empty()){
		int v,p,cnt=0;
		tie(v,p) = que.front(); que.pop();
		for(auto u:adj[v]){
			if (u==p) continue;
			ans *= k-(++cnt)-(v!=0);
			que.emplace(u,v);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 7032
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<int,int> a,pair<int,int> b){
  if(a.second > b.second){
    return true;
  }
  if(a.second < b.second){
    return false;
  }  
  return a.first > b.first;
}
int main(){
  int n,m;cin>>n>>m;
  vector<pair<int,int>> arr(n);
  for(int i=0;i<n;++i){
    int a,b;cin>>a>>b;
    arr[i] = make_pair(a,b);
  }
  sort(arr.begin(),arr.end(),comp);
  set<int> st;for(int i=0;i<=m;++i)st.insert(i);
  
  long long result = 0;
  for(auto i :arr){
    if(i.first <= m){
      int mx = m-i.first;
      auto it = st.upper_bound(mx);
      if(it == st.begin()){
        continue;
      }else{
        it--;
        result += i.second;
        st.erase(it);
      }
    }
  }
  
  cout<<result<<endl;
  return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

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

	ll n;cin >> n;
	vector<pair<int, string> > a;
	vector<pair<int, string> > b;
	vector<pair<int, string> > c;
	REP(i, n){
		string str;cin >> str;
		int cou = 0;
		int mi = 0;
		REP(j, str.size()){
			if(str[j] == '(')cou++;
			else cou--;

			mi = min(mi, cou);
		}
		if(cou > 0)a.EB(-mi, str);
		else if(cou == 0)b.EB(mi, str);
		else c.EB(mi - cou, str);
	}

	sort(ALL(a));
	sort(ALL(c));
	a.insert(a.end(), b.begin(), b.end());
	a.insert(a.end(), c.begin(), c.end());

	int cou = 0;
	REP(i, a.size()){
		string str = a[i].SE;
		//cout << str << endl;
		REP(j, str.size()){
			if(str[j] == '(')cou++;
			else cou--;

			if(cou < 0){
				cout << "No" << endl;
				return 0;
			}
		}
	}

	if(cou == 0)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 81664
#include<iostream>
#include<string>
using namespace std;
int main(){
	int h,w;
	string x;
	int a[100][100];
	int i=0;
	int j=0;
	
	cin>>h>>w;
	for(i=0;i<h;i++){
		cin>>x;
		for(j=0;j<w;j++){
			if(x[j]=='.'){
				a[i][j]=0;
			}else{
				a[i][j]=1;
			}
		}
	}
	
	for(i=0;i<h;i++){
		if(a[i][0]==0){
			a[i][0]=-1;
		}else{
			a[i][0]=0;
		}
		for(j=1;j<w;j++){
			if(a[i][j]==1){
				a[i][j]=0;
			}else if(a[i][j-1]==-1){
				a[i][j]=-1;
			}else{
				a[i][j]=a[i][j-1]+1;
			}
		}
	}
	
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cout<<a[i][j];
			if(j!=w-1){
				cout<<" ";
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 3192
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const long long MOD = 1000000007;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

template <i64 mod = MOD>
struct ModInt{
    i64 p;

    ModInt() : p(0){}
    ModInt(i64 x){p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod;}

    ModInt& operator+=(const ModInt& y){p = p + *y - ((p + *y) >= mod ? mod : 0); return *this;}
    ModInt& operator-=(const ModInt& y){p = p - *y + (p - *y < 0 ? mod : 0); return *this;}
    ModInt& operator*=(const ModInt& y){p = (p * *y) % mod; return *this;}
    ModInt& operator%=(const ModInt& y){if(y)p %= *y; return *this;}

    ModInt operator+(const ModInt& y) const{ModInt x = *this; return x += y;}
    ModInt operator-(const ModInt& y) const{ModInt x = *this; return x -= y;}
    ModInt operator*(const ModInt& y) const{ModInt x = *this; return x *= y;}
    ModInt operator%(const ModInt& y) const{ModInt x = *this; return x %= y;}

    friend ostream& operator<<(ostream& stream, const ModInt<mod>& x){
        stream << *x;
        return stream;
    }

    friend ostream& operator>>(ostream& stream, const ModInt<mod>& x){
        stream >> *x;
        return stream;
    }

    ModInt& operator++(){p = (p + 1) % mod; return *this;}
    ModInt& operator--(){p = (p - 1 + mod) % mod; return *this;}

    bool operator==(const ModInt& y) const{return p == *y;}
    bool operator!=(const ModInt& y) const{return p != *y;}

    const i64& operator*() const{return p;}
    i64& operator*(){return p;}

};

using mint = ModInt<>;



void solve(long long n, long long a, long long b){

    mint ans = 1;
    auto mpow = [](auto x, i64 y){
     auto z = x;
     decltype(x) val = y & 1 ? x : decltype(x)(1);
     while(z *= z, y >>= 1)
      if(y & 1)
       val *= z;
     return val;
    };


    auto calc_fact = [mpow]{
     constexpr int N = 3e5;
     vector<mint> fact(N + 1, 1);
     vector<mint> inv(N + 1, 1);
     for(int i = 1; i < N; ++i){
      fact[i + 1] = fact[i] * (i + 1);
      inv[i + 1] = mpow(fact[i + 1], MOD - 2);
     }
     return make_pair(fact, inv);
    };
    vector<mint> fact, inv;
    tie(fact, inv) = calc_fact();

    ans = mpow(mint(2), n) - 1;

    mint v1 = 1, v2 = 1;

    for(int i = 1; i <= a; ++i){
        v1 *= mint(n - i + 1);
        v1 *= mpow(mint(i), MOD - 2);
    }

    for(int i = 1; i <= b; ++i){
        v2 *= mint(n - i + 1);
        v2 *= mpow(mint(i), MOD - 2);
    }


    ans-= v1;
    ans-= v2;
    cout << ans << endl;
}


signed main(){
    long long n;
    scanf("%lld",&n);
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    solve(n, a, b);
    return 0;
}


Measured memory_bytes: 9600
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;

static inline void p(int x) { printf("%d\n", x); }

int main()
{
	int n, cnt = 0;
	scanf("%d", &n);

	vector<int> A(n), G;
	for (int &x: A)
		scanf("%d", &x);

	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)
		G.push_back(x);
	reverse(G.begin(), G.end());

	for (int g: G)
		for (auto b = A.begin(), i = b + g, e = A.end(); i != e; i++) {
			int v = *i;
			auto j = i - g;
			for(; j >= b && *j > v; j -= g)
				*(j + g) = *j, cnt++;
			*(j + g) = v;
		}

	p(G.size());
	for (int &x: G)
		printf("%s%d", (&x == &G[0] ? "" : " "), x);
	puts("");
	p(cnt);
	for (int x: A)
		p(x);
}


Measured memory_bytes: 6264
x = int(input())
if x <= 6:
    print(1)
elif x <= 11:
    print(2)
else:
    ans = x//11
    a = x%11
    if a == 0:
        print(ans*2)
    elif a <= 6:
        print(ans*2+1)
    else:
        print(ans*2+2)

Measured memory_bytes: 70876
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int inp[25];
int ans;
int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &inp[i]);
	}
	for (int i = 1; i < n - 1; i++) {
		int sum = inp[i - 1] + inp[i] + inp[i + 1];
		int chk = min(min(inp[i - 1], inp[i]), inp[i + 1])+
			max(max(inp[i-1], inp[i]), inp[i+1]);
		if (sum == chk + inp[i]) {
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set> 
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>
using namespace std;
#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<int, int>
#define pll pair<ll, ll>
#define vii vector<ii>
#define f(i,a,b) for(int i=a; i<b; i++)
#define F first
#define S second
#define sz(a) (int)(a).size()
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
int x[] = { 0, -1, 0, 1, -1, 1, -1, 1 };
int y[] = { -1, 0, 1, 0, 1, -1, -1, 1 };
const int MOD = 998244353, N = 1e5 + 5;
const double pi = acos(-1);

int dp[200][N], weight[N], val[N];
// dp [items][sum of values]

int main()
{
	assem99;

	int n, w; cin >> n >> w;
	int sum = 0;
	f(i, 1, n + 1)
	{
		cin >> weight[i] >> val[i];
		sum += val[i];
	}
	f(i, 0, 105) f(j, 0, N) dp[i][j] = 1e9;
	f(i, 0, 105) dp[i][0] = 0;
	int ans = 0;
	f(i, 1, n + 1)
	{
		f(j, 1, sum + 1)
		{
			if (val[i] <= j) dp[i][j] = min(dp[i - 1][j], weight[i] + dp[i - 1][j - val[i]]);
			else dp[i][j] = dp[i - 1][j];
			if (dp[i][j] <= w) ans = max(ans, j);
		}
	}
	
	//f(i, 0, min(sum, w) + 1) ans = max(ans, dp[n][i]);
	cout << ans;

	return 0;
}


Measured memory_bytes: 42624
# 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    a,b,c,d = MAP()
    
    if min(b, d) - max(a, c) >= 0:
        print(min(b, d) - max(a, c))
    else:
        print(0)
if __name__ == "__main__":
    main()




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

struct List {
  int powNo;
  int motNo;
  int cabNo;
  bool isPass;
} List[1020];

int power = 0;
int motor = 0;
int cable = 0;
int N = 0;
int table[320];

void tableInit() {
  for (int i = 0; i < 320; i++) {
    table[i] = 2;
  }
}

bool input() {
  cin >> power >> motor >> cable;
  if (!power && !motor && !cable) return false;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> List[i].powNo >> List[i].motNo >> List[i].cabNo >> List[i].isPass;
  }
  return true;
}

void output() {
  for (int i = 1; i <= power+motor+cable; i++) {
    printf("%d\n", table[i]);
  }
}

void solve() {
  tableInit();
  for (int i = 0; i < N; i++) {
    if (List[i].isPass) {
      table[List[i].powNo] = 1;
      table[List[i].motNo] = 1;
      table[List[i].cabNo] = 1;
    }
  }
  for (int i = 0; i < N; i++) {
    if (!List[i].isPass) {
      if (table[List[i].powNo] == 1 && table[List[i].motNo] == 1 && table[List[i].cabNo] == 2) {
        table[List[i].cabNo] = 0;
      }
      else if (table[List[i].powNo] == 1 && table[List[i].cabNo] == 1 && table[List[i].motNo] == 2) {
        table[List[i].motNo] = 0;
      }
      else if (table[List[i].motNo] == 1 && table[List[i].cabNo] == 1 && table[List[i].powNo] == 2) {
        table[List[i].powNo] = 0;
      }
    }
  }
}

int main() {
  while (input()) {
    solve();
    output();
  }
  return 0;
}



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

using namespace std;
const long long INF = 1e18;
#define PI 3.141592653589793
#define REP(i, n) for(int i = 0;i < n;++i)
long long N,Y;
int main()
{
  cin>>N>>Y;
  N-=Y;
  int ans =N/(Y-1)+1;
  if(N%(Y-1)!=0)ans++;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3548
import math
n, m = map(int, input().split(' '))


from_n = math.factorial(n)/math.factorial(2)/math.factorial(n - 2) if n >= 2 else 0
from_m = math.factorial(m)/math.factorial(2)/math.factorial(m - 2) if m >= 2 else 0
print(int(from_n + from_m))

Measured memory_bytes: 3060
s=input()
st=[]
d=[]
for i in s:
    if i in d:
        st[d.index(i)]+=1
    else:
        d.append(i)
        st.append(1)

if len(st)==2 & st[0]==2 & st[1]==2:
    print('Yes')
else:
    print('No')

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
ll factorial(int i) {       //階乗
    if (i == 0) return 1;
    return (factorial(i - 1)) * i;
}

int main() { 
    int n;
    cin >> n;
    int a[110000];
    rep(i, n) {
        int A;
        cin >> A;
        A--;
        a[i] = A;
    }
    int count = 1;
    int j = 0;
    rep(i, n) {
        if(a[j] == 1) {
            cout << count << endl;
            return 0;
        }
        j = a[j];
        count++;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3988
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int n, a;

	cin >> n >> a;

	cout << (n - a) + 1 << endl;







	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

#define N 3
#define LIM 32
#define HN 362897

struct dep{
  int depth,key;
};

int ans[N][N]={
  {1,2,3},
  {4,5,6},
  {7,8,0}
};

int min = LIM;
struct dep h[HN];

int hash1(int k)
{
  return k % HN;
}
int hash2(int k)
{
  return 1 + k%(HN-1);
}
int hash(int k, int i)
{
  return (hash1(k) + i*hash2(k))%HN;
}


void dfs(int p[N][N], int n)
{
  int i,j,i0,j0,a=0,b=1;
  int f=0;
  int tmp[N][N];
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(ans[i][j]!=p[i][j])f++;
      if(p[i][j]==0)
      {
        i0=i;
        j0=j;
      }
      a+=p[i][j]*b;
      b*=10;
    }
  }

  if(f==0)
  {
    if(min>=n)
    {
      min=n;
    }
    return;
  }
  if(n>min) return;
  i=0;
  while(1)
  {
    b=hash(a, i);
    if(h[b].key == 0)
    {
      h[b].key=a;
      h[b].depth=n;
      break;
    }
    else if(h[b].key == a)
    {
      if(h[b].depth>n)
      {
        h[b].depth=n;
        break;
      }
      else return;
    }
    i++;
  }

  if(i0>0 && i0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0-1][j0];
    tmp[i0-1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>0 && j0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0-1];
    tmp[i0][j0-1]=f;
    dfs(tmp, n+1);
  }

  if(i0>=0 && i0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0+1][j0];
    tmp[i0+1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>=0 && j0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0+1];
    tmp[i0][j0+1]=f;
    dfs(tmp, n+1);
  }

}

int main()
{
  int i,j;
  int p[N][N];

  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      scanf("%d",&p[i][j]);
    }
  }
  dfs(p,0);

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

  return 0;
}



Measured memory_bytes: 4688
/*dismint|jjc*/
#include <bits/stdc++.h>
using namespace std;
#define forl(V, S, E) for(int V = S; V < E; V++)
#define ford(V, S, E) for(int V = S; V >= E; V--)
#define fore(E, X) for(auto &E:X)
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
typedef unordered_map<int, unordered_set<int>> graph;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int r; cin >> r;
	println(3*r*r);
}


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

using namespace std;

//const char t[20]="CODEFESTIVAL2016";

struct node{
	long long v; int tag;
	node(long long x1,int x2):v(x1),tag(x2){}
};

bool cmp(node x, node y){
	return x.v<y.v;
}

int main(){
	int w,h;
	scanf("%d%d",&w,&h);
	vector<node> a;
	int x;
	for (int i=0;i<w;i++){
		scanf("%d",&x);
		a.push_back(node(x,0));
	}
	for (int i=0;i<h;i++){
		scanf("%d",&x);
		a.push_back(node(x,1));
	}
	sort(a.begin(),a.end(),cmp);
	int cnt[2];
	long long ans=0;
	cnt[0]=cnt[1]=0;
	for (int i=0;i<a.size();i++){
		ans+=( ((a[i].tag==0)?(h+1):(w+1)) - cnt[1-a[i].tag] )*a[i].v;
		cnt[a[i].tag]++;
	}
	cout << ans <<endl;


	return 0;
}

Measured memory_bytes: 5096
let s = read_line () in
let c = String.get s 0 in
let len = String.length s in
let s2 = String.make len c in
let s2 = if(int_of_string s <= int_of_string s2) then s2 else (
  let c = (int_of_char c)+1 in
  let s2 = String.make len (char_of_int c) in
  s2
)in
Printf.printf "%s\n" s2


Measured memory_bytes: 2432
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    ll a, b;
    cin >> a >> b;
    ll ret = 0;
    for(ll i = a; i < (a / 4 + 1) * 4; ++i){
        ret = i ^ ret;
    }
    for(ll i = (b / 4) * 4; i <= b; ++i){
        ret = i ^ ret;
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
m_arr = []
a_arr = []
r_arr = []
c_arr = []
h_arr = []
n.times do
  s = gets.chomp
  case s[0]
  when "M" then
    m_arr << s
  when "A" then
    a_arr << s
  when "R" then
    r_arr << s
  when "C" then
    c_arr << s
  when "H" then
    h_arr << s
  end
end

arr = []
if m_arr.length > 0 then
  arr << m_arr.length
end
if a_arr.length > 0 then
  arr << a_arr.length
end
if r_arr.length > 0 then
  arr << r_arr.length
end
if c_arr.length > 0 then
  arr << c_arr.length
end
if h_arr.length > 0 then
  arr << h_arr.length
end

count = 0
arr.combination(3) do |n1, n2, n3|
  count += (n1 * n2 * n3)
end

puts count



Measured memory_bytes: 9468
#include <iostream>
#include <map>
using namespace std;
int main(){
	int n;
	map<int, int> cnt;
	int maxCnt = 0;
	while(cin >> n){
		cnt[n]++;
		maxCnt = max(maxCnt, cnt[n]);
	}
	for(map<int,int>::iterator itr = cnt.begin(); itr != cnt.end(); itr++){
		if(maxCnt == itr->second){
			cout << itr->first << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1196
<?php
error_reporting(0);
//$N = explode(" ",trim(fgets(STDIN)));
//list($N,$M) = explode(" ",trim(fgets(STDIN)));
$A=trim(fgets(STDIN));
$B=trim(fgets(STDIN));
$C=trim(fgets(STDIN));
$D=trim(fgets(STDIN));
printf("%d\n",min($A,$B)+min($C,$D));


Measured memory_bytes: 3700
x,y = map(int, input().split(" "))
a = [x]
idx = 0

while True:
    if idx == 0:
        idx += 1
    elif a[idx-1]*2 <= y:
        a.append(a[idx-1]*2)
        idx += 1
    else:
        break

print(len(a))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
typedef long long ll;
using namespace std;
typedef pair<int,int> P;
vector<int> dir={-1,0,1,0,-1,-1,1,1,-1};

const ll mod=1000000007;

int main() {
	int s,w;
  cin >> s >> w;
  if(s<=w)cout<<"unsafe"<<endl;
  else cout<<"safe"<<endl;
}

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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef int64_t Int;
typedef std::vector<Int> LI;
const double pi = 3.14159265358979323846264338;
const Int mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(Int& x) { if( scanf("%" PRId64, &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(Int &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

template<typename T>
struct Maybe {
   T x;
   bool valid;
   Maybe() : valid(false) {}
   Maybe(T x_) : x(x_), valid(true) {}
   operator T() const {
      assert( valid );
      return x;
   }
};

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      std::vector<Int> xs(3); scan(xs);
      for(Int i = 0; i < 3; ++i) {
         if( xs[i] == xs[(i+1)%3] ) printf("%ld\n", xs[(i+2)%3]);
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}




Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
N = int(input())
ans = 0
if N != 1:
    fact_list = factorization(N)
    for _, i in fact_list:
        j = 1
        while i >= j:
            ans += 1
            i = i - j
            j += 1
            
print(ans)

Measured memory_bytes: 9484
N, M = map(int, input().split())
ls = []
for i in range(1,M+1):
  if M%i==0:
    j = M//i
    if i<=M//N:
      ls += [i]
    if j<=M//N:
      ls += [j]
  if M**0.5<i:
    break
print(max(ls))

Measured memory_bytes: 3060
N, M = map(int, input().split())
H = list(map(int, input().split()))
load = [ [H[i]] for i in range(N)]
ans = 0

for j in range(M):
    A, B = map(int, input().split())
    load[A-1].append(H[B-1])
    load[B-1].append(H[A-1])

for i in range(N):
    if max(load[i]) == load[i][0]:
        ans += 1
        if len(load[i]) != 1:
            for j in range(len(load[i])-1):
                if load[i][0] == load[i][j+1]:
                    ans -= 1
                    break
    

#print(load)
print(ans)


Measured memory_bytes: 25972
import java.util.Scanner;

/**
 * Red Dragonfly
 */
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int x1 = sc.nextInt();
		int x2 = sc.nextInt();

		System.out.println(Math.abs(x1 - x2));
	}
}



Measured memory_bytes: 26232
#include <iostream>
#include <queue>
#include <algorithm>

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

using namespace std;

int main(void){
	int h, w; cin >> h >> w;
	queue <pair<int, int> > q;
	static int a[1000][1000];
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			char tmp;
			cin >> tmp;
			if(tmp == '#'){
				a[i][j] = 0;
				q.push(make_pair(i, j));
			} else a[i][j] = -1;
		}
	}

	while(!q.empty()){
		pair<int, int> p = q.front(); q.pop();
		for(int i=0; i<4; i++){
			if(p.first+dy[i]<0 || h-1<p.first+dy[i] || p.second+dx[i]<0 || w-1<p.second+dx[i]) continue;
			if(a[p.first+dy[i]][p.second+dx[i]] == -1){
				a[p.first+dy[i]][p.second+dx[i]] = a[p.first][p.second]+1;
				q.push(make_pair(p.first+dy[i], p.second+dx[i]));
			}
		}
	}

	int ans=0;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			ans = max(ans, a[i][j]);
		}
	}


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

Measured memory_bytes: 12304
#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>;

int main() {
	string	s;
	cin >> s;
	int		n;
	cin >> n;
	rep(i, n)
	{
		string	order;
		int a, b;
		cin >> order >> a >> b;
		int len;
		len = b - a + 1;
		if (order == "reverse")
			reverse(s.begin() + a, s.begin() + b + 1);
		else if (order == "replace")
		{
			string	alt;
			cin >> alt;
			s.replace(a, len, alt);
		}
		else
			cout << s.substr(a, len) << endl;
	}
}



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

int main() {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    if (S[K - 1] == 'A') {
        S[K - 1] = 'a';
    } else if (S[K - 1] == 'B') {
        S[K - 1] = 'b';
    } else {
        S[K - 1] = 'c';
    }
    cout << S << endl;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

const MOD = 10^^9 + 7;

int calc(string s) {
    auto dp = new int[][](s.length + 1, 13);
    // dp[i][j]
    // i : i 桁目までみた
    // j : 13 で割った余

    dp[0][0] = 1;
    for (int i = 0; i < s.length; i++) { // i 桁目
        for (int j = 0; j < 13; j++) { // 余り
            foreach (k; s[i] == '?' ? iota(0, 10) : iota(s[i]-'0', s[i]-'0'+1)) {
                dp[i + 1][(10 * j + k) % 13] += dp[i][j];
                dp[i + 1][(10 * j + k) % 13] %= MOD;

            }
        }
    }
    return dp[s.length][5];
}

void main() {
    string s = read!string;
    writeln(calc(s));
}


Measured memory_bytes: 10648
N = int(input())
MOD = 10**9 + 7

memo = [{} for _ in range(N+1)]


# 前3つのアルファベットをもとに、OKなアルファベットを生成する
def genLegalChars(last3):

    if len(last3) != 3:
        print('Error! variable "last3" is not a string of length 3. None is returned in this function.')
        return None

    if last3[1:] == 'AG':
        return ['A','T','G']
    elif last3[1:] == 'GA':
        return ['A','T','G']
    elif last3[1:] == 'AC':
        return ['A','T','C']
    elif last3[0] == 'A' and last3[2] =='G':
        return ['A','G','T']
    elif last3[0:2] == 'AG':
        return ['A','G','T']
    else:
        return ['A','T','G','C']


def DFS(length, last3):

    # その長さで、その直前3つの場合の、そのノードの値が分かっている場合はそれを返す
    if last3 in memo[length]:
        return memo[length][last3]

    # 末端の（長さが既に求められている長さに等しい）場合は1を返す
    if length == N:
        return 1

    curNodeVal = 0
    # 次のノードに来ても良いアルファベットを列挙する
    # それぞれのアルファベットからノードを分岐させ、再帰呼び出し
    for char in genLegalChars(last3):
        curNodeVal = (curNodeVal + DFS(length+1, last3[1:]+char)) % MOD

    # メモ化してからreturnする
    memo[length][last3] = curNodeVal

    return curNodeVal

print(DFS(0,'TTT'))

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

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int[] dice_number1 = new int[6];
		int[] dice_number2 = new int[6];

		for(int side_number = 0; side_number < 6; side_number++) {

			dice_number1[side_number] = in.nextInt();

		}

		for(int side_number = 0; side_number < 6; side_number++) {

			dice_number2[side_number] = in.nextInt();

		}

		dice3 dice = new dice3(dice_number1);
		boolean dice_match = dice.dice_match(dice_number1, dice_number2);

		if(dice_match) {

			System.out.println("Yes");

		}else {

			System.out.println("No");

		}
	}
}


class dice3{

	int[] dice_number;

	// ?????????????????????
	dice3(int[] dice_number){

		this.dice_number = dice_number;

	}

	// ????????????
	public int[] getDice_number() {
		return dice_number;
	}

	// ????????????
	public void setDice_number(int[] dice_number) {
		this.dice_number = dice_number;
	}

	// ?????????????????¢??????????????????
	void roll(char roll_direction){

		int tmp;

		switch(roll_direction){

		// ?????????????????¢??????
		case 'S':

			tmp = dice_number[0];
			dice_number[0] = dice_number[4];
			dice_number[4] = dice_number[5];
			dice_number[5] = dice_number[1];
			dice_number[1] = tmp;

			break;

		// ?\\???????????¢??????
		case 'N':

			tmp = dice_number[0];
			dice_number[0] = dice_number[1];
			dice_number[1] = dice_number[5];
			dice_number[5] = dice_number[4];
			dice_number[4] = tmp;

			break;

		// ??????????????¢??????
		case 'W':

			tmp = dice_number[0];
			dice_number[0] = dice_number[2];
			dice_number[2] = dice_number[5];
			dice_number[5] = dice_number[3];
			dice_number[3] = tmp;

			break;

		// ??????????????¢??????

		case 'E':

			tmp = dice_number[0];
			dice_number[0] = dice_number[3];
			dice_number[3] = dice_number[5];
			dice_number[5] = dice_number[2];
			dice_number[2] = tmp;

			break;

		}
	}

	// ?????????????????????????????¢?????????????????????
	void turn(char turn_direction) {

		int tmp;

		switch(turn_direction) {

		// ????????¢
		case 'R':

			tmp = dice_number[1];
			dice_number[1] = dice_number[3];
			dice_number[3] = dice_number[4];
			dice_number[4] = dice_number[2];
			dice_number[2]= tmp;

			break;

		// ????????¢
		case 'L':

			tmp = dice_number[1];
			dice_number[1] = dice_number[2];
			dice_number[2] = dice_number[4];
			dice_number[4] = dice_number[3];
			dice_number[3] = tmp;

			break;

		}
	}

	// ?????¨???????????°?????????????????°????????\????????§?????????????????????????????????
	boolean dice_match(int[] dice_number1, int[] dice_number2) {

		for(int i = 0; i < 6; i++) {

			if(i % 2 == 0) {

				// ??????????????¢??????
				roll('S');

			}else {

				// ?¨????????????¢??????
				roll('E');

			}

			for(int j = 0; j < 4; j++) {

				turn('R');

				if(Arrays.equals(dice_number1, dice_number2)) {

					return true;

				}
			}
		}

		return false;

	}
}

Measured memory_bytes: 26176
fun main(args: Array<String>) {
    val s = readLine()!!
    val t = readLine()!!
    val n = s.length
    for (startPos in 0 until n) {
        var i = startPos
        var r = true
        for (j in 0 until n) {
            r = s[i] == t[j]
            if (!r) break
            i = (i + 1) % n
        }
        if (r) {
            println("Yes")
            return
        }
    }
    println("No")
}


Measured memory_bytes: 33460
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        var sc = new Scanner(System.in);
        var n = sc.next();

        var ones = n.substring(n.length() - 1);
        String answer;
        switch (ones) {
            case "3":
                answer = "bon";
                break;
            case "2":
            case "4":
            case "5":
            case "7":
            case "9":
                answer = "hon";
                break;
            default:
                answer = "pon";
        }
        var writer = new PrintWriter(System.out);
        writer.println(answer);
        writer.flush();
    }
}


Measured memory_bytes: 35744
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
typedef long long ll;

const int LMT = 3010;
ll dp[LMT][LMT][4];

int main() {
  ll r,c,k;
  cin >> r >> c >> k;
  ll cl[r+1][c+1];
  for(int i=0;i<r+1;i++)
  for(int j=0;j<c+1;j++){
      cl[i][j]=0;
  }
  ll x,y,z;
  for(int i=0;i<k;i++) {
      cin >> x >> y >> z;
      cl[x][y]=z;
  }
  for(int i=0;i<LMT;i++)
  for(int j=0;j<LMT;j++)
  for(int k=0;k<4;k++){
      dp[i][j][k]=0;
  }

  for(int i=1;i<r+1;i++)
  for(int j=1;j<c+1;j++)
  for(int k=0;k<4;k++){
      //前の行のk=3か、前の列からスライド
      if(k==0)dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0]);
      //k-1か前の列からスライド
      if(k==1)dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1]);
      if(k==2)dp[i][j][k]=max({dp[i][j][1],dp[i][j-1][1]+cl[i][j],dp[i][j-1][2]});
      if(k==3)dp[i][j][k]=max({dp[i][j][2],dp[i][j-1][2]+cl[i][j],dp[i][j-1][3]});
  }

  cout << dp[r][c][3] << endl;
  return 0;
}


Measured memory_bytes: 356532
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

string s;
int k;
V< V< V<int> > > dp;

int rec(int l, int r, int cnt) {
    if (dp[l][r][cnt] != 0) return dp[l][r][cnt];
    if (l == r) return dp[l][r][cnt] = 1;
    if (l + 1 == r) {
        if (s[l] == s[r]) return dp[l][r][cnt] = 2;
        else {
            if (cnt > 0) return dp[l][r][cnt] = 2;
            else return dp[l][r][cnt] = 1;
        }
    }

    if (s[l] == s[r]) return dp[l][r][cnt] = rec(l + 1, r - 1, cnt) + 2;
    else {
        dp[l][r][cnt] = max(rec(l + 1, r, cnt), rec(l, r - 1, cnt));
        if (cnt > 0) chmax(dp[l][r][cnt], rec(l + 1, r - 1, cnt - 1) + 2);
        return dp[l][r][cnt];
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s >> k;
    int sz = s.size();
    dp.resize(sz, V< V<int> >(sz, V<int>(k + 1, 0)));
    rec(0, sz - 1, k);
    cout << dp[0][sz - 1][k] << '\n';
    return 0;
}


Measured memory_bytes: 109696
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);
vector<bool> vectorprime(ll x){
    vector<bool> is_prime(x+1);
    vector<ll> prime;
    rep(i,x+1) is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(ll i=2;i<=x;i++){
        if(is_prime[i]){
            prime.pb(i);
        }
        for(int j=i*2;j<=x;j+=i) is_prime[j]=false;
    }
    return is_prime;
}

int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll Q; cin>>Q;
    vector<bool> v=vectorprime(100000);
    vector<ll> s(100000+2,0);
    ll now=0;
    rep1(i,100000){ //0-origin:rep
        if(v[i] && v[(i+1)/2]){
            s[i+1]=s[i]+1;
        }
        else s[i+1]=s[i];
    }
    rep(i,Q){
        ll l,r; cin>>l>>r;
        cout<<s[r+1]-s[l]<<endl;
    }
}



Measured memory_bytes: 4076