akhauriyash/Code-Regression huggingface dataset:
#pragma comment(linker, "/STACK:640000000")
#include <bits/stdc++.h>

#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define ll long long
#define bit __builtin_popcountll
#define sqr(x) (x) * (x)
#define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)

using namespace std;

typedef pair<int, int> pii;

const double eps = 1e-9;
const double pi = acos(-1.0);

string s[100];

int main() {
	#ifdef LOCAL
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	#endif

	int a, b; cin >> a >> b;

	string rowA = "";
	string rowB = "";

	for (int i = 0; i < 100; i++) {
		rowA += "#";
		rowB += ".";
	}

	for (int i = 0; i < 50; i++) s[i] = rowA;
	for (int i = 50; i < 100; i++) s[i] = rowB;

	a--;
	b--;

	for (int i = 0; i < 49; i += 2) {
		for (int j = 0; j < 100; j += 2) {
			if (a > 0) {
				s[i][j] = '.';
				a--;
			}
		}
	}

	for (int i = 51; i < 100; i += 2) {
		for (int j = 0; j < 100; j += 2) {
			if (b > 0) {
				s[i][j] = '#';
				b--;
			}
		}
	}

	cout << 100 << " " << 100 << endl;
	for (int i = 0; i < 100; i++) {
		cout << s[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
A = list(map(int,input().split()))

D=defaultdict(int)
for a in A:
    D[a]+=1

S=sum(A)

Q = int(input())

for _ in range(Q):
    b,c = map(int,input().split())

    m = D[b]

    D[c]+=D[b]
    D[b]=0
    diff = (c-b)*m
    S+=diff
    print(S)


Measured memory_bytes: 89472
//
//  main.c
//  How Many Divisors?
//
//  Created by 曾億宜 on 2019/9/19.
//  Copyright © 2019 曾億宜. All rights reserved.
//

#include <stdio.h>

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



Measured memory_bytes: 2140
import itertools

n, m = map(int, input().split())

path = [[False] * n for i in range(n)]

# 頂点AからBにいく道はあるか？ vice versa 頂点BからAにいく道はあるか
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True


ans = 0

for i in itertools.permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break

            if not path[i[j]][i[j + 1]]:
                break

print(ans)



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
Int n,k,ans;
vector<vector<Int> > G;
vector<Int> dp,sz;
void dfs(Int v,Int p){
  if(~p&&G[v].size()==1u){
    dp[v]=0;
    sz[v]=1;
    return;
  }
  using P=pair<Int,int>;
  vector<P> d;
  Int c=0;
  priority_queue<P> q;
  for(Int u:G[v]){
    if(u==p) continue;
    dfs(u,v);
    sz[v]+=sz[u];
    d.emplace_back(dp[u],sz[u]>=k);
    q.emplace(dp[u]-(sz[u]>=k),-(sz[u]>=k));
    c+=d.back().second;
  }
  if(d.size()>=2){
    Int tmp=c;
    if(~p&&n-sz[v]>=k) tmp++;
    auto x=q.top();q.pop();
    auto y=q.top();q.pop();
    tmp+=x.first;
    tmp+=y.first;
    if(0){
      cout<<v<<":"<<c<<" DDD "<<tmp<<endl;
      cout<<x.first<<" "<<x.second<<endl;
      cout<<y.first<<" "<<y.second<<endl;
    }
    ans=max(ans,tmp);
  }
  for(Int i=0;i<(Int)d.size();i++){
    Int x=d[i].first,y=d[i].second;
    dp[v]=max(dp[v],x+c-y);
  }
  
  {
    Int tmp=dp[v];
    if(~p&&n-sz[v]>=k) tmp++;
    //cout<<v<<":"<<dp[v]<<" "<<tmp<<endl;
    ans=max(ans,tmp);
  }

  dp[v]=max(dp[v],c);
}
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin>>n>>k;
  G.resize(n);
  dp.resize(n,-1);
  sz.resize(n,1);
  for(Int i=0;i<n-1;i++){
    Int u,v;
    cin>>u>>v;
    u--;v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ans=0;
  dfs(0,-1);
  //for(Int i=0;i<n;i++) cout<<i<<":"<<dp[i]<<" AAA "<<sz[i]<<endl;
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 21100
n = input()
k = int(input())
dp = [[[0 for i in range(k+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(k+1):
      for i in range(10):
        if b ==1:
          if c ==k:  
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
          else:
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
            else:
              dp[a+1][1][c+1] += dp[a][1][c]
        else:
          if int(n[a]) > i:
            if c == k:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
              else:
                dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i:
            if c == k:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
              else:
                dp[a+1][0][c+1] += dp[a][0][c]
            
            
print(dp[-1][0][-1] + dp[-1][1][-1])
        

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    int A, B;
   
    int P[N], Q[N]; 
    for(int i = 0; i < N; i++) cin >> P[i];
    for(int i = 0; i < N; i++) cin >> Q[i];
    int data[N]; for(int i = 0; i < N; i++) data[i] = i+1;
   
    int pos = 1;
    do {
         for(int i = 0; i < N; i++){
            if (P[i] != data[i]) goto badP;
        }
        A = pos;
        badP:;
        for(int i = 0; i < N; i++){
            if (Q[i] != data[i]) goto badQ;
        }
        B = pos;
        badQ:;
        pos++;
 
    }while(next_permutation(data, data+N));
    cout << abs(A-B) << endl;
	return 0;
}
 


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

int main(){
  long long N , A , B ;
  cin >> N >> A >> B ;
  long long x = N/(A+B) ;
  long long y = N-x*(A+B) ;
  long long sum =0;
  if(A>=y) sum = y;
  else sum = A;
  
  cout << x*A+sum << endl;
 
}


Measured memory_bytes: 256
import itertools
import numpy as np

N, M, X = map(int, input().split())
C = []
H = []
for i in range(N):
    tmp = [int(x) for x in input().split()]
    H.append(tmp)

# print(H)

for i in range(2 ** N):
    cost = []
    for j in range(N):
        if bin(i).replace("0b", "").zfill(N)[j] == "1":
            cost.append(H[j])
            # combined1 = [x + y for (x, y) in zip(H[j], H[])]

    cost = np.array(cost)
    cost = cost.reshape(-1, M + 1)
    cost = np.sum(cost, axis=0)
    # print(cost.shape)
    C.append(list(cost))

# print(C)
result = []
for i in C:
    flag = True
    for j in range(M):
        if i[j + 1] >= X and flag:
            flag = True
        else:
            flag = False
    if flag:
        result.append(i[0])

if len(result) == 0:
    print(-1)
else:
    print(min(result))
# l = list(range(1, M + 1))
# hoge = itertools.combinations_with_replacement(l, N)
# for v in hoge:
#     print(v)


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

public class Hello
{
    public static void Main()
    {
        hoge();
        System.Console.ReadLine();
    }

    public static void hoge()
    {
        var vars = System.Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

        var x = vars[0];
        var k = vars[1];
        var d = vars[2];

        if(x == 0 && k % 2 == 0)
        {
            Console.WriteLine(0);
            return;
        }
        if (x == 0 && k % 2 == 1)
        {
            Console.WriteLine(d);
            return;
        }

        if(x < 0)
        {
            x = x * -1;
           
        }

        if (k <= x / d)
        {
            Console.WriteLine(x - k * d);
        }
        else
        {
            var div = x / d;
            var amari = x % d;
            var koshi = amari - d;
            if((k - div) % 2 == 1)
            {
                Console.WriteLine(koshi * -1);
            }
            else
            {
                Console.WriteLine(amari);
            }
        }
    }

}

Measured memory_bytes: 28184
import fractions
a,b,c,d = map(int, input().split())

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
cd = lcm(c,d)
dab = b -a

if a%c != 0:
  cf = a + (c - a%c)
else:
  cf = a
ce = b - (b%c)
if a%d != 0:
  df = a + (d - a%d)
else:
  df = a
de = b - (b%d)
if a%cd != 0:
  cdf = a + (cd - a%cd)
else:
  cdf = a
cde = b - (b%cd)
nc = (ce-cf + c )//c
nd = (de-df + d )//d
ncd = (cde-cdf + cd )//cd
print(dab-(nc+nd-ncd)+1)

Measured memory_bytes: 5076
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
 
/*---------------------------------------------------*/

int g[105][105];

void init(){
    rep(i,105){
        rep(j,105){
            if(i != j)g[i][j] = INF / 2;
            else g[i][j] = 0;
        }
    }
}

void wf(int n){
    rep(k, n){
        rep(i, n){
            rep(j, n){
                if(i != j)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

int main(){
    init();
    int n, m, a[1005], b[1005], c[1005];
    cin>> n >> m;
    rep(i,m){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        g[a[i]][b[i]] = c[i];
        g[b[i]][a[i]] = c[i];
    }
    wf(n);
    int cnt = m;
    rep(i, m){
        bool ok = false;
        rep(j, n){
            if(g[j][a[i]] + c[i] == g[j][b[i]]) ok = true;
        }
        if(ok)cnt--;
    }
    cout << cnt << endl;
    return 0;
}


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

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int a[]=new int[3];
		a[0]=sc.nextInt();
		a[1]=sc.nextInt();
		a[2]=sc.nextInt();
		int k=sc.nextInt();
		Arrays.sort(a);
		for(int i=0;i<k;i++)a[2]*=2;
		System.out.println(a[0]+a[1]+a[2]);

	}
}

Measured memory_bytes: 21076
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int a,b,c,d,e,temp;
    cin >> d >> e;
    
    a=d+e;
    b=d-e;
    c=d*e;
    
        if(a<b)
        {
            temp=a;
            a=b;
            b=temp;
        }

        if(a<c)
        {
            temp=a;
            a=c;
            c=temp;
        }

        if(b<c)
        {
            temp=b;
            b=c;
            c=temp;
        }
        
        cout << a << endl;

    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
using namespace std;
 
int main() {
  string S;
  ll K;
  cin >> S >> K;

  for(ll i = 0; i < K; i++) {
    if(S.at(i) != '1') {
      cout << S.at(i) << endl;
      break;
    }
    if(i == K - 1) cout << 1 << endl;
  }
}


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];

    }
    sort(all(v));

    vector<P> q(m);
    for(int i = 0; i < m; ++i) {
        cin >> q[i].S >> q[i].F;
        
    }
    sort(all(q), greater<P>());

    int pos = 0;
    int qpos = 0;
    while(pos < n && qpos < m) {
        while(pos < n && q[qpos].S > 0) {
            if(v[pos] >= q[qpos].F) {
                ++pos;
                break;
            }
            v[pos] = q[qpos].F;
            ++pos;
            --q[qpos].S;

        }
        ++qpos;

    }
    
    LL res = 0;
    for(int i = 0; i < n; ++i) {
        res += v[i];

    }
    cout << res << endl;
    return 0;
}



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

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

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (long long)1e18 + 1;

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

    ll N, H;
    std::cin >> N >> H;

    vector<ll> a(N), b(N);
    REP(i, N) {
        std::cin >> a[i] >> b[i];
    }

    RSORT(b);

    ll max_a = *max_element(ALL(a));
    ll ans   = 0;
    REP(i, N) {
        if(max_a < b[i] && H != 0) {
            H = max(H - b[i], 0LL);
            ans++;
        }
        if(H == 0) break;
    }

    std::cout << (ll)(ans + ceil(H / (double)max_a)) << std::endl;

    return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>
#define mkp make_pair

struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

int main() {
  int N, M; cin >> N >> M;
  dsu d(N);
  rep(i, M){
    int a, b; cin >> a >> b;
    a--; b--;
    d.merge(a, b);
  }


  set<int> s;
  rep(i, N){
    s.insert(d.leader(i));
  }
  cout << s.size() - 1 << endl;
}

Measured memory_bytes: 7656
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ld, ld> P;
typedef vector<ld> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll a;
    ld b;
    cin>>a>>b;
    cout<<(ll)(a*b+0.0001)<<endl;
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main()
{
	int v,n;
	cin>>v>>n;
	if(n==0)
	cout<<v<<endl;
	else{
	for(int i=0;i<n;i++)
	{
		int x; cin>>x;
		mp[x]=1;
	}
	
	for(int i=0;i<=n;i++)
	{
		if(mp[v-i]==0)
		{
			cout<<v-i<<endl;
			break;
		}
		if(mp[v+i]==0)
		{
			cout<<v+i<<endl;
			break;
		}
	}
}
	return 0;
	
}

Measured memory_bytes: 3640
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
	long long int n;
	cin >> n;
	cout << 180 * (n - 2) << endl;
	return 0;
}

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

namespace GcdLcm {
     class Program {
          
          static long gcd(long a, long b) {//最大公約数
               if(b == 0) {
                    return a;
               }
               else {
                    return gcd(b, a % b);
               }
          }

          static long lcm(long c, long d) {//最小公倍数
               long g = gcd(c, d);
               return c / g * d;
          }
          public static void Main() {
               int N = int.Parse(Console.ReadLine());
               long[] Num = new long[N];


               for(int x = 0; x < N; x++) {
                    string input = Console.ReadLine();
                    Num[x] = long.Parse(input);
               }
               long ans = 1;

               for(int y = 0; y < N; y++) {
                    ans = lcm(ans, Num[y]);
               }
               Console.WriteLine(ans);


          }
     }

}



Measured memory_bytes: 13140
#include <cstdio>
#include <vector>
#include <algorithm>

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

	char* map[101];
	for (int i = 0; i < 101; i++) {
		map[i] = new char[N + 1];
		map[i][0] = 0;
	}

	int tmp;
	for (int i = 1; i < N + 1; i++) {
		scanf("%d", &tmp);
		for (int j = 0; j < 101; j++) {
			if (j < tmp)
				map[j][i] = 1;
			else 
				map[j][i] = 0;
		}

	}

	int count = 0;
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0 && map[i][j + 1] == 1) count++;
		}
	}

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

	return 0;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

ll N;

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

  std::cin >> N;

  ll res = (N - 1) * N / 2;
  std::cout << res << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define x first
#define y second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define newline cout<<"\n"
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
#define INF (int)1e5
#define nax (ll)2e5+3
#define eps (double)1e-9
#define all(x) x.begin(),x.end()
 
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> pdbs;
// look for  all edge cases
//search for a pattern




int main(){
	fast;
	int n,m;
	cin >> n >> m;
	vector<ll> v(n);
	ll sum = 0;
	for(int i =0 ; i< m;i++){
		cin >> v[i];
		sum += v[i];
	}
	if(sum > n){
		cout<<-1;
	}
	else{
		cout<<n - sum;
	}
	return 0;
}

	


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

const int MAXN = 60;
std::vector<int> A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int fa[MAXN], n;
void dfs(int u) { for (int i : A[u]) if (i != fa[u]) fa[i] = u, dfs(i); }
int mark[MAXN];
void dfs1(int u, int fa = 0) {
	for (int i : C[u]) if (i != fa)
		mark[u] || mark[i] ? 0 : (D[i].push_back(u), 0), dfs1(i, u);
}
void dfs2(int u, int fa = 0) {
	for (int i : B[u]) if (i != fa)
		mark[u] || mark[i] ? 0 : (D[u].push_back(i), 0), dfs2(i, u);
}
inline bool lb(const std::vector<int> & x, int v) {
	auto at = std::lower_bound(x.begin(), x.end(), v);
	return at != x.end() && *at == v;
}
void dfs3(int u, int fa = 0) {
	mark[u] = true; for (int i : B[u]) if (lb(C[u], i) && i != fa) dfs3(i, u);
}
int ind[MAXN];
std::queue<int> q;
int solve(int rt) {
	for (int i = 1; i <= n; ++i) C[i].clear(), D[i].clear();
	std::fill(ind + 1, ind + 1 + n, 0);
	std::fill(mark + 1, mark + 1 + n, 0);
	for (int i = 1; i <= n; ++i) if (fa[i]) {
		C[fa[i]].push_back(i);
		C[i].push_back(fa[i]);
	}
	for (int i = 1; i <= n; ++i) std::sort(C[i].begin(), C[i].end());
	dfs3(rt); dfs1(rt); dfs2(rt);
	for (int i = 1; i <= n; ++i) for (auto j : D[i]) ++ind[j];
	for (int i = 1; i <= n; ++i) if (ind[i] == 0) q.push(i);
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (auto i : D[t]) if (!--ind[i]) q.push(i);
	}
	int res = n - std::accumulate(mark + 1, mark + 1 + n, 0);
	return *std::max_element(ind + 1, ind + 1 + n) ? n + 1 : res;
}
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	int T; std::cin >> T;
	while (T --> 0) {
		std::cin >> n;
		for (int i = 1, t1, t2; i < n; ++i) {
			std::cin >> t1 >> t2;
			A[t1].push_back(t2);
			A[t2].push_back(t1);
		}
		for (int i = 1, t1, t2; i < n; ++i) {
			std::cin >> t1 >> t2;
			B[t1].push_back(t2);
			B[t2].push_back(t1);
		}
		for (int i = 1; i <= n; ++i) std::sort(A[i].begin(), A[i].end());
		for (int i = 1; i <= n; ++i) std::sort(B[i].begin(), B[i].end());
		bool can = true;
		for (int i = 1; i <= n; ++i) can &= A[i] == B[i];
		int ans = n + 1;
		if (can) ans = 0;
		else {
			int rt = 0;
			for (int i = 1; i <= n; ++i) if (A[i].size() > 1) rt = i;
			assert(rt);
			fa[rt] = 0; dfs(rt);
			for (int i = 1; i <= n; ++i) 
				ans = std::min(ans, solve(i));
			for (int i = 1; i <= n; ++i) if (A[i].size() == 1) {
				int s = fa[i];
				for (int j = 1; j <= n; ++j) if (j != i)
					fa[i] = j, ans = std::min(ans, solve(i) + 1);
				fa[i] = s;
			}
		}
		std::cout << (ans == n + 1 ? -1 : ans) << '\n';
		for (int i = 1; i <= n; ++i) A[i].clear(), B[i].clear();
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdint>

using namespace std;

template <class T, class Updater, class Aggregator>
class LazySegmentTree {
    size_t n, m;
    vector<T> tree, buf;
    vector<bool> buffering;
    Updater update;
    Aggregator aggregate;
    const T e;
    void buffer(size_t i, T x) {
        buffering[i] = true;
        buf[i] = update(buf[i], x);
        tree[i] = update(buf[i], x);
    }
    void propagate(size_t i) {
        if (!buffering[i]) return;

        buffer(i<<1|0, buf[i]);
        buffer(i<<1|1, buf[i]);
        buf[i] = e;
        buffering[i] = false;
    }
    void modify(size_t l, size_t r, const T &x, size_t i, size_t a, size_t b) {
        if (r <= a || b <= l) return;
        if (l <= a && b <= r) {
            buffer(i, x);
            return;
        }
        propagate(i);

        size_t c=(a+b)>>1;
        modify(l, r, x, i<<1|0, a, c);
        modify(l, r, x, i<<1|1, c, b);
        tree[i] = aggregate(tree[i<<1|0], tree[i<<1|1]);
    }
    T query(size_t l, size_t r, size_t i, size_t a, size_t b) {
        if (r <= a || b <= l) return e;
        if (l <= a && b <= r) return tree[i];

        propagate(i);
        size_t c=(a+b)>>1;
        T vl=query(l, r, i<<1|0, a, c);
        T vr=query(l, r, i<<1|1, c, b);

        return aggregate(vl, vr);
    }
public:
    LazySegmentTree(size_t m, T e=T()): n(1), m(m), e(e) {
        while (n < m) n <<= 1;

        tree.assign(n<<1, e);
        buf.assign(n<<1, e);
        buffering.assign(n<<1, false);
    }
    void modify(size_t l, size_t r, const T &x) {
        modify(l, r, x, 1, 0, n);
    }
    T query(size_t l, size_t r) {
        return query(l, r, 1, 0, n);
    }
};

template <class T>
struct Updater {
    T operator ()(const T &lhs, const T &rhs) {
        return rhs;
    }
};

template <class T>
struct Min {
    T operator ()(const T &lhs, const T &rhs) {
        return min(lhs, rhs);
    }
};

int main() {
    size_t n;
    int q;
    scanf("%zu %d\n", &n, &q);

    int64_t e=(1LL<<31)-1;
    LazySegmentTree<int64_t, Updater<int64_t>, Min<int64_t>> tree(n, e);
    for (int i=0; i<q; ++i) {
        int query;
        scanf("%d", &query);

        if (query == 0) {
                size_t s, t;
                int64_t x;
                scanf("%zu %zu %lld", &s, &t, &x);
                tree.modify(s, t+1, x);
        } else if (query == 1) {
                size_t s, t;
                scanf("%zu %zu", &s, &t);
                printf("%lld\n", tree.query(s, t+1));
        } else {
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 6632
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {

    // ここから入力
    
    ll a,b,ans = 0;
    cin >> a >> b;
    
    while(a <= b){
        ans++;
        a *= 2;
    }
    
    cout << ans << endl;

}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    string s;cin>>s;
    if(s=="Sunny")cout<<"Cloudy\n";
    else if(s=="Cloudy")cout<<"Rainy\n";
    else cout<<"Sunny\n";
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

int main()
{
    int N; cin >> N;
    ll R[N];
    for(int i=0; i<N; i++){
        ll Ri; cin >> Ri;
        R[i] = Ri;
    }
    ll maxv = (-1)*pow(10,10);
    ll minv = pow(10, 10);  
    for(int i=0; i<N; i++){
        maxv = max(maxv, R[i]-minv);
        minv = min(minv, R[i]);
    } 
    cout << maxv << endl;
}


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

int main(){
  int h[5];
  int hm[5];
  int totime;
  for (int i =0;i<5;i++) cin >> h[i];

  for (int i =0;i<5;i++){
    hm[i] = h[i] % 10;
    if (hm[i] == 0){
      hm[i] += 10;
    }
    totime += h[i]-hm[i]+10;
    hm[i] = 10 - hm[i];
  }
  totime -= *max_element(hm,hm+5);
  cout << totime;
  
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>

using namespace std;

const int MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;
#define rep(i, m, n) for(int i=m;i<n;i++)
#define rrep(i, n, m) for(int i=n;i>=m;i--)

int main() {
    ll N;
    cin >> N;
    ll S = 0;
    string tmp = to_string(N);
    for (int i = 0; i < tmp.length(); ++i) {
        S += tmp[i] - '0';
    }
    if (N % S == 0) {
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main() {
  //入力
  string S;
  cin>>S;
  int len=S.length();
  long long temp=0;
  long long totalans=0;
  //bit全探索
  for(int i=0;i<(1 <<(len-1));i++){
    temp=0;
    for(int j=0;j<len;j++){
      temp=temp*10;
      temp+=S.at(j)-'0';
      if(i&(1<<j)){
        //cout<<"###"<<temp<<endl;
        totalans+=temp;
        temp=0;
      }
    }
    //cout<<"#"<<temp<<endl;
    totalans+=temp;
  }
  
  cout<<totalans<<endl;
  return 0;       
}

Measured memory_bytes: 3572
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define all(v) ((v).begin()),((v).end())
#define PI(n) ((double)acos(n))
int dx8[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy8[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen ( "in.txt", "r", stdin );
	//freopen("out.txt", "w", stdout);
#else
	// online submission
#endif
}
void fast() {
	std::ios_base::sync_with_stdio ( 0 );
	cin.tie ( NULL );
	cout.tie ( NULL );
}
vector<vector<int>> gh ( 1e5 + 1 );
int vis[100001];
int cnt = 0;
bool ff = 0;
int n;
vector<int> bfs2 ( int st ) {
	queue<int>q;
	vector<int>len ( 100001, 100005 ); // intialize be infinte
	q.push ( { st } );
	len[st] = 0;
	int dep = 0;
	while ( !q.empty() ) {
		dep++;
		int sz = q.size();
		while ( sz-- ) {
			int node = q.front();
			q.pop();
			for ( int i = 0; i < gh[node].size(); i++ ) {
				int nxtnode = gh[node][i];
				if ( len[nxtnode] == 100005 ) {
					len[nxtnode] = dep;
					q.push ( nxtnode );
				}
			}
		}
	}
	return len;
}
int main() {
	fast();
	cin >> n;
	for ( int i = 0; i < n - 1; i++ ) {
		int u, v;
		cin >> u >> v;
		gh[u].push_back ( v );
		gh[v].push_back ( u );
	}
	vector<int>v1, v2;
	v1 = bfs2 ( 1 );
	v2 = bfs2 ( n );
	int c1 = 0, c2 = 0;
	for ( int i = 2; i < n; i++ ) {
		if ( v1[i] <= v2[i] )
			c1++;
		else c2++;
	}
	if ( c1 > c2 )
		cout << "Fennec" << endl;
	else cout << "Snuke" << endl;
}


Measured memory_bytes: 6656
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut v: Vec<f64> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();
    v.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{}", v.iter().fold(v[0], |acc, &x| (acc + x) / 2.0));
}


Measured memory_bytes: 2168
#include<stdio.h>
int main()
{
    int n,i,d,j,s=0;

    scanf("%d",&n);

    for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
        {
            if(i*j==n) s++;

            else continue;

        }
    }

     if(s>=1) printf("Yes\n");

     else printf("No\n");


return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int n;
    cin >> n;
    n = n%10;
    if(n==2||n==4||n==5||n==7||n==9)    printf("hon");
    if(n==0||n==1||n==6||n==8)    printf("pon");
    if(n==3)    printf("bon");
    return 0;
}

Measured memory_bytes: 3688
from sys import stdin

n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
b = [int(x) for x in stdin.readline().rstrip().split()]
c = [int(x) for x in stdin.readline().rstrip().split()]

score = 0
ex = 0
for i in a:
    score += b[i-1]
    if ex != 0 and i == ex+1:
        score += c[ex-1]
    ex = i

print(score)



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


long long a[2*100000+1]={};
long long dp( long long j){
	if(j<=0){
		return 0;
	}		
	if(a[j]){
		return a[j];
	}else{
		return a[j]=dp(j-1)+j;
	}
}
		



int main(){
	long long n,k;
	cin>>n>>k;
	long long ans=0;
	for(long long i=k;i<=n+1;i++){
		long long  o=0,e=0;
		o+=dp(i-1);
		e+=dp(n)-dp(n-i);
		//cout<<i<<" "<<o<<" "<<e<<endl;
		ans+=(e-o+1)%1000000007;
		ans=ans%1000000007;
	}
	cout<<ans<<endl;
	//for(int i=0;i<10;i++){
	//	cout<<a[i]<<endl;
	//}
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

ll dp[2020][2020];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    dp[0][0] = 0;

    ll N, M;
    cin >> N >> M;
    vector<ll> S(N), T(M);
    REP(i, N) cin >> S[i];
    REP(i, M) cin >> T[i];

    REP(i, N+1){
    	REP(j, M+1){
    		if(i<N){
    			dp[i+1][j] += dp[i][j];
    			dp[i+1][j] %= mod;
    		}
    		if(j<M){
    			dp[i][j+1] += dp[i][j];
    			dp[i][j+1] %= mod;
    		}
    		if(i<N && j<M){
                if(S[i]!=T[j]){
                    dp[i+1][j+1] -= dp[i][j];
                }else{
                    dp[i+1][j+1] ++;
                }
                dp[i+1][j+1] += mod;
                dp[i+1][j+1] %= mod;
    		}
    	}
    }

    /*
    REP(i, N+1){
    	REP(j, M+1){
    		cout << dp[i][j] << " ";
    	}
    	cout << endl;
    }
    */
    
    cout << dp[N][M]+1 << endl;
    return 0;
}

Measured memory_bytes: 31872
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long LL;

LL n, a[20];
unordered_map<LL,LL> dp; 

LL dfs(int l,int r,LL xl,LL xr){
	if(l+1==r) return 0ll;
	LL k = (xl<<30)+(xr<<10)+(l<<5)+r;
	if(dp[k]) return dp[k];
	dp[k] = 1ll<<55;
	rep(i,l+1,r-1) dp[k] = min(dp[k], dfs(l,i,xl,xl+xr) + dfs(i,r,xl+xr,xr) + a[i]*(xl+xr) );
	return dp[k];
}

int main(){
	cin>>n;
	rep(i,1,n)cin>>a[i];
	cout<<dfs(1,n,1,1)+a[1]+a[n]<<endl;
	return 0;
}

Measured memory_bytes: 14280
import sys
sys.setrecursionlimit(10**6)


N = int(input())
#頂点iのindexは[i-1]
tree = []
for i in range(N):
    tree.append([])

#Wが0なら偶数、1なら奇数
for i in range(N-1):
    u, v, w = map(int,input().split())
    tree[v-1].append([u-1,w % 2])
    tree[u-1].append([v-1,w % 2])
    
#print(tree)

    
color = []
for i in range(N):
    color.append(0)
    color[0] = 1
#白=-1、黒=1、無色=0

distance = 0

def poyo(x):
    global tree
    global color
    for i in tree[x]:#その頂点から行ける頂点を一覧
        if color[i[0]] == 0:#iもリスト([0]が行ける頂点、[1]が距離)
            if i[1] == 0:
                color[i[0]] = color[x]
            else:
                color[i[0]] = color[x] * (-1)
            
            poyo(i[0])


poyo(0)

for i in color:
    if i == -1:
        i = 0
        
    print(i)







Measured memory_bytes: 82344
#include<iostream>
using namespace std;
int main(){
long long a;
long long b;
long long c;
cin>>a>>b>>c;
if(c>=(a+b))cout<<"0"<<" "<<"0"<<endl;
else {
  if(c>=a)cout<<"0"<<" "<<(a+b)-c<<endl;
  else  cout<<a-c<<" "<<b<<endl;
}

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
int main(){
    std::string s[3];
    for(int i = 0; i < 3; i++){
        std::cin >> s[i];
    }
    std::cout << s[0][0] << s[1][0] << s[2][0] << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
using namespace std;
typedef pair<int, int> P;

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

typedef long long ll;
typedef vector<int> VI;


int A[2000010];
int C[10100];
int B[2000010];
int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n; cin >> n;
    int k=0;
    for(int i=0; i<n; ++i){
        cin >> A[i];
        k = max(k, A[i]);
    }
    for(int i=0; i<10001; ++i) C[i]=0;
    
    for(int i=0; i<n; ++i) C[A[i]]++;
    
    for(int i=1; i<10001; ++i) C[i] = C[i]+C[i-1];
    
    for(int i=n-1; i>=0; --i){
        B[C[A[i]]-1] = A[i];
        C[A[i]]--; 
    }
    for(int i=0; i<n; ++i){
        if(i) cout << " ";
        cout << B[i];
    }
    cout << endl;
	return 0;
}


Measured memory_bytes: 18788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_v=1e9;
int main(){
  ll s;
  cin>>s;
  if(s==(ll)1e18){
    cout<<0<<" "<<0<<" "<<max_v<<" "<<0<<" "<<0<<" "<<max_v<<endl;
    return 0;
  }
  cout<<0<<" "<<0<<" ";
  cout<<max_v<<" "<<1<<" ";
  cout<<(max_v-(s%max_v))<<" "<<(s/max_v)+1<<endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n);
  rep(i, n) scanf("%d", &a[i]);
  rep(i, n) scanf("%d", &b[i]);
  rep(i, n) scanf("%d", &c[i]);
 
  sort(a.begin(), a.end());
  sort(c.begin(), c.end());
  ll ans = 0;
  rep(i, n) {
    ll x = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
    ll y = upper_bound(c.begin(), c.end(), b[i]) - c.begin();
	y = n - y;
	ans += x * y;
  }
  printf("%lld\n", ans);
}


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

typedef unsigned long long uLL;
typedef long long int LL;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
typedef pair <long long,long long> pll;
typedef pair <long long,pll> plll;
const int N = 1e5 + 5;
const int inf = 1e9;
const long long INF = 1e18;
const double PI = acos(-1.0);
const double EPS = 1e-8;
const int MOD = 1000000007;

string a, b;
int la , lb;
int dp[ 3001 ][ 3001 ];

int solve( int i , int j ) {
        if( i >= la || j >= lb ) return 0;
        if( dp[i][j] != -1 ) return dp[i][j];
        if( a[i] == b[j] ) return 1 + solve( i + 1 , j + 1 );
        return dp[i][j] = max( solve( i + 1 , j ) , solve( i , j + 1 ) );
}
void print( int i, int j ) {
        if( i >= la ||j >= lb ) return;
        if( a[i] == b[j] ) {
                cout << a[i];
                print( i + 1 , j + 1 );
        }
        else {
                if( solve( i + 1 , j ) >= solve( i , j + 1 ) ) print( i + 1 , j );
                else print( i , j + 1 );
        }
}
int main( int argc , char const *argv[] ) {
        ios_base::sync_with_stdio( false ); cin.tie( NULL );
        cin >> a >> b;
        la = a.size();
        lb = b.size();
        memset( dp , -1 , sizeof( dp ) );
        solve( 0 , 0 );
        print( 0 , 0 );
        return 0;
}













Measured memory_bytes: 35968
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1e9 + 100;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = 20;
int n, m;
char s[maxn][maxn];

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  memset(s, 0, sizeof(s));
  for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);
  }
  return true;
}

bool used[maxn][maxn];

void solve() {
  memset(used, 0, sizeof(used));
  int x = 0, y = 0;
  used[n - 1][m - 1] = 1;
  while (x != n - 1 || y != m - 1) {
    bool ok = false;
    used[x][y] = 1;
    if (s[x + 1][y] == '#') {
      x++;
      ok = true;
      continue;
    }
    if (s[x][y + 1] == '#') {
      y++;
      ok = true;
      continue;
    }
    if (!ok) {
      printf("Impossible\n");
      return;
    }
  }
  bool ok = true;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (s[i][j] == '#' && !used[i][j]) {
        ok = false;
      }
    }
  }
  printf(ok ? "Possible\n" : "Impossible\n");
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (true) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time: %.18f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

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

using namespace std;

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

	bool fA = false;
	bool fB = false;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] == 'A') {
			fA = true;
		}
		else if (S[i] == 'B') {
			fB = true;
		}
	}

	if (fA && fB) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}





Measured memory_bytes: 3632
<?php
# 入力部
// fscanf(STDIN, "%s %s", $s, $t);
// fscanf(STDIN, "%d %d", $n, $m);
// fscanf(STDIN, "%s", $u);
// fscanf(STDIN, "%d %d", $k, $x);
// $s1 = fgets(STDIN); //"\n"の2文字
// $s2 = fgets(STDIN);
// fscanf(STDIN, "%d", $r);
fscanf(STDIN, "%f", $n);
// fscanf(STDIN, "%s", $s);
// fscanf(STDIN, "%c", $c);
// fscanf(STDIN, "%s", $s2);
// fscanf(STDIN, "%d %d %d", $a, $b, $c);


# 処理部
// $arr = str_split($s);
// $arr2 = str_split($s2);
// $arr1 = explode(" ", $s1);
// $arr2 = explode(" ", $s2);
// for ($i = 0; $n > $x * $i; $i++) {
// }
// if (strpos($s, 'RRR') !== false) {
//   $r = 3;
// } elseif (strpos($s, 'RR') !== false) {
//   $r = 2;
// } elseif (strpos($s, 'R') !== false) {
//   $r = 1;
// } else {
//   $r = 0;
// }
// $s = "No";
// if ($x >= 30) {
//   $s = "Yes";
// }
// for ($i = 0; $i * 1000 < $n; $i++) {
// }
// $c = "a";
// if (ctype_upper($a)) {
//   $c = "A";
// }
// $s = "Yes";
// echo count($arr1);
// for ($i = 0; $i < strlen($s1); $i++) {
//   if ($arr1[$i] != $arr2[$i]) {
//     $s = "No";
//   }
// }
// $unit;
// switch ($n % 10) {
//   case 0:
//   case 1:
//   case 6:
//   case 8:
//     $unit = "pon";
//     break;
//   case 3:
//     $unit = "bon";
//     break;
//   default:
//     $unit = "hon";
//     break;
// }
// if ($s == "ABC") {
//   $r = "ARC";
// } else {
//   $r = "ABC";
// }
// $r = "NG";
// $arr = array("SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN");
// for ($i = 0; $i <= count($arr); $i++) {
//   if ($arr[$i] == $s) {
//     break;
//   }
// }
// $r = "safe";
// if ($s <= $w) {
//   $r = "unsafe";
// }
// $r = "No";
// if (strpos($n, "7") !== false) {
//   $r = "Yes";
// }
// $r = "No";
// if ($arr[2] == $arr[3] && $arr[4] == $arr[5]) {
//   $r = "Yes";
// }
// $r = "Yes";
// if ($s == "AAA" || $s == "BBB") {
//   $r = "No";
// }
if ($n % 2 == 0) {
  $r = $n / 2 / $n;
} else {
  $r = ($n + 1) / 2 / $n;
}
// if ($n < 10) {
//   $r += (10 - $n) * 100;
// }
// $arr = array($a, $b, $c);
// $arr = array_unique($arr);
// if (count($arr) == 2) {
//   $r = "Yes";
// } else {
//   $r = "No";
// }
// if ($s == $u) {
//   $a--;
// } else {
//   $b--;
// }
// for ($i = 0; $h > 0; $i++) {
//   $h -= $a;
// }
// $r = "No";
// if ($n == $m) {
//   $r = "Yes";
// }
// $r = "win";
// if ($a + $b + $c >= 22) {
//   $r = "bust
// ";
// }
// $arr = array(1, 2, 3);
// unset($arr[$a - 1]);
// unset($arr[$b - 1]);
// $arr = array_values($arr);
// if ($n < 10 && $m < 10) {
//   $r = $n * $m;
// } else {
//   $r = -1;
// }

# 出力部
// echo ($n * ($n - 1) / 2) + ($m * ($m - 1) / 2) . "\n";
// echo $z . " " . $x . " " . $y . "\n";
// echo ($i * 1000) - $n . "\n";
// echo json_encode($arr) . "\n";
// echo $arr[0] . "\n";
// echo $i + 1 . "\n";
echo $r . "\n";
// echo ++$c . "\n";
// echo $a . " " . $b . "\n";
// echo $t . $s . "\n";


Measured memory_bytes: 16132
def LI():
    return list(map(int, input().split()))


mod = pow(10, 9)+7
N = int(input())
if N < 3:
    ans = 0
else:
    a = N//3
    ans = 1
    for i in range(2, a+1):
        n = N-3*i+1
        r = i-1
        n = n+r-1
        bunshi = 1
        bunbo = 1
        for j in range(r):
            bunshi = (bunshi*(n-j)) % mod
            bunbo = (bunbo*(j+1)) % mod
        ans = (ans+(bunshi*pow(bunbo, -1, mod))) % mod
print(ans)

Measured memory_bytes: 9128
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
template <typename T> using V = vector<T>;

template <typename T>
struct SegTree {
    V<T> segs;
    function<T(T, T)> merge;
    T id_ele;
    ll upper;

    SegTree(const V<T> &segs_arg, function<T(T, T)> merge, T id_ele) : merge(merge), id_ele(id_ele) {
        size_t seg_size = 1;
        while(seg_size < segs_arg.size()) seg_size <<= 1;
        seg_size <<= 1;
        upper = seg_size / 2;
        seg_size--;
        segs.resize(seg_size, id_ele);
        for(size_t i = 0; i < segs_arg.size(); i++) segs[i + seg_size / 2] = segs_arg[i];
        for(ssize_t i = seg_size / 2 - 1; 0 <= i; i--) segs[i] = merge(segs[2 * i + 1], segs[2 * i + 2]);
    }

    T get_query(ll ql, ll qr, size_t idx, ll nl, ll nr) {
        if(nr <= ql || qr <= nl) return id_ele;
        if(ql <= nl && nr <= qr) {
            return segs[idx];
        }
        auto mid = (nl + nr) / 2;
        T l = get_query(ql, qr, 2 * idx + 1, nl, mid);
        T r = get_query(ql, qr, 2 * idx + 2, mid, nr);
        return merge(l, r);
    }

    T get_query(ll ql, ll qr) {
        return get_query(ql, qr, 0, 0, upper);
    }

    void update_query(ll idx, T val) {
        idx += upper - 1;
        segs[idx] = val;
        while(idx) {
            ll pidx = (idx - 1) / 2;
            segs[pidx] = merge(segs[2 * pidx + 1], segs[2 * pidx + 2]);
            idx = pidx;
        }
    }
};

int main() {
    ll N, Q;
    cin >> N >> Q;
    V<ll> init_v(N);
    SegTree<ll> st(init_v, [](ll a, ll b) { return a + b; }, 0);
    while(Q--) {
        ll com;
        cin >> com;
        if(com == 0) {
            ll i, x;
            cin >> i >> x;
            i--;
            init_v[i] += x;
            st.update_query(i, init_v[i]);
        } else {
            ll s, t;
            cin >> s >> t;
            s--;
            cout << st.get_query(s, t) << endl;
        }
    }
    return 0;
}



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

int main(){

	int n,q;
	cin >> n;
	int* S = new int[n];
	for (int i = 0; i < n; i++) cin >> S[i];
	cin >> q;
	int* T = new int[q];
	for (int i = 0; i < q; i++) cin >> T[i];

	int count = 0;
	for (int i = 0; i < q; i++){
		for (int j = 0; j < n; j++){
			if (S[j] == T[i]){
				count++;
				break;
			}
		}
	}

	cout << count << endl;

	delete[] S;
	delete[] T;
		
	return 0;
}


Measured memory_bytes: 3132