akhauriyash/Code-Regression huggingface dataset:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

amax = sum(a)
bmax = sum(b)

# dp[i][j][k]: 薬品iまで見て，Aがjグラム，Bがkグラムの最小予算
dp = [[[5000]*(bmax+1) for _ in range(amax+1)] for _ in range(N)]
dp[0][a[0]][b[0]] = c[0]
dp[0][0][0] = 0
for i in range(1,N):
    for j in range(amax+1):
        for k in range(bmax+1):
            if j == k == 0:
                dp[i][j][k] = 0
            elif j-a[i] < 0 or k-b[i] < 0:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i]][k-b[i]]+c[i])

ans = 5000
now = 1
while True:
    if Ma*now <= amax and Mb*now <= bmax:
        if dp[N-1][Ma*now][Mb*now] < ans:
            ans = dp[N-1][Ma*now][Mb*now]
        now += 1
    else:
        break

if ans == 5000:
    print('-1')
else:
    print(ans)

Measured memory_bytes: 63452
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
k = INT()
x_l = LIST()

ans = 0
for x in x_l:
    ans += min(abs(x), abs(x-k))

print(ans*2)

Measured memory_bytes: 6096
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define ll          unsigned long long int

#define pb          push_back
#define pii         pair<int,int>
#define F           first
#define S           second
#define vi          vector<int>
#define vli          vector<ll>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define M_PI        3.14159265358979323846
#define mp          make_pair
#define sz(x)       (int)x.size()
#define matrix      vector<vector<ll>>
#define forn(i,a,b)  for(int i=a;i<b;i++)
#define eps 0.0000000001
#define all(a)      (a).begin(),(a).end()
#define ordered_set     tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 
 
const long long INF = (long long) 1e11+1;
const long long mod = (long long) 998244353;
const long long hell = (long long) 1000000007;

ll power(ll x,ll y)
{
  ll res=1;
  while(y>0){
    if(y%2) res=(x*res);
    x=(x*x);    
    y=y/2;
  }
  
  return res%mod;
}
 
ll modinv(ll x){
  return power(x,hell-2);
}

ll gcd(ll a,ll b)
{
    while( b != 0)
	{
		ll  t = b;
		b= a %t;
		a = t;
	}
	return a;
}

void fastIO() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}


void solve(){
    int n;
    cin>>n;
    n=n%10;
    
    if(n==3){
        cout<<"bon";
    }
    else if(n==0 or n==1 or n==6 or n==8){
        cout<<"pon";
    }else
    cout<<"hon";
}

int main(){
   fastIO();
   int test;
   //cin>>test;
   test=1;    
   
   while(test--)
   solve();
}


Measured memory_bytes: 3640
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	k := nextInt()

	run := 0
	for i := 0; i < n; i++ {
		x := nextInt()
		run += 2 * min(x, k-x)
	}

	fmt.Println(run)

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

// ---- readfunc
func scanInit() {
	const cap = 64 * 1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1776
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int A, B;
    cin >> A >> B;
    if (A % 2 != 0 && B % 2 != 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>

using namespace std;

int main(){

    string S;
    cin >> S;

    for (int i = 0; i < 4; i++){
        cout<< S[i];
    }
    cout << " ";
    for (int i = 4; i < 12; i++){
        cout << S[i];
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
vi seg;
ll N;
void init(vi v){
    N=1;
    while(N<v.size())N*=2;
    seg=vi(N*2-1);
    rep(i,v.size())seg[i+N-1]=v[i];
    for(int i=N-2;i>=0;i--)seg[i]=seg[i*2+1]+seg[i*2+2];
}
void add(ll i,ll x){
    i=N+i-1;
    seg[i]+=x;
    while(i>0){
        i=(i-1)/2;
        seg[i]=seg[i*2+1]+seg[i*2+2];
    }
}
ll getsum(ll a,ll b,ll k,ll l,ll r){
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return seg[k];
    ll c1=getsum(a,b,k*2+1,l,(l+r)/2);
    ll c2=getsum(a,b,k*2+2,(l+r)/2,r);
    return c1+c2;
}
int main(){
    ll n,q;cin>>n>>q;
    vi v(n);
    rep(i,n)cin>>v[i];
    init(v);
    rep(i,q){
        ll t,a,b;cin>>t>>a>>b;
        if(t)out(getsum(a,b,0,0,N));
        else add(a,b);
    }
}

Measured memory_bytes: 19344
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
	int N; cin >> N;
	vector<int> a(N),b(N);
	rep(i,N){
		cin >> a[i];
	}
	rep(i,N){
		cin >> b[i];
	}
	ll suma = 0;
	ll sumb = 0;
	rep(i,N){
		if(a[i] > b[i]) sumb += a[i]-b[i];
		if(b[i]-a[i] >= 2) suma += (b[i]-a[i])/2;
	}
	cout << (suma >= sumb ? "Yes" : "No") << endl;

}

Measured memory_bytes: 384
N, M = map(int, input().split())

Pref = [[]for _ in range(N)]

City = []

for _ in range(M):
    prefecture, year = map(int, input().split())
    prefecture -= 1
    Pref[prefecture].append([_, year])

for i in range(N):
    Pref[i].sort(key=lambda x: x[1])
    for j in range(len(Pref[i])):
        s1 = str(i+1).zfill(6)
        s2 = str(j+1).zfill(6)
        Pref[i][j].append(s1+s2)
        City.append(Pref[i][j])
City.sort()
for a, b, c in City:
    print(c)



Measured memory_bytes: 96544
n = int(input())
dict = {}
command = [(input().split()) for i in range(n)]
for c in command:
    if(c[0] == "insert"):
        dict[c[1]] = 1
    elif(c[0] == "find"):
        if(c[1] in dict):
            print('yes')
        else:
            print('no')



Measured memory_bytes: 303804
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int a,b;
    cin >> a >> b;
    cout << 6 - a - b << endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
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; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  string s; cin >> s;
  map<char,int> m;
  for(char c: s) {
    m[c]++;
  }

  int ok = true;
  for(char c: s) if (m[c] != 2) ok=false;
  Yes(ok);
  return 0;
}


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

typedef long long ll;

ll func(ll x){
    if(x<10) return x;
    return x%10 + func(x/10);
}

int main(){
    ll N;
    cin >> N;
    
    ll ds;
    ds = func(N);
    //cout << ds << endl;
    if(N%ds==0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next] or True:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

ans = 0
for i in range(N):
    if dist_from_u[i] < dist_from_v[i]:
        ans = max(ans, dist_from_v[i]-1)
print(ans)
exit()

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)


Measured memory_bytes: 81752
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;

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

int main() {
    int n; cin >> n;
    vector<int> ab_sum(n);
    ll b_sum = 0;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        ab_sum[i] = a+b;
        b_sum += b;
    }
    auto compare = [] (int a, int b) {return a > b; };
    sort(ab_sum.begin(), ab_sum.end(), compare);
    ll ans = -b_sum;
    for (int i = 0; i < n; i+=2) {
        ans += ab_sum[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int M,N,C;
    int l[100000],c[100000];
    pair<int,int> w[100000];
    cin >> N >> M >> C;
    for(int i=0;i<C;i++) cin >> l[i];
    for(int i=0;i<N;i++){
        int v;
        cin >> c[i] >> v;
        w[i]=make_pair(v,i);
    }
    sort(w,w+N);
    
    int ans=0;
    for(int i=N-1;M>0 && i>=0;i--){
        if(l[c[w[i].second]-1]>0){
            l[c[w[i].second]-1]--;
            ans+=w[i].first;
            M--;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4572
#include<stdio.h>

int N,U,K,V,G[105][105]={0},i,j;
int main()
{
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&U,&K);
		for(j=0;j<K;j++)
		{
			scanf("%d",&V);
			G[U][V]=1;
		}
	}
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			printf("%d%c",G[i][j],j==N?'\n':' ');
	return 0;
}



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

using namespace std;

#define sz(x) (int)(x.size())
#define fi(a, b) for(int i=a;i<b;++i)
#define fj(a, b) for(int j=a;j<b;++j)
#define fk(a, b) for(int k=a;k<b;++k)
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
////////////////////////////////

int const N = 1e5 + 41;
int const MOD = 1e9 + 7;

int n, m;
int x[N], y[N];

void add(ll &a, ll b){
	a += b;
	a %= MOD;
}

ll sum(ll a, ll b){
	return (a + b) % MOD;
}

ll mul(ll a, ll b){
	return (a * 1LL * b % MOD);
}

void solve(){
	scanf("%d %d",&n,&m);
	fi(0, n) scanf("%d",&x[i]);
	fi(0, m) scanf("%d",&y[i]);
	sort(x, x+n);
	sort(y, y+m);
	
	ll s = 0;
	for(int i=n-2;i>=0;--i){
		ll len = (x[i+1] - x[i]);
		ll w = mul(i+1, (n - (i + 1)));
		add(s, mul(len, w));
	}
	ll ans = 0;
	fi(1, m){
		ll w = mul(i, m - i);
		ll len = (y[i] - y[i-1]);
		ll tmp = mul(s, len);
		tmp = mul(tmp, w);
		add(ans, tmp);
	}
	
	printf("%lld\n",ans);
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();



	return 0;
}

Measured memory_bytes: 1024
use std::collections::HashMap;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        q: usize,
        s: chars,
        td: [(String, String); q]
    };
    let mut lcurrent = 0;
    let mut rcurrent = 0;
    for &(ref t, ref d) in td.iter().rev() {
        let t = t.chars().next().unwrap();
        let d = d.chars().next().unwrap();
        if d == 'L' {
            if lcurrent < n && s[lcurrent] == t {
                lcurrent += 1;
            }
            if rcurrent > 0 && s[n - rcurrent] == t {
                rcurrent -= 1;
            }
        } else {
            if rcurrent < n && s[n - rcurrent - 1] == t {
                rcurrent += 1;
            }
            if lcurrent > 0 && s[lcurrent - 1] == t {
                lcurrent -= 1;
            }
        }
    }

    println!("{}", n - lcurrent - rcurrent);
}


Measured memory_bytes: 18684
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define rep(i, a) for (int i = 0; i < (a); i++)
#define repd(i, a) for (int i = (a)-1; i >= 0; i--)
#define reps(i, a, j) for (int i = (j); i < (a); i++)
#define deb(x) cout << #x << " " << x << endl;
#define debs(x) cout << #x << " " << x << " ";
#define deba(x) for (auto _i:x) cout << _i << " "; cout << endl;
#define ms(a) memset(a,0,sizeof(a));
#define mp make_pair
#define eb emplace_back
#define FastOpen freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define pii pair < int , int >
#define all(a) a.begin(),a.end() 
//int power(int x,int p){if(p==0)return 1;if(p==1)return x;if(p%2)return x*power(x,p-1);int y=power(x,p/2);return y*y;}
/*
k stones 
moves - 
0 - losing state

*/

void solve() {
    int n,k; cin >> n >> k;
    int moves[n]; rep(i,n) cin >> moves[i];
    int dp[k+1];
    ms(dp);
    dp[0] = 0; // losing state
    reps(i,k+1,1) {
        rep(j,n) {
            if (i-moves[j] >= 0) {
                if (dp[i-moves[j]] == 0) dp[i] = 1;
            }
        }
    }
    if (dp[k]) cout << "First" << endl;
    else cout << "Second" << endl;

}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    FastOpen
    int t; t=1;
    while (t--) solve();
}





Measured memory_bytes: 4396
#11:24
n,k = map(int,input().split())
a = list(map(int,input().split()))
t = input()
raw = []
for i in range(n):
  if t[i] == 'r':
    raw.append(2)
  elif t[i] == 's':
    raw.append(0)
  else:
    raw.append(1)
ans = 0
result = []
for i in range(n):
  if i - k < 0:
    result.append(raw[i])
    ans += a[raw[i]]
  else:
    if raw[i] != result[i-k]:
      result.append(raw[i])
      ans += a[raw[i]]
    else:
      result.append(3)
print(ans)

Measured memory_bytes: 4980
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
typedef long long ll;

int main()
{
	int n, q;
	int ans = 0;

	cin >> n;
	vector<int> S(n);
	rep(i, n) cin >> S[i];
	cin >> q;
	vector<int> T(q);
	rep(i, q) cin >> T[i];

	rep(i, q) {
		rep(j, n) {
			if (T[i] == S[j]) {
				ans++;
				break;
			}
		}
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3144
#include <stdio.h>
 
int keta(int num)
{
        int acc = 0;
        while(num > 0) {
                num /= 10;
                acc++;
        }
        return acc;
}
 
int main()
{
        int a,b;
        while(scanf("%d %d",&a,&b) != EOF) {
                printf("%d\n",keta(a+b));
        }
        return 0;
}

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


void input(); template<typename First,typename... Rest> void input(First&,Rest&...);
void inputVector(); template<typename First,typename... Rest>  void inputVector(std::vector<First>&,Rest&...);
#define loop(n) for(int i = 0;i < (int)(n);++i)
#define rep(i,n) for(int i = 0;i < (int)(n);++i)


void calculate(){
    double N,A;
    input(N,A);
    std::cout << ceil((N + A) / 2) << '\n';
}

int main(int,char**){
    std::string str;
    input(str);
    int res = 0;
    rep(i,3)
        if(str[i] == '1') res++;
    std::cout << res << '\n';
}



void input(){return;}
template<typename First,typename... Rest>
void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}

void inputVector(){return;}
template<typename First,typename... Rest> 
void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <type_traits>
#include <map>

using namespace std;

int main(int argc, const char * argv[]) {
    long long h, w;
    cin >> h >> w;

    if(h == 2 || w == 2){
        cout << 0 << endl;
    }else if(h == 1 && w != 1){
        cout << w - 2 << endl;
    }else if(h != 1 && w == 1){
        cout << h - 2 << endl;
    }else if(h == 1 && w == 1){
        cout << 1 << endl;
    }else{
        cout << (h-2) * (w-2) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define MOD 1000000007
#define MOD 998244353
#define INF 100000000000000009
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define ZREP(i,n) for(int i=1;i<(n);++i)
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl

int gcd(int a,int b){
    if(a<=0||b<=0){
        return 0;
    }
    if(a<b)swap(a,b);
    int r=a%b;
    while(r){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}


signed main(){
    int N;
    int A[114514];
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    int L[114514],R[114514];
    L[0]=A[0];
    R[N-1]=A[N-1];
    for(int i=1;i<N;i++){
        L[i]=gcd(A[i],L[i-1]);
    }
    for(int i=N-2;i>=0;i--){
        R[i]=gcd(A[i],R[i+1]);
    }
    int Ans=max(L[N-2],R[1]);
    for(int i=1;i<=N-2;i++){//A[i]を抜かす
        Ans=max(Ans,gcd(L[i-1],R[i+1]));
    }
    cout << Ans << endl;
    
    return 0;
}


Measured memory_bytes: 2816
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 100010;

int n;
char s[N];
int pos[N * 2];

void test(char c) {
  memset(pos, -1, sizeof(pos));
  int pre = 0;
  pos[n + 1] = 0;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == c) ++pre;
    else --pre;
    if (pos[pre + n + 1] == -1)
      pos[pre + n + 1] = i;
    if (pos[pre + n] != -1 && i - pos[pre + n] >= 2) {
      cout << (pos[pre + n] + 1) << ' ' << i;
      exit(0);
    }
    if (pre + n - 1 >= 0 && pos[pre + n - 1] != -1 && i - pos[pre + n - 1] >= 2) {
      cout << (pos[pre + n - 1] + 1) << ' ' << i;
      exit(0);
    }
  }
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> (s + 1);
  n = strlen(s + 1);
  for (char c = 'a'; c <= 'z'; ++c)
    test(c);
  cout << "-1 -1";

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 1152
import sys
import itertools
INF = float("INF")

N = int(input())
AA = list(map(int, sys.stdin.readline().split()))
BB = list(map(int, sys.stdin.readline().split()))

cards = set()
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.add((a, b, i))
    else:
        cards.add((b, a, i))

def solve(ii):
    tmp = 0
    for i in range(N):
        for j in range(i+1,N):
            if ii[i] > ii[j]:
                tmp += 1
    return tmp

ans = INF
for Acards in itertools.combinations(cards, (N+1)//2):
    Bcards = cards - set(Acards)

    Ais = sorted([(card[0], card[2]) for card in Acards])
    Bis = sorted([(card[1], card[2]) for card in Bcards])

    bn = -1
    ii = []
    flag = False
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        if bn > n: # 組み合わせた時広義単調増加になってない
            flag = True
            break
        bn = n
        ii.append(i)

    if flag: continue

    ans = min(ans,solve(ii))


if ans == INF:
    print(-1)
else:
    print(ans)


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

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long, long>;
using pdd = pair<ld, ld>;

template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<ll>;
V(size_t) -> V<ll>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

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; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

const ll INF = (1ll<<62);
// const ld EPS   = 1e-10;
// const ld PI    = acos(-1.0);
const ll mod = (int)1e9 + 7;
//const ll mod = 998244353;

int main(){

    ll N;
    cin >> N;
    V<ll> H(N), P(N);
    REP(i, N) cin >> H[i] >> P[i];

    V<ll> ids(N);
    iota(ALL(ids), 0);

    sort(ALL(ids), [&](ll x, ll y){
        return H[x] + P[x] < H[y] + P[y];
    });

    V<ll> dp(N+1, INF);
    dp[0] = 0;

    REP(i, N){
        V<ll> td(N+1, INF);
        REP(j, N){
            chmin(td[j], dp[j]);
            if(dp[j]<=H[ids[i]]){
                chmin(td[j+1], dp[j]+P[ids[i]]);
            }
        }
        swap(td, dp);
    }

    ll res = 0;
    REP(i, N+1) if(dp[i]<INF) res = i;

    cout << res << endl;

    return 0;
}

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

using namespace std;

int main(){

  


  int a,b,c,d,f,l;


  cin >> a>>b>>c>>d;

  if (a<b){
    f = a;
  }else{
    f = b;
  }
  if (c<d){
    l = c;
  }else{
    l = d;
  }
  int out = f + l;
  cout<<out<<endl;
}


Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]
tmp_a = a.copy()
Sum = [a[0]]
if a[0] > 0:
    flg = 1
    ans = 0
elif a[0] < 0:
    flg = 0
    ans = 0
elif a[0] == 0:
    Sum[0] = 1
    flg = 1
    ans = 1
idx = 0
for i in range(n-1):
    Sum.append(Sum[idx] + a[i+1])
    if flg  == 1:
        flg = 0
        if Sum[i+1] >= 0:
            tmp = Sum[i+1]
            Sum[i+1] = -1
            ans += tmp + 1
    else:
        flg = 1
        if Sum[i+1] <= 0:
            tmp = Sum[i+1]
            Sum[i+1] = 1
            ans += 1 - tmp
    idx += 1

tmp_ans = ans

a = tmp_a
Sum = [a[0]]
if a[0] > 0:
    Sum[0] = -1
    flg = 0
    ans = a[0] + 1
elif a[0] < 0:
    Sum[0] = 1
    flg = 1
    ans = 1 - a[0]
elif a[0] == 0:
    Sum[0] = -1
    flg = 0
    ans = 1
idx = 0
for i in range(n-1):
    Sum.append(Sum[idx] + a[i+1])
    if flg  == 1:
        flg = 0
        if Sum[i+1] >= 0:
            tmp = Sum[i+1]
            Sum[i+1] = -1
            ans += tmp + 1
    else:
        flg = 1
        if Sum[i+1] <= 0:
            tmp = Sum[i+1]
            Sum[i+1] = 1
            ans += 1 - tmp
    idx += 1

print(min(tmp_ans, ans))


Measured memory_bytes: 14332
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        String[] as = input.readLine().split(" ");
        int a = as.length;
        List<String> list = new ArrayList<String>(Arrays.asList(as));
        List<String> listdel = new ArrayList<String>(new HashSet<>(list));
        int b = listdel.size();
        if(a == b ){
            System.out.println("YES");
        }else{
            System.out.println("NO");

        }
    }
}

Measured memory_bytes: 63408
def kai(a):
    return a==a[::-1]
s=input()
x=0
if kai(s)==False:
    for i in range(len(s)):
        if s[i]!=s[-1-i]:
            x+=1
            for j in range(25):
                s[i]==chr(97+j)
                if s==s[::-1]:
                    break
print(x//2)

Measured memory_bytes: 3188
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	cin >> N >> K;
	vector<int>v(N);
	for (auto &i : v)cin >> i;
	vector<int>dp(K + 1);
	for (int i = 1; i <= K; i++) {
		for (auto j : v) {
			if (i - j < 0)continue;
			if (!dp[i - j])dp[i] = 1;
		}
	}
	if (dp[K])cout << "First\n";
	else cout << "Second\n";
	return 0;
} 

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
    int n,h,w,ans=0;
    cin >> n >> h >> w;
    int a[n],b[n];
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
        if(a[i]>=h && b[i]>=w) ans++;
    }
    cout << ans <<endl;

}

Measured memory_bytes: 256
n = int(input())
A = []

for i in range(n):
    a = int(input())
    A.append(a)
A.sort()
i = 0
ans = 0
while True:
    cnt = 0
    while A[i + cnt] == A[i]:
        cnt += 1
        if i + cnt == n:
            break
    if cnt%2 == 1:
        ans += 1
    i += cnt
    if i == n:
        break
print(ans)

Measured memory_bytes: 13176
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a,b,c;
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		
		System.out.println((a-c)/(b+c));
	}
}

Measured memory_bytes: 21972
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<memory.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int n,k;
  cin >> n >> k;
  ll a[n+1]={};
  rep(i,n)cin >> a[i+1];
  ll sum[n+1]={},posisum[n+1]={};
  rep(i,n){
    sum[i+1]=sum[i]+a[i+1];
    posisum[i+1]=posisum[i]+max(0LL,a[i+1]);
  }
  ll ans=-longinf;
  for(int i=1;i+k<=n+1;i++){
    ans=max(ans,max(0LL,(sum[i+k-1]-sum[i-1]))+posisum[i-1]+posisum[n]-posisum[i+k-1]);
  }
  cout << max((ll)0,ans) << endl;
return 0;}

Measured memory_bytes: 2560
/*
黒板に 
N
 個の正の整数 
A 1 , . . . , A N が書かれています．

すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
黒板に書かれている整数すべてを， 2 で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．
*/
package main

import "fmt"

func main() {
	var n, ans int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	for {
		for i := range a {
			if a[i] % 2 != 0 {
				fmt.Println(ans)
				return
			} 
			a[i] /= 2
		}
		ans++
	}
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
    int n,k; cin >> n >> k;
    ll ans = k;

    for(int i=0; i<n-1; i++) ans = ans * (k-1);

    cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define F first
#define S second


typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;

int main() {
	set<int> s;
	int q; cin >> q;
	VI qu(q), x(q);
	rep(i, q)cin >> qu[i] >> x[i];

	rep(i, q) {
		if (qu[i] == 0) {
			s.insert(x[i]);
			cout << sz(s) << endl;
		}
		else {
			puts(s.find(x[i]) != s.end() ? "1" : "0");
		}
	}
}


Measured memory_bytes: 13564
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int x, y;
	cin >> x >> y;
	if (abs(x - y) <= 1) cout << "Brown\n";
	else cout << "Alice\n";
}

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

typedef long long ll;

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,l,n) for(int i=(l);i<(n);i++)

template<class T>
using vt = vector<T>;
template<class T>
using vvt = vector<vector<T>>;

int main(){
    vector<vector<int>> Bingo(3,vector<int>(3));
    vector<vector<int>> Atari(3,vector<int>(3,0));
    int N;
    vector<int> number(100);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin >> Bingo[i][j];
        }
    }
    cin >> N;
    for(int i=0;i<N;i++) cin >> number[i];
    for(int m=0;m<N;m++){
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){ 
                if(number[m]==Bingo[i][j]) Atari[i][j]=1;
            }
        }
    }
    for(int i=0;i<3;i++){
        if(Atari[i][0]*Atari[i][1]*Atari[i][2]==1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    for(int i=0;i<3;i++){
        if(Atari[0][i]*Atari[1][i]*Atari[2][i]==1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if(Atari[0][0]*Atari[1][1]*Atari[2][2]==1){
        cout << "Yes" << endl;
        return 0;
    }
    if(Atari[0][2]*Atari[1][1]*Atari[2][0]==1){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}




Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const int MAXN = 100100;
string S[MAXN];

struct Node {
    int sum;
    int id;
    int child[26];
    Node() : sum(0), id(-1) {
        memset(child, -1, sizeof(child));
    }
};

int trieNum = 1;
Node trie[4*MAXN];

void addTrie(int from, int num) {
    if (trie[from].child[num] == -1) trie[from].child[num] = trieNum++;
}

int cnt[26][26];
int ans[MAXN][26][26];
int pf[MAXN];

void calc(int now, int p) {
    if (trie[now].id >= 0) {
        int id = trie[now].id;
        pf[id] = p++;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++)
                ans[id][i][j] = cnt[i][j];
        }
    }
    for (int i = 0; i < 26; i++) {
        if (trie[now].child[i] >= 0) {
            for (int j = 0; j < 26; j++) {
                if (i != j && trie[now].child[j] >= 0) {
                    int id = trie[now].child[j];
                    cnt[i][j] += trie[id].sum;
                }
            }
            calc(trie[now].child[i], p);
            for (int j = 0; j < 26; j++) {
                if (i != j && trie[now].child[j] >= 0) {
                    int id = trie[now].child[j];
                    cnt[i][j] -= trie[id].sum;
                }
            }
        }
    }
}
int pos[26];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        int now = 0;
        for (char c : S[i]) {
            trie[now].sum++;
            addTrie(now, c-'a');
            now = trie[now].child[c-'a'];
        }
        trie[now].sum++;
        trie[now].id = i;
    }
    calc(0, 0);
    cin >> Q;
    while (Q--) {
        int k;
        string perm;
        cin >> k >> perm;
        --k;
        for (int i = 0; i < 26; i++)
            pos[perm[i]-'a'] = i;
        int res = 1 + pf[k];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (pos[i] > pos[j]) res += ans[k][i][j];
            }
        }
        cout << res << endl;
    }
    return 0;
}


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

long long solve(long long a, long long b)
{
    if (a < b)
    {
        if (b - a > a) return a;
        else return b - a;
    }
    if (a % b == 0) return 0;
    long long x = a - (a / b) * b;
    long long y = (a / b + 1) * b - a;
    if (x > y) return y;
    return x;
}

int main()
{
    long long n, k;
    cin >> n >> k;
    cout << solve(n, k);
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

l, c, r = 0, 1, 2
P = sum(A[:l])
Q = sum(A[l:c])
R = sum(A[c:r])
S = sum(A[r:])
err = 10**10

while c <= N-2:
	while True:
		# leftを動かして考える
		# lを動かして差が広がったらいったん中断
		if abs(P-Q) < abs((P+A[l])-(Q-A[l])):
			break
		# もちろんcはlよりも大きい
		if l == c-1:
			break

		P += A[l]
		Q -= A[l]
		l += 1

	while True:
		# rightについても同様に動かして考える
		# rを動かして差が広がったらいったん中断
		if abs(R-S) < abs((R+A[r])-(S-A[r])):
			break
		# もちろんrはN-1以下
		if r == N-1:
			break

		R += A[r]
		S -= A[r]
		r += 1

	err = min(max(P,Q,R,S)- min(P,Q,R,S), err)

	# centerについて調整
	Q += A[c]
	R -= A[c]
	c += 1

print(err)


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

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    string s;
    cin >> s;
    if(s[0] == s[1] and s[1] == s[2]){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}

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

int main() {
  
  string S;
  cin >> S;
  
  vector<int> C;
  for (char x: S) {
    C.push_back( x - '0' );
  }

  for (int tmp = 0; tmp < (1 << 3); tmp++) {
    bitset<3> p(tmp);
    int A = C.at(0);
    for ( int i=0; i<3; i++) {
       if(p.test(i)) A += C.at(i+1);
       else A -= C.at(i+1);
    }
    if ( A == 7 ) {
      for ( int i=0; i<3; i++) {
        cout << S.at(i);
        if(p.test(i)) cout << "+";
        else cout << "-";
      }
      cout << S.at(3) << "=7" << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
N, M = [int(x) for x in input().split(" ")]
submit = dict()

for _ in range(M):
    p, S = [x for x in input().split(" ")]
    p = int(p)
    if p in submit:
        submit[p].append(S)
    else:
        submit[p] = [S]


cor = 0
fail = 0

for _, res in submit.items():
    fail_one = 0
    cor_one = 0
    for pat in res:
        if pat == "AC":
            cor_one = 1
            break
        else:
            fail_one += 1
    cor += cor_one
    if cor_one == 1:
        fail += fail_one

print(cor, fail)


Measured memory_bytes: 64856
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n,dif,i;
    scanf("%d",&n);
    int a[n+10];
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);

    dif=a[n-1]-a[0];

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





}


Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

    dp = [-1] * (N + 10)
    dp[0] = 0
    sort_A = sorted(A, reverse=True)

    for a in sort_A:
        tmp = cost[a]
        for i in range(N + 1):
            if dp[i] == -1:
                continue
            dp[i+tmp] = max(dp[i+tmp], dp[i] * 10 + a)

    print(dp[N])






main()

Measured memory_bytes: 65756
#pragma region Template
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX;
const int INF = INT_MAX;

inline int sqr(int x) { return (x * x); }
inline void printd(double x) { printf("%.10lf\n", x); }
inline void upsort(VI& x) { sort((x).begin(), (x).end()); }
inline void downsort(VI& x) { sort((x).begin(), (x).end(), greater<int>()); }
inline int absdiff(int a, int b) {
	if (b > a) return absdiff(b, a);
	return (a - b);
}
int gcd(int a, int b) { // 最大公約数
	if (a < b) return gcd(b, a);
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
inline int lcm(int a, int b) { return a * b / gcd(a, b); } // 最小公倍数
#pragma endregion



signed main()
{	
	int N, M;
	cin >> N >> M;
	VP AB(M);
	rbf(ab, AB) cin >> ab.first >> ab.second;

	VI perm(N-1);
	int i = 2;
	rbf(p, perm) p = i++; // perm = {2, 3, ... , N}

	i = 2;
	int pattern = 1;
	while (i < N) pattern *= i++;

	// {2, 3, ... , N}の全並べ替えパターンをallpermに格納
	VVI allperm(pattern, VI(N - 1));
	i = 0;
	do {
		allperm[i++] = perm;
	} while (next_permutation(All(perm)));

	int a, b, cnt = 0;
	bool flg = false, flg2 = false;
	// 全並べ替えパターンについて辺を辿ることができるかを判定
	rbf(pp, allperm) {
		a = 1; b = 1;
		flg2 = true;
		rbf(p, pp) {		
			a = b;
			b = p;
			flg = false;
			rbf(ab, AB) {
				// a, bをつなぐ辺があるかの判定
				if ((a == ab.first && b == ab.second) || (b == ab.first && a == ab.second)) {
					flg = true;
					break;
				}
			}
			// a, bをつなぐ辺がなければありえないパスなのでbreak
			if (!flg) {
				flg2 = false;
				break;
			}
		}
		// rbf(p, pp)を完走できればあり得るパスなのでカウント追加
		if (flg2) {
			cnt++;
		}
	}

	COL(cnt);

	return 0;
}

Measured memory_bytes: 640