akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
using namespace std;

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

  int sum = 0;
  
  for(int i = 0; i < n.length(); i++){
    sum += n[i] - '0';
  }
  
  if(stoi(n) % sum == 0){
      cout << "Yes" << endl;
  } else {
      cout << "No" << endl;
  }
  
  return 0;
}

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

res = 0
for i in range(n-1):
    if a[i] + a[i+1] <= x:
        continue

    candy = a[i] + a[i+1] - x
    res += candy
    a[i+1] = max(0, a[i+1] - candy)

print(res)

Measured memory_bytes: 84716
function solve(A, B, C, D, E, F)
    i = j = k = l = 0
    max = -Inf
    solution = (i, j, k, l)
    ok() = k * C + l * D ≤ E * (i * A + j * B) && 100 * i * A + 100 * j * B + k * C + l * D ≤ F
    while ok()
        while ok()
            while ok()
                while ok()
                    x = 100 * (k * C + l * D) / (i * 100A + j * 100B + k * C + l * D)
                    if x > max
                        solution = (i, j, k, l)
                        max = x
                    end
                    l += 1
                end
                l = 0
                k += 1
            end
            k = l = 0
            j += 1
        end
        j = k = l = 0
        i += 1
    end
    i, j, k, l = solution
    println(i * 100A + j * 100B + k * C + l * D, " ", k * C + l * D)
end

A, B, C, D, E, F = [parse(Int, x) for x in split(readline())]
solve(A, B, C, D, E, F)


Measured memory_bytes: 151916
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int n,T;
	int c,t;
	scanf("%d%d",&n,&T);
	int ans=999999;
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&c,&t);
		if(t<=T){
			ans=min(c,ans);
		}
	}
	if(ans==999999)
		puts("TLE");
	else
		printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector <ll> a(n), b(m);
  REP(i, n) {
	cin >> a[i];
  }
  REP(i, m) {
	cin >> b[i];
  }
  vector <ll> as(n + 1, 0), bs(m + 1, 0);
  REP(i, n) {
	as[i + 1] = as[i] + a[i];
  }
  REP(i, m) {
	bs[i + 1] = bs[i] + b[i];
  }
  int ans = 0;
  REP(i, n + 1) {
	if (k < as[i]) {
		continue;
	  }
	auto itr = upper_bound(all(bs), k - as[i]);
	ans = max(ans, i + (int) (itr - bs.begin()) - 1);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 9568
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int n = N / 10;
  if (n % 111 == 0)
    cout << "Yes" << endl;
  else if ((N % 1000) % 111 == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
using namespace         std;
#define                 int long long
#define                 double long double
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<'\n'
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 1014159
#define  vi vector<int>
#define  v  vector
#define die exit(0)
#define alln(arr) arr+1 , arr+1+n
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update> oset; 

int n,m,k,arr[N];

void solve()
{
    string s;
    cin>>s;

    for(auto i : s)
    {
    	cout<<'x';
    }
}


signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    int t = 1;
    //cin>>t;
    forn(i,1,t)
    {
        solve();
        nl;
    }



    return 0;

}

//       clang++ c.cpp ; ./a.out < a.txt ;  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin>>a;
  int b;
  b=a;
  a -= b / 1000 * 1000;
  if(a!=0){
    cout<<1000 - a<<'\n';
  }
  else{
    cout<<0<<'\n';
  }
  return 0;
}
 

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int x[11];
int y[11];
double road[11][11];
bool used[11];
double ans[44444];
int ptr;
int n;
void dfs(int i,int r,double cnt)
{
	used[i]=true;
	if(r==n)
		ans[ptr++]=cnt;
	for(int j=1;j<=n;j++)
		if(!used[j])
			dfs(j,r+1,cnt+road[i][j]);
	used[i]=false;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		cin>>y[i];
		for(int j=1;j<=i;j++){
			double cnt=sqrt(pow(x[j]-x[i],2)+pow(y[j]-y[i],2));
			road[i][j]=cnt;
		}
	}
	for(int i=1;i<=n;i++)
		dfs(i,1,0);
	double average=0.0;
	for(int i=0;i<ptr;i++)
		average+=ans[i];
	average/=ptr;
	average*=2.0;
	int w=1;
	int e=0;
	while(w<average){
		e++;
		w*=10;
	}
	cout<<setprecision(10+e)<<average<<endl;
	return 0;
 } 

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int main(){
  int n,m;
  cin>>n>>m;
  vi tere(1010,-1);
  REP(i,n){
    int a;
    cin>>a;
    while(a<=1000 && tere[a]==-1){
      tere[a] = i;
      ++a;
    }
  }
  vi vote(n,0);
  REP(i,m){
    int a;
    cin>>a;
    if(tere[a]!=-1)vote[tere[a]]++;
  }
  int mx = 0;
  REPR(i,n){
    if(vote[mx]<vote[i])mx=i;
  }
  cout << mx+1 << endl;
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if (N % 2 == 0) {
        int L = A[(N-1)/2] + A[N/2];
        int R = B[(N-1)/2] + B[N/2];
        cout << R - L + 1 << "\n";
    }
    else {
        int L = A[N/2], R = B[N/2];
        cout << R - L + 1 << "\n";
    }
}


Measured memory_bytes: 4720
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,k;
  cin>>k>>a>>b;
  int A=a/k;
  int B=b/k;
  int aa=a%k;
  if(A==B&&aa!=0)cout<<"NG"<<endl;
  else cout<<"OK"<<endl;
}


Measured memory_bytes: 3628
// Example program
#include <iostream>
#include <string>
using namespace std;

int main()
{
	int ans;
	string s;
	cin >> s;
	int c1 = 0, c2 = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '0')
			++c1;
		else
			++c2;
	}
	if (c1 > c2)
		ans = c1 - c2;
	else
		ans = c2 - c1;
	ans = s.size() - ans;
    cout << ans;
}


Measured memory_bytes: 512
#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}


void Main()
{
    string s;cin>>s;
    int n = SIZE(s);

    int result = 0;

    REP(i,n){
        if(s[i] != s[n-1-i]){
            result++;
        }
    }
    cout<<(result+1)/2<<endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

bool ng[10];

bool check(int N){
    while(N>0){
        if(ng[N%10]) return false;
        N/=10;
    }
    return true;
}

signed main()
{
    int N,K; cin>>N>>K;
    REP(i,K){
        int a; cin>>a;
        ng[a]=true;
    }
    for(int i=N;;i++){
        if(check(i)){
            cout<<i<<endl;
            return 0;
        }
    }
}


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

#define MAX 500000 

bool prime_table[MAX];

int main(){
	int n, i, j, ans;
	// make table
	for (i = 0; i < MAX; i++) {
		if(i==0||i==1){
			prime_table[i] = false;
		}else{
			prime_table[i] = true;
		}
	}
	// find prime
	for (i = 2; i < MAX; i++) {
		if(prime_table[i]){
			for (j = i+i; j < MAX; j+=i) {
				prime_table[j] = false;
			}
		}
	}

	while (cin >> n) {
		if (n == 0) {
			break;
		}
		ans = 0;
		for (i = 2; i <= n/2; i++) {
			j = n-i;
			if (prime_table[i] && prime_table[j]) {
				ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 0
import Data.List

base = 10^9+7 :: Integer

mulmod a b = (a * b) `mod` base

powmod a n = f 1 n a
  where
    f r 0 _ = r
    f r n t = f (if odd n then mulmod r t else r) (div n 2) (mulmod t t)

invmod a = powmod a (base - 2)

combmod n k = let k' = min k (n-k) in mulmod (foldl mulmod 1 [n-k'+1..n]) (foldl mulmod 1 $ map invmod [1..k'])

combwrmod n k = combmod (n+k-1) k

factor n = f n (2:[3,5..])
  where
    f 1 _ = []
    f n pa@(p:ps)
     | r==0 = p : f q pa
     | n<p*p = [n]
     | otherwise = f n ps
      where
        (q, r) = divMod n p

main = map read . words <$> getLine >>= \[n, m] -> print $ foldl mulmod 1 $ map (combwrmod n . genericLength) $ group $ factor m 

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()

// このHP減らすのに必要な魔力の最小値
ll dp[10005], a[1005], b[1005];
ll h, n;
int main() {
  cin >> h >> n;
  rep(i, n) { cin >> a[i] >> b[i]; }
  rep(i, h + 1) { dp[i] = 1e9; }
  dp[0] = 0;
  rep(i, h) {
    if (dp[i] == 1e9) continue;
    rep(j, n) {
      ll tmp = i + a[j];
      if (tmp > h) tmp = h;
      dp[tmp] = min(dp[tmp], dp[i] + b[j]);
    }
  }
  cout << dp[h] << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int int64_t
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define REPP(i, n) for (int i = 1; (i) < (int)(n+1); ++ (i))
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORP(i, m, n) for(int i = m; i < n+1; i++)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).begin(),(c).end(),greater<int>());
#define BIT(n) (1LL<<(n))
#define PCNT(x) __builtin_popcountll(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) x/__gcd(x,y)*y
#define PB push_back
#define MP make_pair
#define endl "\n"
#define pa cout << ans << endl
#define p(x) cout << x << endl
#define pall(x) for(auto iter : x) p(iter)
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define yn(x) cout << (x ? "Yes" : "No") << endl
using namespace std;
typedef long double LD;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
using UnweightedGraph = vector<vector<int> >;
using WeightedGraph = vector<vector<pair<int, int> > >;
const int INF = 2000000000ll;
const long double PI = acosl(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int power(int a, int b) {return b?power(a*a,b/2)*(b%2?a:1):1;}
int perm(int N, int K){
    int x=1;
    for(int i=1;i<=K;i++)
    {
        x=x*(N-i+1);
    }
    return x;
}
int factorial(int N) {return perm(N,N);}
int comb(int N,int K) {return factorial(N)/factorial(K)/factorial(N-K);}
int hcomb(int N, int K) {return comb(N+K-1, N-1);}

int dtoi(double d) {return round(d);}

int isprime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i*i <= n; ++i) {
        if (n % i ==  0) return 0;
    }
    return 1;
}

int mystoll(string S){
    int num = 0;
    for (int i = (int) S.length()-1; i >= 0; i--){
        num += (S[i]-'0') * power(10,S.length()-1-i);
    }
    return num;
}

template<class T>
int SUM(T a) {
    int sum = 0;
    for(auto iter : a) sum += iter;
    return sum;
}

void solve(int N, const vector<int> & A);

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int N;
    cin >> N;
    vector<int> A(N);
    map<int,int> L,R;
    REP (i, N) {
        cin >> A[i];
        L[A[i]+i]++;
        R[i-A[i]]++;
    }
    int ans = 0;
    for (auto itr : L) {
        ans += itr.second * R[itr.first];
    }
    pa;
    return 0;
}


/*
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_e && sh test.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_e && sh etest.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_e && sh submit.sh
*/


Measured memory_bytes: 38920
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main()
{
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;
 if ((e - a) > k ) {
   puts (":(") ;
   return 0;
 }
 puts ("Yay!");
  
  return 0;
}


Measured memory_bytes: 384
possible_appearances = ->(dice) {
  table = 
     [[0, 1, 2, 3, 4, 5], [3, 1, 0, 5, 4, 2], [1, 5, 2, 3, 0, 4], [5, 1, 3, 2, 4, 0],
      [1, 2, 0, 5, 3, 4], [3, 5, 1, 4, 0, 2], [5, 4, 2, 3, 1, 0], [2, 1, 5, 0, 4, 3],
      [1, 0, 3, 2, 5, 4], [5, 2, 1, 4, 3, 0], [2, 4, 0, 5, 1, 3], [4, 5, 3, 2, 0, 1],
      [3, 4, 5, 0, 1, 2], [4, 0, 2, 3, 5, 1], [1, 3, 5, 0, 2, 4], [2, 0, 1, 4, 5, 3],
      [0, 4, 3, 2, 1, 5], [4, 2, 5, 0, 3, 1], [4, 3, 0, 5, 2, 1], [2, 5, 4, 1, 0, 3],
      [3, 0, 4, 1, 5, 2], [0, 3, 1, 4, 2, 5], [0, 2, 4, 1, 3, 5], [5, 3, 4, 1, 2, 0]]
  result = []
  table.each do |dice1|
    another = Array.new(6, 0)
    dice1.each_with_index {|n, i| another[n] = dice[i]}
    result << another
  end
  result.uniq
}

n = gets.to_i
dices = []
n.times {dices << gets.split.map(&:to_i)}
result = "Yes"
s = dices.size
catch(:jump) do
  (s - 1).times do |i|
    appearances = possible_appearances.(dices[i])
    (i + 1).upto(s - 1) do |j|
      if appearances.include?(dices[j])
        result = "No"
        throw(:jump)
      end
    end
  end
end
puts result



Measured memory_bytes: 7040
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
             
inf = float("inf")
step = [[inf] * (w+2) for _ in range(h+2)]

if grid[1][1] == "#":
    step[1][1] = 1
else:
    step[1][1] = 0
    
for i in range(1,h+2):
    for j in range(1,w+2):
        if i == 1 and j == 1:
            continue
        if grid[i-1][j] == "#":
            y_flag = 0
        else:
            y_flag = 1 
        if grid[i][j-1] == "#":
            x_flag = 0
        else:
            x_flag = 1
        if grid[i][j] == ".":
            step[i][j] = min(step[i-1][j], step[i][j-1])
        else:
            step[i][j] = min(step[i-1][j]+y_flag, step[i][j-1]+x_flag)

print(step[h][w])

Measured memory_bytes: 44144
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int GCD(int a,int b)
{
  int r, tmp;
   /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


int Svec(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  long long int n,m,cnt=0;
  cin>>n>>m;
  cnt+=2*n+m;
  cout<<min(cnt/4,m/2)<<endl;
  
}
///////////////////////////

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

class DisjointSet
{
    public:
        vector<int> rank, p;

        DisjointSet() {}
        DisjointSet(int size)
        {
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size; i++) makeSet(i);
        }

        void makeSet(int x)
        {
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x, int y)
        {
            return findSet(x) == findSet(y);
        }

        void unite(int x, int y)
        {
            link(findSet(x), findSet(y));
        }

        void link(int x, int y)
        {
            if (rank[x] > rank[y]) {
                p[y] = x;
            } else {
                p[x] = y;
                if (rank[x] == rank[y]) {
                    rank[y]++;
                }
            }
        }

        int findSet(int x)
        {
            if (x != p[x]) {
                p[x] = findSet(p[x]);   // 経路圧縮
            }
            return p[x];
        }
};

int main()
{
    int n, a, b, q;
    int t;

    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);

    for (int i = 0; i < q; i++) {
        cin >> t >> a >> b;
        if (t == 0) ds.unite(a, b);
        else if (t == 1) {
            if (ds.same(a, b)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3176
n=int(input())
a=list(map(int,input().split()))
s=[3]+[0]*(n+1)
m=10**9+7
c=1
for i in a:
    s[i+1]+=1
    c=(c*s[i])%m
    s[i]-=1
    if s[i]<0:
        print(0)
        break
else:
    print(c)       

Measured memory_bytes: 13964
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
int r0,w0,c,r;
int main(){

while(cin>>r0>>w0>>c>>r,r0+w0+c+r){
	int ans=0;
	while(((r0+r*ans)/w0)<c)ans++;
	cout<<ans<<endl;
}
	return 0;
}


Measured memory_bytes: 3068
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
void read(int &x)
{
    int f=1;
    x=0;
    char s=getchar();
    while(s<'0'||s>'9')
    {
        if(s=='-')
            f=-1;
        s=getchar();
    }
    while(s>='0'&&s<='9')
    {
        x=x*10+s-'0';
        s=getchar();
    }
    x*=f;
}
#define ll long long
ll le[200005];
ll ri[200005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>le[i]>>ri[i];
    }
    sort(le+1,le+n+1);
    sort(ri+1,ri+n+1);
    if(n%2==1){
        cout<<ri[n/2+1]-le[n/2+1]+1LL<<endl;

    }else
    {
        cout<<ri[n/2]+ri[n/2+1]-le[n/2]-le[n/2+1]+1LL<<endl;
    }
    

    return 0;
}

Measured memory_bytes: 6720
import java.util.*;
import java.math.*;

public class Main {

    static long MOD = 1000000007;

    public static long k(long a) {
        long ret = 1;
        while(a >= 2) {
            ret *= a;
            ret %= MOD;
            a--;
        }
        return ret;
    }

    public static long comb(long a, long b) {
        BigInteger mod = new BigInteger(String.valueOf(MOD));
        BigInteger up = new BigInteger(String.valueOf(k(a)));
        BigInteger down = new BigInteger(String.valueOf(k(b))).multiply(new BigInteger(String.valueOf(k(a - b))));
        return up.multiply(down.modInverse(mod)).mod(mod).longValue();
    }


    public static void main(String[] args) {
        BigInteger mod = new BigInteger(String.valueOf(MOD));
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();

        for(int i = 1 ; i <= k; i++) {
            if (n - k + 1 < i)
                System.out.println("0");
            else
                System.out.println(new BigInteger(String.valueOf(comb(k - 1,i-1))).multiply( new BigInteger(String.valueOf(comb(n - k + 1, i)))).mod(mod).longValue());
        }



    }
}

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

using namespace std;

#define int long long

bool codejam = 0;

typedef long long li;
typedef long double ld;

void solve();

int32_t main () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	int t = 1; 
	// cin >> t;
	int tt = t;
	while (t--) { 
		if (codejam) cout << "Case #" << tt - t << ": ";
		solve();
	}
	return 0;
}
void solve() {
	int n, m; cin >> n >> m;
	vector<vector<int>> bulbs;
	int p[m + 1];
	for (int i = 1; i <= m; i += 1) {
		int k; cin >> k;
		vector<int> lol;
		for (int j = 0; j < k; ++j) {
			int lol2; cin >> lol2; lol.push_back(lol2 - 1);
		}
		bulbs.push_back(lol);
	}
	for (int i = 0; i < m; i++) {
		cin >> p[i];
	}
	int ans = 0;
	for (int mask = 0; mask < (1LL << n); mask += 1) {
		bool ok = true;
		for (int i = 0; i < (int) bulbs.size(); i += 1) {
			int x = 0;
			for (auto j: bulbs[i]) {
				if ((1LL << j) & mask) x ^= 1;
			}
			if (x != p[i]) {
				ok = false;
			}
		}
		if (ok) ++ans;
	}
	cout << ans;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    /**
	 *
	 */

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int answer = Integer.MAX_VALUE;
        //A only
        if (y > x) {
            int candidate = y-x;
            answer = Math.min(candidate, answer);
        }
        //A-B
        int negY = -y;
        if (negY >= x) {
            int candidate = negY-x + 1;
            answer = Math.min(candidate, answer);
        }
        //B-A
        int negX = -x;
        if (y >= negX) {
            int candidate = y-negX + 1;
            answer = Math.min(candidate, answer);
        }
        //B-A-B
        if(negY - negX >= 0) {
            int candidate = negY-negX + 2;
            answer = Math.min(candidate, answer);
        }
        System.out.println(answer);
    }
}

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

int main() {
  int N,M,AnsAC=0,AnsWA=0;
  cin>>N>>M;
  vector<int> AC(N),WA(N);
  int p;
  string S;
  rep(i,M){cin>>p>>S;
           if(AC.at(p-1)==0){if(S=="AC"){AC.at(p-1)++;}else{WA.at(p-1)++;}}
          }
  rep(i,N){AnsAC+=AC.at(i);AnsWA+=AC.at(i)*WA.at(i);}
  cout<<AnsAC<<" "<<AnsWA<<endl;
}


Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;


int main() {
  int n;
  cin >> n;
  cout << 48-n << endl;
}


Measured memory_bytes: 256
# Problem E - Red Scarf

# input
N = int(input())
a_nums = list(map(int, input().split()))

# initialization
xor_sum = 0
# xor sum
for a in a_nums:
    xor_sum = xor_sum ^ a
ans = []

# xor check
for a in a_nums:
    tmp = xor_sum ^ a
    ans.append(tmp)

# output
print(" ".join(list(map(str, ans))))


Measured memory_bytes: 41728
//Volume0-0048
import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		//declare
		float weight;
		String class_;
		
		//input
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			weight = sc.nextFloat();
			
			//calculate
			class_ = null;
			if     (91.00 < weight)                   {class_ = "heavy";      }
			else if(81.00 < weight && weight <= 91.00){class_ = "light heavy";}
			else if(75.00 < weight && weight <= 81.00){class_ = "middle";}
			else if(69.00 < weight && weight <= 75.00){class_ = "light middle";}
			else if(64.00 < weight && weight <= 69.00){class_ = "welter";}
			else if(60.00 < weight && weight <= 64.00){class_ = "light welter";}
			else if(57.00 < weight && weight <= 60.00){class_ = "light";}
			else if(54.00 < weight && weight <= 57.00){class_ = "feather";}
			else if(51.00 < weight && weight <= 54.00){class_ = "bantam";}
			else if(48.00 < weight && weight <= 51.00){class_ = "fly";}
			else if(                  weight <= 48.00){class_ = "light fly";}
			
			//output
			System.out.println(class_);
		}
	}
}

Measured memory_bytes: 19272
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    ll div = 1000000007;
    int dp[100000];
    int hole[100000] = {0};

    rep(i, M) {
        int a;
        cin >> a;
        hole[a] = 1;
    }

    dp[0] = 1;

    if (hole[1]) {
        dp[1] = 0;
    } else {
        dp[1] = 1;
    }

    if (N > 1) {
        for (int i = 2; i < N + 1; i++) {
            if (hole[i] == 1) {
                dp[i] = 0;
            } else {
                dp[i] = (dp[i - 1] + dp[i-2]) % div;
            }
        }
    }

    cout << dp[N] << endl;
}

Measured memory_bytes: 1024
class Main{
		    public static void main(String[] a){
		         int x = 0;
		         for(int i=1;i<=9;i++){
		             for(int j=1;j<=9;j++){
		                 x = i*j;
		                 System.out.println(i+"x"+ j +"="+ x);
		             }
		         }
		    }
		}


Measured memory_bytes: 24164
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

a_e = [a, b, c, d, e]

for i in range(5):
    for j in range(5):
        if abs(a_e[i] - a_e[j]) > k:
            print(":(")
            exit()

print("Yay!")


Measured memory_bytes: 3316
/**
 *  author: mahfuzz
 *  created: 28.04.2020
**/
 
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << #x << ':' << x << "\n"
typedef long long ll;

int main(int argc, char* argv[]){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int x; cin >> x;
    int l = 0, r = 1023456;
    
    while(r - l > 1){
        int mid = l + (r - l) / 2;
        int temp = floor(mid * 1.08);
        
        if(temp == x){
            cout << mid << "\n";
            return 0;
        }else if(temp > x)
            r = mid;
        else if(temp < x)
            l = mid;
    }
    
    cout << ":(\n";
    
        
    return 0;
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9) 
input = sys.stdin.readline
def gdc(a, b):
    if b == 0:
        return a
    return gdc(b, a%b)
def lcm(a,b):
    return a*b//gdc(a,b)

def main():
    N = int(input())
    T = [int(input()) for i in range(N)]
    if N == 1:
        return print(T[0])
    ans = lcm(max(T[0], T[1]), min(T[0], T[1]))
    if N == 2:
        print(ans)
        return
    for i in range(2,N):
        ans = lcm(max(ans, T[i]), min(ans, T[i]))
    print(ans)

if __name__ == '__main__':
    main()

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

int cnt;

void insertion_sort(vector<int> &A, int n, int g) {  
  for ( int i = g; i < n; i++ ) {
    int v = A[i];
    int j = i-g;
    while ( j >= 0 && A[j] > v ) {
      A[j+g] = A[j];
      j -= g;
      cnt++;
    }
    A[j+g] = v;    
  }
}

vector<int> shell_sort(vector<int> &A, int n) {
  vector<int> G;
  for ( int h = 1; ; ) {
    if ( h > n ) break;
    G.push_back(h);
    h = 3*h+1;
  }

  for ( int i = (int)G.size()-1; i >= 0; i-- ) {
    insertion_sort(A, n, G[i]);
  }

  return G;
}

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

  vector<int> A(n);
  for ( int i = 0; i < n; i++ ) cin >> A[i];

  vector<int> G = shell_sort(A, n);

  cout << G.size() << endl;
  for ( int i = (int)G.size()-1; i >= 0; i-- ) {
    cout << G[i];
    if ( i ) cout << " ";
  }
  cout << endl;

  cout << cnt << endl;

  for ( int i = 0; i < n; i++ ) cout << A[i] << endl;
  
  return 0;
}



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

#define MOD (1000000007)

int main(void) {
    char s[100005];
    scanf("%s", (char *)&s);
    int len = strlen(s);
    unsigned long long *new, *old;
    unsigned long long _ta[13], _tb[13];
    new = _ta; old = _tb;
    if (s[len-1] == '?') {
        for (int i = 0; i < 13; i++) {
            old[i] = i < 10;
        }
    } else {
        for (int i = 0; i < 13; i++) {
            old[i] = i == (s[len-1] - '0');
        }
    }

    for (int i = len - 2, digit = 10; i >= 0; i--, digit = (digit * 10) % 13) {
        for (int j = 0; j < 13; j++) {
            new[j] = 0;
        }
        if (s[i] == '?') {
            for (int m = 0; m<10; m++) {
                for (int j = 0; j<13; j++) {
                    int sh = (j + m * digit) % 13;
                    new[sh] += old[j];
                }
            }
        } else {
            int m = s[i] - '0';
            for (int j = 0; j<13; j++) {
                int sh = (j + m * digit) % 13;
                new[sh] += old[j];
            }
        }
        
        for (int j = 0; j<13; j++) {
            new[j] %= MOD;
        }
        unsigned long long *temp;
        temp = new;
        new = old;
        old = temp;
    }

    printf("%lld\n", old[5]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace boost::multiprecision;
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int N=1000005;
ll fact[N],invfact[N];
ll power(ll x,ll y){
  if(y<=0) return 1LL;
  ll z=power(x,y/2);
  if(y%2) return (((z*z)%mod)*x)%mod;
  return (z*z)%mod;
}

void pre(){
  fact[0]=invfact[0]=invfact[1]=fact[1]=1;
  rep(i,2,N) fact[i]=(i*fact[i-1])%mod;
  rep(i,2,N) invfact[i]=(invfact[i-1]*power(i,mod-2))%mod;
}
ll nCr(ll n,ll k){ return (((fact[n]*invfact[n-k])%mod)*invfact[k])%mod; }



const int N1=1e5+1;
vector<int> isprime(N1,1);
set<int>prime;
void seive(){
  rep(i,2,sqrt(N1)+1){
      if(isprime[i]){
        for(int j=i*i;j<N1;j+=i) isprime[j]=0;
        prime.insert(i);
      }
  }
  rep(i,sqrt(N1)+1,N1) if(isprime[i]) prime.insert(i);
}



struct dsu {
    vector<int> par, rank;
    dsu(int n): par(n+1), rank(n+1) {
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            rank[i]= 1;
        }
    }
    int root(int a) {
        if (a == par[a]) return a;
        return par[a] = root(par[a]);
    }
    void merge(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (rank[a] > rank[b]) swap(a, b);
        par[b] = a;
    }
    set<int> parent(int n){
        set<int> s;
        for(int i=1;i<=n;i++){
            s.insert(root(i));
        }
        return s;
    }
};
void solve(){
  int n;
  cin>>n;
  int a[n];
  rep(i,0,n) cin>>a[i];
  int mx=*max_element(a,a+n),mn=*min_element(a,a+n);
  int mxid=max_element(a,a+n)-a,mnid=min_element(a,a+n)-a;
  cout<<2*n-1<<endl;
  if(abs(mx)>=abs(mn)){
    rep(i,0,n) cout<<mxid+1<<" "<<i+1<<endl;
    rep(i,1,n) cout<<i<<" "<<i+1<<endl;
  }
  else{
    rep(i,0,n) cout<<mnid+1<<" "<<i+1<<endl;
    rrep(i,n-1,1) cout<<i+1<<" "<<i<<endl;
  }
}

int main(){
    optimizeIO();

    {solve();}
}


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

#define MOD (1000 * 1000 * 1000 + 7)
#define INF (1LL << 60)
#define pb push_back
#define po pop_back
#define fi first
#define se second

typedef long long ll;
typedef long double ld;

#define maxn 105
#define maxw 100005
ll A[maxn][2];
ll dp[maxn][maxw];

int main() {
    int N, W;
    scanf("%d%d", &N, &W);

    for (int i = 1; i <= N; ++i)
        scanf("%lld%lld", &A[i][0], &A[i][1]);

    for (int i = 1; i <= N; ++i) {
        dp[i][A[i][0]] = max(A[i][1], dp[i - 1][A[i][0]]);

        for (int j = 1; j <= W; ++j) {
            if (dp[i - 1][j] != 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);

            if (j + A[i][0] <= W && dp[i - 1][j] != 0)
                dp[i][j + A[i][0]] = dp[i - 1][j] + A[i][1];
        }
    }

    ll m = 0;
    for (int i = 1; i <= W; ++i)
        m = max(m, dp[N][i]);

    printf("%lld\n", m);
    return 0;
}

Measured memory_bytes: 78080
#include<stdio.h>

int main(){

int N,ans=0;
scanf("%d",&N);

int L[N];

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

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 (L[i]!=L[j]&&L[j]!=L[k]&&L[k]!=L[i]){
                if (L[i]>L[j]&&L[i]>L[k]){
                    if (L[i]<L[j]+L[k]){ans++;}
                }else if (L[j]>L[k]){
                    if (L[j]<L[k]+L[i]){ans++;}
                }else{
                    if (L[k]<L[j]+L[i]){ans++;}
                }
            }
        }
    }
}

printf("%d",ans);

return 0;

}

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

using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl
#define HYPP(x) hypot(x.first,x.second)

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;



int main() {
	int H, W;
	cin >> H >> W;
	vector<string> grid(H);
	for (int i = 0; i < H; i++) {
		cin >> grid[i];
	}

	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			if (grid[y][x] == '#') {
				if (x != 0) {
					if (grid[y][x - 1] == '#') {
						continue;
					}
				}
				if (y != 0) {
					if (grid[y - 1][x] == '#') {
						continue;
					}
				}
				if (x != W - 1) {
					if (grid[y][x + 1] == '#') {
						continue;
					}
				}
				if (y != H - 1) {
					if (grid[y + 1][x] == '#') {
						continue;
					}
				}
				cout << "No" << endl;
				return 0;
			}
			
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, m, n) for(ll i = (ll)m; i < (ll)n; i++)
#define PER(i, m, n) for(ll i = (ll)m; i > (ll)n; i--)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

int main(){
    string s, t;
    cin >> s >> t;
    ll ans = t.size();

    REP(i, 0, s.size()-t.size()+1){
        ll cnt = 0;
        REP(j, 0, t.size()){
            if(t[j] != s[i+j]){
                cnt++;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if (a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 17320
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vll = vector<vector<ll> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using the = pair<int, int>;
using lthe = pair<ll, ll>;

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

const int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };

int dp[3002][3002] = { 0 };

int main() {
	string s, t;
	cin >> s >> t;
	int ns = s.size(), nt = t.size();

	//vector<vector<string>>dp(ns + 1, vector<string>(nt + 1, ""));
	//初期化済み
	//dp
	for (int i = 1; i <= ns; i++) {
		for (int j = 1; j <= nt; j++) {
			if (s[i - 1] == t[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				if (dp[i - 1][j] < dp[i][j - 1])  dp[i][j] = dp[i][j - 1];
				else  dp[i][j] = dp[i - 1][j];
			}
		}
	}

	string ans = "";
	int i = (int)s.size(), j = (int)t.size();
	while (i > 0 && j > 0)
	{
		// (i-1, j) -> (i, j) と更新されていた場合
		if (dp[i][j] == dp[i - 1][j]) {
			--i; // DP の遷移を遡る
		}

		// (i, j-1) -> (i, j) と更新されていた場合
		else if (dp[i][j] == dp[i][j - 1]) {
			--j; // DP の遷移を遡る
		}

		// (i-1, j-1) -> (i, j) と更新されていた場合
		else {
			ans = s[i - 1] + ans; // このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
			--i, --j; // DP の遷移を遡る
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 35456
from itertools import permutations
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
x = [i for i in range(1, n + 1)]
y = []
for i in permutations(x, n):
    y.append(list(i))
a = b = 0
for i in range(len(y)):
    if y[i] == p:
        a = i + 1
    if y[i] == q:
        b = i + 1
print(abs(a - b))


Measured memory_bytes: 10228
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	ll suma = 0;
	map<ll, ll> counter;
	for (int i = 0; i < n; i++) {
		ll a;
		cin >> a;
		suma += a;
		counter[a]++;
	}
	ll q;
	cin >> q;
	for (int qq = 0; qq < q; qq++) {
		ll b, c;
		cin >> b >> c;
		ll counter_b = counter[b];
		counter[b] = 0;
		counter[c] += counter_b;
		suma -= b*counter_b;
		suma += c*counter_b;
		cout << suma << "\n";
	}
}



Measured memory_bytes: 9408
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
  if A[i] > B[i]:
    ans += B[i]
  else:
    ans += A[i]
    B[i] -= A[i]
    if A[i+1] > B[i]:
      ans += B[i]
      A[i+1] -= B[i]
    else:
      ans += A[i+1]
      A[i+1] = 0
print(ans)

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

int main(){
	string s1, s2;
	int ans;
	
	cin>>s1>>s2;
	
	for(int i=0; i<s1.length(); i++){
		if(s1[i]==s2[i]) ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

                        namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Trim().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        public class lower_bound<T> : IComparer<T> where T : IComparable<T>
        {
            public int Compare(T x, T y)
            {
                return 0 <= x.CompareTo(y) ? 1 : -1;
            }
        }
        static int LIS(List<int> A)
        {
            var lst = new List<int>();
            for(var i=0;i<A.Count;++i)
            {
                var num = ~lst.BinarySearch(A[i], new lower_bound<int>());
                if (lst.Count <= num)
                    lst.Add(A[i]);
                else
                    lst[num] = A[i];
            }
            return lst.Count;
        }
        static void Main(string[] args)
        {
            var n = Sarray()[0];
            var A = new List<int>();
            for (var i = 0; i < n; ++i)
            { A.Add((int)Sarray()[0]); }
            WriteLine(LIS(A));
        }
    }
}


Measured memory_bytes: 23952
#include <stdio.h>

int main(void) {
  
  int A, B, x, y, z, max;
  
  	scanf("%d %d", &A, &B);
  
  	x = A + B;
  	y = A - B;
  	z = A * B;
  
  	if (x >= y)
      if (x >= z)
        max = x;
  	  else
        max = z;
  	else if (y >= z)
      max = y;
  	else
      max = z;
  
  printf("%d \n", max);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define eb emplace_back
#define f first
#define s second
#define sz(x) (ll)x.size()
#define lnt(s) (ll)s.length()
#define mt(cnt) cnt.empty()
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> osSet;

using pll = pair<ll, ll>;
using pl = pair<ll, pll>;
using tll = tuple<ll, ll, ll>;

const ll maxN = 1e5 + 11;
const ll INF = 1e17;
const ll MOD = 1e9 + 7;

ll xs[] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll ys[] = {0, 0, -1, 1, -1, 1, -1, 1};

ll segtree[maxN << 2];
ll lazy[maxN << 2];
ll A[maxN];

inline ll left(ll x){
	return x << 1;
}

inline ll right(ll x){
	return (x<<1) + 1;
}

ll func(ll x){
	return (x*(x+1))/2;
}

ll _pow(ll b, ll p){
	if(p == 0) return 1;
	if(p == 1) return b;
	ll exB = b*b;
	if(p&1) return b*_pow(exB, p/2);
	return _pow(exB, p/2);
}

bool isP[maxN];

void init(){
	memset(isP, 1, sizeof(isP));
	isP[0] = isP[1] = 0;
	for(ll i=2; i<maxN; i++){
		if(isP[i]){
			for(ll j=(i<<1); j<maxN; j+=i)
				isP[j] = 0;
		}
	}
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll t;
	init();
	cin >> t;
	for(ll i=2; i<maxN; i++){
		if(isP[i] and i>=t){
			cout << i;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3744
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = 0;
		int current = 0;
		for(int i = 0; i < n; ++i) {
			int h = sc.nextInt();
			if(h >= current) {
				++ans;
				current = h;
			}
		}
		
		System.out.println(ans);
	}
}


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

int main() {
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  int count=0;
  while(a>=b){
    b=b*2;
    count++;
  }
  while(b>=c){
    c=c*2;
    count++;
  }
  if(count<=k) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef long long int int64;

void sort(int *a,int n){
  if(n<=1) return;
  int p=rand()%n;
  int pivot=a[p];
  a[p]=a[0];
  int cnt=1;
  int index=0;
  int l=1;
  int r=n;
  while(l<r){
    if(a[l]==pivot){
      cnt++;
      l++;
    } else if(a[l]<pivot){
      a[index++]=a[l++];
    } else {
      int swap=a[l];
      a[l]=a[r-1];
      a[r-1]=swap;
      r--;
    }
  }
  sort(a,index);
  sort(a+l,n-l);
  while(cnt--) a[index++]=pivot;
}

void run(void){
  int w,h;
  scanf("%d%d",&w,&h);
  int *p=(int *)calloc(w,sizeof(int));
  int i;
  for(i=0;i<w;i++) scanf("%d",p+i);
  int *q=(int *)calloc(h,sizeof(int));
  for(i=0;i<h;i++) scanf("%d",q+i);
  srand((unsigned)time(NULL));
  sort(p,w);
  sort(q,h);
  int x=0;
  int y=0;
  int64 sum=0;
  while(x<w && y<h){
    if(p[x]<=q[y]){
      sum+=(int64)p[x++]*(h+1-y);
    } else {
      sum+=(int64)q[y++]*(w+1-x);
    }
  }
  while(x<w) sum+=p[x++];
  while(y<h) sum+=q[y++];
  printf("%lld\n",sum);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 896
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

for i in range(N):
    for j in range(1, min(K+1, len(h)-i)):
        dp[i+j] = min(dp[i] + abs(h[j+i] - h[i]), dp[i+j])

print(dp[N-1])

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

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define FORR(i,m,n) for(int i=m;i>=n;i--)
#define pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 999999999

using namespace std;

#define int long long

int32_t main(){
	string str;
	cin >> str;
	int n=str.size();
	
	stack<int> st;
	REP(i, n){
		if(str[i]=='S') st.push(str[i]);
		else if(st.size()!=0 && st.top() == 'S') st.pop();
		else st.push(str[i]);
	}

	cout << st.size() << endl;
}

Measured memory_bytes: 2052