akhauriyash/Code-Regression huggingface dataset:
Ass = [tuple(map(int, input().split())) for _ in range(3)]
N = int(input())
Bs = [int(input()) for _ in range(N)]

isFoundss = [[0]*(3) for _ in range(3)]
for B in Bs:
    for i in range(3):
        for j in range(3):
            if Ass[i][j] == B:
                isFoundss[i][j] = 1
#print('isFoundss:', isFoundss)

ans = 'No'
for i in range(3):
    for j in range(3):
        if isFoundss[i][j] == 0:
            break
    else:
        ans = 'Yes'

for j in range(3):
    for i in range(3):
        if isFoundss[i][j] == 0:
            break
    else:
        ans = 'Yes'

for i in range(3):
    if isFoundss[i][i] == 0:
        break
else:
    ans = 'Yes'

for i in range(3):
    if isFoundss[i][2-i] == 0:
        break
else:
    ans = 'Yes'

print(ans)


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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n); i >= 0; i--)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define RREP(i, a, n) for(int i = (int)(n); i >= a; i--)
#define all(x) (x).begin(),(x).end()

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; }

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    set<char> key;
    rep(i,N)
    {
        char tmp;
        cin >> tmp;
        key.insert(tmp);
    }
    if( key.size() == 4 ) cout << "Four" << endl;
    else cout << "Three" << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main() {
    int n;
    
    ll ans = 0;

    vector<int> a;

    cin >> n;

    for (int i = 0; i < n; i++) {
         int aa;
         cin >> aa;
         a.push_back (aa);
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[i-1] != i) {
            int b = a[i-1];
            if (a[b-1] == i) ans++;
            else ans = 100;
        }
    }
    
    (ans == 0 || ans == 2) ? (cout << "YES" << endl) : (cout << "NO" << endl);
}



Measured memory_bytes: 256
/*  
    tanuj_johal :: gla_clg_sync_with_CSE(true);
    bonding.tie(true);
    hardwork.tie(true);
    
    ::::::::--------------------::::::::
*/

#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          long long
#define fio         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define vi          vector<ll>
#define pp          push_pop
#define pll         pair<ll,ll>
#define in          insert
#define ff          first
#define ss          second
#define inf         10000000000000000
#define all(p)      p.begin(), p.end()
#define que_max     priority_queue <int>
#define que_min     priority_queue <int, vi, greater<int>>
#define print(a)    for(auto i:a){cout<<i<<" ";}
#define print1(a)   for(auto i:a){cout<<i.ff<<" "<<i.ss<<endl;}

typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> Set;


const ll mod = 1e9+7;

ll power(ll x,ll y,ll p){ll r=1;x=x%p;while(y>0){if(y&1)r=(r*x)%p;y=y>>1;x=(x*x)%p;}return r;}

void solve()
{
    unordered_map<ll,ll> mp;          set<ll> st; 
    
    ll n;
    cin>>n;
    for(ll i=0;i<n-1;i++){
        ll a;cin>>a;
        mp[a]++;
    }
    
    for(ll i=1;i<=n;i++){
        cout<<mp[i]<<"\n";
    }




}

int main()
{
    fio
    // int t;cin>>t;while(t--)
    {
        solve();
    }
    
}


Measured memory_bytes: 11320
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <list>
#include <ctime>
#include <memory.h>
#include <bitset>
#include <climits>
#include <iostream>
#include <stdlib.h>

#define F first
#define S second
#define endl "\n"
#define pb push_back
#define mp make_pair
#define bs 1000000007
#define pi 3.141592653589793
#define y1 kjdfshnvoavaofobiopj
using namespace std;

long long n, k, x, y, ans;

int main(){
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);

cin>>n>>k>>x>>y;
if(k >= n)
	ans = min(k, n)*x;
else
	ans = k*x+(n-k)*y;
cout<<ans<<endl;

return 0;}


Measured memory_bytes: 764
n,k = map(int, input().split())
p = list(map(int, input().split()))
def expected_value(p):
  E = []
  for i in p:
    E.append(float((i+1)/2))
  return E
def cumulative_sum(E, n):
  s = []
  for i in range(n):
    if i == 0:
      s.append(0)
    s.append(s[i]+E[i])
  return s
def max_search(k,n,p):
  ans = []
  E = expected_value(p)
  S = cumulative_sum(E, n)
  for i in range(int(n-k+1)):
    ans.append(S[i+k] - S[i])
  return max(ans)
print(max_search(k,n,p))

Measured memory_bytes: 79496
/*
Hanit Banga
*/

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false)

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

const int N = 1e5 + 5;

int main()
{
	ll x;
	cin >> x;

	ll ans = x;
	for (ll i = 1; i <= x; ++i)
	{
		if (i * (i + 1) / 2 >= x)
		{
			ans = min(ans, i);
			break;
		}
	}

	cout << ans << endl;
}	

Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner()

	a := sc.NextInt()
	b := sc.NextInt()
	_ = sc.NextInt()
	k := sc.NextInt()

	if k%2 == 0 {
		fmt.Printf("%+v\n", a-b) // output for debug
	} else {
		fmt.Printf("%+v\n", b-a) // output for debug
	}
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
char str[10];
int main()
{
  scanf("%s",str+1);
  int n=strlen(str+1);
  for(int i=1;i<=n;i++)
  {
    if(str[i] == '9') putchar('1');
    else if(str[i] == '1') putchar('9');
    else putchar(str[i]);
  }
  return 0;
}

Measured memory_bytes: 128
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <bitset>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000000000//10^18
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007
#define MODANOTHER 998244353
#define PI acos(-1)

#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vvvd vector<vector<vector<double>>>


//#define int long long

using namespace std;


const int MAX = 510000;

ll mod_inverse(int a,int M){
	int x=M-2;
	ll temp=a;
	ll ret=1;
	//a^(MOD-1)==1(mod MOD)を利用
	//a^-1==a^(MOD-2) (mod MOD)を繰り返し二乗法で求める

	while(x!=0){
		if(x%2==1){
			ret=(ret*temp)%M;
		}
		temp=(temp*temp)%M;
		x=x/2;
	}
	return ret;
}

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++){
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k){
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed compare_int(const void *a, const void *b)
{
	int *A = (int *)a;
	int *B = (int *)b;
	if (*A < *B) return 1;
	if (*A > *B) return -1;
	return 0;
}


signed main(void)
{
	//変数の宣言
	int n,m;
	int h,w;
	int x,y,z;
	static int a[200010];
	static int b[200010];
	static int v[100010];
	static int p[100010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	int temp=0;
	int temp1=0;
	int temp2=0;
	int temp3=0;
	vector<int> vec;
	vector<int> vtemp;
	int max=0;
	int min=INFINT;
	int len=0;
	int sum=0;
	int ok=0;
	int ng=0;
	char dummy;
	static char stemp[100010];
	vvi graph;
	
	//データの読み込み


	scanf("%d %d",&n,&m);
	//scanf_s("%d %d",&n,&m);


	//scanf("%s",&s);
	//scanf_s("%s",&s,20);


	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		//scanf_s("%d",&a[i]);
	}



	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

//	clock_t start=clock();
//	COMinit();
	for(i=0;i<n;i++){
		sum += a[i];
	}

	qsort(a,n,sizeof(int),compare_int);

	/*printf("sum=%d\n",sum);
	printf("sum/4m=%f\n",(double)sum/(4*m));
	for(i=0;i<n;i++){
		printf("a[%d]=%d\n",i,a[i]);
	}*/

	flag=1;
	for(i=0;i<m;i++){
		if(a[i]<(double)sum/(4*m)){
			printf("No");
			return 0;
		}
	}

	printf("Yes");


//	clock_t end=clock();

	//	printf("計算部分終了\n");

	//出力
	
	//printf("%d",(d[i-1][j-1]+1)/2);

//	printf("time=%lf",(double)(end-start)/CLOCKS_PER_SEC);
	//	printf("結果の出力終了\n");

	return 0;
}



Measured memory_bytes: 2304
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
print(dp[-1])

Measured memory_bytes: 84208
#include <bits/stdc++.h>
using namespace std;
#define Maxn 307
#define modp 998244353
int len,n,K;
int a[Maxn];
int f[Maxn][Maxn][Maxn],s1[Maxn][Maxn][Maxn],s2[Maxn][Maxn][Maxn];
char s[Maxn];
int main()
{
    scanf("%s%d",s+1,&K);
    len=strlen(s+1);
    n=0;
    for (int i=1;i<=len;i++)
        if (s[i]=='1') ++a[n]; else ++n;
    if (K>len) K=len;
    f[n+1][0][0]=1;
    for (int i=0;i<=len;i++)
        s1[n+1][i][0]=1,s2[n+1][i][i]=1;
    int sum=0;
    for (int i=n;i>=0;i--)
    {
        sum+=a[i];
        for (int j=0;j<=sum;j++)
            for (int k=0;k<=K;k++)
            {
                f[i][j][k]=s1[i+1][j][k];
                if (j-a[i]>0) f[i][j][k]=(f[i][j][k]+modp-s1[i+1][j-a[i]-1][k])%modp;
                int lx=a[i]+1,rx=min(j,k+a[i])+1;
                if (lx<rx) f[i][j][k]=(f[i][j][k]+s2[i+1][j-lx][k+a[i]-lx])%modp;
                s1[i][j][k]=f[i][j][k];
                if (j>0) s1[i][j][k]=(s1[i][j][k]+s1[i][j-1][k])%modp;
                s2[i][j][k]=f[i][j][k];
                if (j>0&&k>0) s2[i][j][k]=(s2[i][j][k]+s2[i][j-1][k-1])%modp;
            }
        for (int j=sum+1;j<=len;j++)
            for (int k=0;k<=K;k++)
            {
                f[i][j][k]=0;
                if (j>0) s1[i][j][k]=s1[i][j-1][k];
                if (j>0&&k>0) s2[i][j][k]=s2[i][j-1][k-1];
            }
    }
    int ans=0;
    for (int i=0;i<=K;i++)
        ans=(ans+f[0][sum][i])%modp;
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 329424
import java.util.*;


public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
	    int b = scanner.nextInt();
		if(a + b == 15) 
			System.out.println('+');
		else if(a * b == 15) 
			System.out.println('*');
		else 
			System.out.println('x');
		
		scanner.close();
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int jumpsDP(int n,int * arr,int * dp,int k){
    dp[0] = 0;
    dp[1] = 0;
    int q1 = INT_MAX;
    if(dp[n]!=-1){
        return dp[n];
    }
    for(int i=1;i<=k;i++){
        if(n-i>=0){
            q1 = min(q1,jumpsDP(n-i,arr+i,dp,k) + abs(arr[i] - arr[0]));
        }
    }
    dp[n] = q1;
    return dp[n];
}
int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n],dp[n+1];
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<=n;i++){
        dp[i] = -1;
    }
    cout<<jumpsDP(n,arr,dp,k);
}

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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
/*--------------------------------------------*/
int main(){
    int x,y,z;cin>>x>>y>>z;
    x-=z;
    int cnt=0;
    while(1){
        if(x-(y+z)<0)break;
        x-=y+z;
        cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#include <utility>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<pair<string, int>, int>>a(n);
	REP(i, n) {
		cin >> a[i].first.first >> a[i].first.second;
		a[i].first.second = -a[i].first.second;
		a[i].second = i + 1;
	}
	sort(a.begin(), a.end());
	REP(i, n) {
		cout << a[i].second << endl;
	}
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

def main():
    n,k,q = map(int,input().split())
    a = [int(input()) for _ in range(q)]
    dic = defaultdict(int)
    for i in range(q):
        dic[a[i]] += 1
    
    now = k-q

    for i in range(1,n+1):
        if now+dic[i]>0:
            print("Yes")
        else:
            print("No")
if __name__ == "__main__":
    main()

Measured memory_bytes: 69080
INF = 10 ** 10
n, m = gets.split.map(&:to_i)
bin_memo = [1]
1.upto(n - 1) do |i|
  bin_memo[i] = bin_memo[i - 1] * 2
end
costs = []
keys = []
# m.times do
#   costs << gets.to_i
#   keys << gets.split.map(&:to_i).inject(0) { |res, num| res | bin_memo[num - 1] }
# end
dp = Array.new(2 ** n, INF)
dp[0] = 0
m.times do |i|
  c = gets.to_i
  key = gets.split.map(&:to_i).inject(0) { |res, num| res | bin_memo[num - 1] }
  dp.each_with_index do |cost, opened|
    next if cost == INF
    next_opened = (opened | key)
    dp[next_opened] = [dp[next_opened], cost + c].min
  end
end
puts dp.last == INF ? - 1 : dp.last


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

int main() {
  int N, T, E; cin >> N >> T >> E;
  vector<int> X(N);
  for(int i=0; i<N; i++) cin >> X[i];

  int lb = T - E, ub = T + E;
  for(int i=0; i<N; i++) {
    for(int x=1; x*X[i]<=ub; x++) {
      int v = x * X[i];
      if(lb <= v and v <= ub) {
        cout << i + 1 << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
  return 0;
}



Measured memory_bytes: 3092
def bitcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f #8bitごと
    x = x + (x >> 8) #16bitごと
    x = x + (x >> 16) #32bitごと
    x = x + (x >> 32) #64bitごと = 全部の合計
    return x & 0x0000007f

def binary_to_int(x):
    temp = 0
    for i in range(len(str(x))):
        temp += 2**(len(str(x))-i-1) * int(str(x[i]))
    return temp

n = int(input())
shops = []
for i in range(n):
    shops.append(binary_to_int("".join(input().split())))
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

for i in range(1, 2**10):
    temp = 0
    for j in range(n):
        temp += p[j-1][bitcount(i & shops[j-1])]
    if i == 1:
        ans = temp
    elif temp > ans:
        ans = temp

print(ans)

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int N;cin>>N;
    for(int i=1;;i++)if((1ll<<i)>N){
        cout<<(1ll<<(i-1))<<endl;
        return 0;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  int a,b,tmp;
  cin >> a >> b;
  if(a>b) swap(a,b);
  while(a % b != 0)
  {
      tmp = b;
      b = a % b;
      a = tmp;
  }
  cout << b << endl;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
long long l1,l2,n,a,b;
int main(){
	cin>>n;l1=1,l2=1;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		long long p1=(l1+a-1)/a;
		long long p2=(l2+b-1)/b;
		long long p3=max(p1,p2);
		l1=p3*a;l2=p3*b;
		//cout<<l1<<' '<<l2<<endl;
	}
	cout<<l1+l2<<endl;
	return 0;
}

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

int main() {
    int n;
    cin>>n;
    int  a[500000];
    long long int sum=0;
   long long int m[200000];
    for(int i=0;i<n;i++)
    {cin>>a[i];
    m[a[i]]++;
    sum+=a[i];
    }
    int q;
    cin>>q;
    while(q--)
    {
        int c,b;
        cin>>c>>b;
        if(m[c]>0)
        {
            sum=sum-c*m[c];
            sum+=b*m[c];
            m[b]+=m[c];
            m[c]=0;
        }
        
       
           
       
       cout<<sum<<endl;
    }

}


Measured memory_bytes: 4780
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool binSearch(int *s, int n, int target)
{
	int lo = 0;
	int hi = n - 1;
	while (lo <= hi)
	{
		int mid = lo + (hi - lo) / 2;
		if (s[mid] == target)
			return true;
		else if (target > s[mid])
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	return false;
}

int main()
{
	int val, n, q;
	int s[100000], t[50000];

	cin >> n;
	for (int i = 0; i<n && cin >> val; ++i) s[i] = val;

	int count = 0;
	cin >> q;
	while (q--)
	{
		cin >> val;
		if (binSearch(s, n, val)) count++;
	}

	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3368
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <chrono>
using namespace std;

int main(int argc, const char * argv[]) {
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S.at(i);
    }
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int cnt = 0;
            if (S.at(i).at(j) == '.') {
                for (int k = max(0, i - 1); k <= min(H - 1, i + 1); k++) {
                    for (int l = max(0, j - 1); l <= min(W - 1, j + 1); l++) {
                        if (S.at(k).at(l) == '#') cnt++;
                    }
                }
                S.at(i).at(j) = to_string(cnt).at(0);
            }
        }
    }
    
    for (int i = 0; i < H; i++) {
        cout << S.at(i) << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() { 
  int n,m;
  cin >>n>>m;
  int p[100010],y[100010];
  vector<int> id[100010];
  for(int i=0;i<m;i++){
    cin >> p[i]>>y[i];
    id[p[i]].push_back(y[i]);
  }

  for(int i=0;i<n;i++){
    sort(id[i+1].begin(),id[i+1].end());
  }
  for(int i=0;i<m;i++){
    printf("%06d",p[i]);
    auto itr = lower_bound(id[p[i]].begin(),id[p[i]].end(),y[i]);
    printf("%06d",itr-id[p[i]].begin()+1);
    cout << endl;
  }
}


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

using namespace std;

int main() {
    int w,n,amida[30],yoko1,yoko2,i;

    cin >> w >> n;

    for(i = 1;i <= w;i++){
        amida[i] = i;
    }

    for(i = 0;i < n;i++){
        scanf("%d,%d",&yoko1,&yoko2);
        int box = amida[yoko1];
        amida[yoko1] = amida[yoko2];
        amida[yoko2] = box;
    }

    for(i = 1;i <= w;i++){
        cout << amida[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int p[1005];

int main()
{
	memset(p, 0, sizeof(p));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, D; cin >> N >> D;
	rep (i, N) cin >> p[i];
	int res = 0;
	rep (i, N) res += (int)max(p[i] - D, 0);
	if (res == 0){
		cout << "kusoge" << endl;
	}else{
		cout << res << endl;
	} // end if

	return 0;
}

Measured memory_bytes: 1196
// abc174_b
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
  ll N, D;
  cin>>N>>D;
  ll X, Y, cnt = 0;
  rep(i, N) {
    cin>>X>>Y;
    if (X*X+Y*Y <= D*D) cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 999999
#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<k;i++)
typedef long long ll;
typedef unsigned long long ull;

int main(){
    int pe[8]={0};
    int fj[] ={1,4,1,4,1,2,1,2,1,4,1,4,1,2,1,2};
    while(~scanf("%d",&pe[0])){
        reps(i,1,8)scanf("%d",&pe[i]);
        int comp = INF;
        int res[8]={0};
        rep(i,8){
            int x = 0;
            reps(j,i,i+8){
                x += (fj[j] >= pe[j-i]) ? 0 : pe[j-i] - fj[j];
            }
            if(comp == x){
                bool f = false;
                reps(j,i,i+8){
                    if(res[j-i] < fj[j])break;
                    else if(res[j-i] > fj[j]){
                        f = true;
                        break;
                    }
                }
                if(f){
                    reps(j,i,i+8)res[j-i] = fj[j];
                    comp = x;
                }
            }
            else if(comp > x){
                reps(j,i,i+8)res[j-i] = fj[j];
                comp = x;
            }
        }
        rep(i,7)printf("%d ",res[i]);
        printf("%d\n",res[7]);
    }
	return 0;
}

Measured memory_bytes: 1188
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		    Scanner sc = new Scanner(System.in);

		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int countg1 = 0;
		    int countg2 = 0;
		    int countg3 = 0;
		    if(a == 1 || a == 3 || a == 5||a == 7|| a == 8|| a==10 ||a==12) {
		    	countg1++;
		    }
		    if(b == 1 || b == 3 || b == 5|| b == 7 || b == 8|| b == 10 || b == 12) {
		    	countg1++;
		    }
		    if(a==4||a==6||a==9||a==11) {
		    	countg2++;
		    }
		    if(b==4||b==6||b==9||b==11) {
		    	countg2++;
		    }
		    if(a==2) {
		    	countg3++;
		    }
		    if(b==2) {
		    	countg3++;
		    }
		    if(countg1 == 2||countg2 == 2||countg3==2) {
		    	System.out.println("Yes");
		    }
		    else {
		    	System.out.println("No");
		    }
		    
		    sc.close(); }
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<sstream>
#include<math.h>
#define rep(i,n) for(int i =0;i<(int)(n);i++)
typedef long long ll;
using namespace std;
int main() {
	int x;
	cin >> x;
	cout << (x / 500) * 1000 + ((x % 500) / 5) * 5 << endl;
	return 0;
}


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

namespace ABC
{
    class ABC165A
    {
        const bool TESTING = false;
        const string FILE = "/tmp/data.txt";

        static void Main(string[] args)
        {
            if (TESTING)
            {
                Console.SetIn(new StreamReader(FILE));
            }
            var line = Console.ReadLine();
            int k = int.Parse(line);
            line = Console.ReadLine();
            var sa = line.Split(' ');
            int a = int.Parse(sa[0]);
            int b = int.Parse(sa[1]);
            proc(k, a, b);
#if DEBUG
            Console.WriteLine();
#endif
        }

        private static void proc(int k, int a, int b)
        {
            for (int ki = k; ki <= 1000; ki += k)
            {
                if (a <= ki && ki <= b)
                {
                    Console.WriteLine("OK");
                    return;
                }
            }
            Console.WriteLine("NG");
        }
    }
}


Measured memory_bytes: 27540
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second  
#define endl '\n'
#define pb push_back
#define t_case ll tt; cin>>tt; while (tt--)
#define all(v) v.begin(),v.end()
#define ub(a,x) upper_bound(all(a),x)-a.begin()
#define lb(a,x) lower_bound(all(a),x)-a.begin()
#define fr(a,b,c) for (ll a=b;a<c;a++)
#define take(xx,n) for (int i=0;i<n;i++) cin>>xx[i];
#define take1(xx,n) for (int i=1;i<=n;i++) cin>>xx[i];
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

int main() 
{
	fastio
	//t_case
	{
		ll n,m,q,ans=1000,f=1,d,k,x,y,sum=0,h,w  ;cin>>n  ;
		ll a[n+1]; take(a,n);
		fr(i,0,n-1) {
			if (a[i]<a[i+1]){
			 	x=ans/a[i];
				ans+=x*(a[i+1]-a[i]);
			}
		}
		cout<<ans;
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<utility>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<cctype>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<ll> vl;
typedef queue<int> qi;
typedef queue<ll> ql;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define pq priority_queue
#define rep(i,n) for (int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define INF 200000009
#define init(x) memset(x,0,sizeof(x))
bool dp[10005];
int n,a[105];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for (int i=1;i<=n;++i) cin>>a[i];
	dp[0]=1;
	for (int i=1;i<=n;++i){
		for (int j=10004-a[i];j>=0;--j) dp[j+a[i]]|=dp[j];
	}
	for (int i=10005;i>=0;--i) if (dp[i]&&i%10){
		cout<<i<<endl;
		return 0;
	}
	cout<<0;
	return 0;
}

Measured memory_bytes: 256
import math

N = int(input())
position = [list(map(int, input().split())) for _ in range(N)]
S = 0
for i in range(N):
    x, y = position[i]
    for each_x, each_y in position:
        S += math.sqrt((x-each_x)**2 + (y-each_y)**2)

print(S/N)


Measured memory_bytes: 38256
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, less<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[&](auto f,auto... args){return f(f,args...);};

int main(){
    lint w,a,b;
    cin>>w>>a>>b;
    cout<<max(abs(a-b)-w,0LL)<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <numeric>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
  std::int_fast64_t n;
  std::cin >> n;
  std::vector<std::int_fast64_t> s(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, s.begin());

  const std::int_fast64_t sum = std::accumulate(s.begin(), s.end(), static_cast<std::int_fast64_t>(0));
  if (sum % 10 != 0) {
    std::cout << sum << std::endl;
  } else {
    std::sort(s.begin(), s.end());
    const std::vector<std::int_fast64_t>::iterator min_indivisible = std::find_if(s.begin(), s.end(), [](const std::int_fast64_t& s_i) {
      return s_i % 10 != 0;
    });
    if (min_indivisible != s.end()) {
      std::cout << sum - *min_indivisible << std::endl;
    } else {
      std::cout << 0 << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<algorithm>
#define ff(i,m,n) for(int i=m;i<=n;i++)
using namespace std;

int main() {
	int a;
	cin >> a;
	vector<int64_t> L(a+1);
	L.at(0) = 2;
	L.at(1) = 1;
	ff(i, 2, a) {
		L.at(i) = L.at(i - 1) + L.at(i - 2);
		//cout << i<<":"<<L.at(i) << endl;
	}
	cout << L.at(a) << endl;
	return 0;
}

Measured memory_bytes: 256
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())
divisors = make_divisors(n)
divisors.sort()
res = n*2
for i in range(int(len(divisors)/2+1)):
	if res > (divisors[i]+divisors[-(i+1)]-2):
		res = (divisors[i]+divisors[-(i+1)]-2)
print(res)


Measured memory_bytes: 3264
function main(input) {
  var H = input[0]-0;
  console.log(calc(H));
}


var map = {1:1};
function calc(H){
  if(map[H]) return map[H];
  return map[H] = (calc(Math.floor(H/2))+calc(Math.floor(H/2))+1);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').split("\n"))


Measured memory_bytes: 7756
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    long long N;

    cin >> N;

    if(N==1){
        cout << 1 << endl;
        return 0;
    }
    for(int i=1;i<=N;i++){
        if(i*i > N){
            cout << (i-1)*(i-1) << endl;
            return 0;
        }
    }
}

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

int main(){
    int a,b,c,x,s=0;
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(500*i+100*j+50*k==x) s++;
            }
        }
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=[(f,F),(f,-F)];H=[(F,f),(-F,f)]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=c,;X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if 0==v[d][c]and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Measured memory_bytes: 551448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P,P> PP;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, k;
    vector<ll> book[10];
    cin >> n >> k;
    REP(i,n){
        ll c, g;
        cin >> c >> g;
        g--;
        book[g].push_back(c);
    }
    REP(i,10){
        SORT(book[i]);
        book[i].push_back(0);
        reverse(ALL(book[i]));
        REP(j,book[i].size()-1){
            book[i][j+1] += book[i][j];
        }
    }
    ll dp[15][4005]{}; // i種類までみてj本選んだときの最大
    REP(i,10){
        REP(j,k+1){
            if(j>0&&dp[i][j]==0)break;
            REP(m,book[i].size()){
                dp[i+1][j+m] = max(dp[i+1][j+m],dp[i][j]+book[i][m]+(m-1)*m);
            }
        }
    }
    cout << dp[10][k] << endl;
    return 0;
}



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

struct ModInt {
    using M = ModInt;

    static vector<M> fact, finv;
    static long long MOD;
    long long v;

    // normalize: [-MOD, MOD**2] -> [0, MOD)
    ModInt(const long long _v = 0) : v((_v < 0) ? _v % MOD + MOD : _v % MOD) {}

    M operator+(const M& x) const { return M(v + x.v); }
    M operator-(const M& x) const { return M(v - x.v); }
    M operator*(const M& x) const { return M(v * x.v); }
    M operator/(const M& x) const { return M(v * x.inv().v); }
    M& operator+=(const M& x) { return *this = *this + x; }
    M& operator-=(const M& x) { return *this = *this - x; }
    M& operator*=(const M& x) { return *this = *this * x; }
    M& operator/=(const M& x) { return *this = *this / x; }
    bool operator==(const M& x) const { return v == x.v; }
    bool operator!=(const M& x) const { return v != x.v; }
    friend istream& operator>>(istream& input, M& x) {
        return input >> x.v, x = M(x), input;
    }
    friend ostream& operator<<(ostream& output, const M& x) {
        return output << x.v;
    }
    inline M pow(long long n) const {
        M x(v), res(1);
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    inline M inv() const { return this->pow(MOD - 2); }
    static void build(int n) {
        fact.assign(n + 1, 1);
        for (int i = 1; i < n + 1; i++) fact[i] = fact[i - 1] * M(i);
        finv.assign(n + 1, fact[n].inv());
        for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * M(i);
    }
    static M comb(int n, int k) {
        if (n < k || k < 0) return M(0);
        return fact[n] * finv[n - k] * finv[k];
    }
    static M extgcd(int a, int b, int& x, int& y) {
        M d(a);
        if (b) {
            d = extgcd(b, a % b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1;
            y = 0;
        }
        return d;
    }
};
vector<ModInt> ModInt::fact = vector<ModInt>();
vector<ModInt> ModInt::finv = vector<ModInt>();
long long ModInt::MOD = 1e9 + 7;

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

    set<int> s;
    for (int i = 1; i * i <= n; i++) {
        s.insert(i);
        s.insert(n / i);
    }

    vector<int> v(begin(s), end(s));
    int m = v.size();
    vector<int> num(m);
    for (int i = 0; i < m - 1; i++) {
        int l = n / v[i + 1];
        int r = n / v[i];
        num[i] = r - l;
    }
    num[m - 1] = 1;

    vector<vector<ModInt>> dp(k + 1, vector<ModInt>(m, 0));
    dp[0][m - 1] = 1;
    for (int i = 0; i < k; i++) {
        for (int j = m - 2; j >= 0; j--) dp[i][j] += dp[i][j + 1];
        for (int j = 0; j < m; j++) {
            dp[i + 1][j] += dp[i][m - 1 - j] * num[j];
        }
    }
    ModInt ans = 0;
    for (int j = 0; j < m; j++) ans += dp[k][j];
    cout << ans << endl;
}

Measured memory_bytes: 57200
n = gets.chomp.to_i
positions = [[0, 0, 0]]
n.times do
    positions.push(gets.chomp.split(' ').map(&:to_i))
end
def odd?(num)
    num % 2 != 0
end
1.upto(n) do |i|
    diff = (positions[i][1] - positions[i-1][1]).abs + (positions[i][2] - positions[i-1][2]).abs
    time = (positions[i][0] - positions[i-1][0]).abs
    if odd?(time) != odd?(diff) || diff > time
        puts 'No'
        exit
    end
end
puts 'Yes'

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

int N, M, X;
int A[101];

int main() {
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		cin >> A[i];
	}

	int ans1 = 0;
	for (int i = X; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (i == A[j]) ans1++;
		}
	}

	int ans2 = 0;
	for (int i = X; i >= 0; i--) {
		for (int j = 0; j < M; j++) {
			if (i == A[j]) ans2++;
		}
	}

	cout << min(ans1, ans2) << endl;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main(int argc, char *argv[]) {
	int l[10], v1, v2;
	while (EOF != scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
	&l[0],&l[1],&l[2],&l[3],&l[4],&l[5],&l[6],&l[7],&l[8],&l[9],&v1,&v2)) {
		// sum
		int sum = 0;
		for (int i=0;i<10;i++) sum+=l[i];
		// 1's length
		float ans = (float)(sum)*(float)(v1)/(float)(v1+v2);
		//printf("%f\n",ans);
		// calc
		int tmp = 0;
		for (int i = 0; i < 10; i++) {
			tmp += l[i];
			if (ans <= tmp) {
				printf("%d\n",i+1);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

reverse = 0
pre = []
after = []
S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q[0] == '1':
        reverse = 1 - reverse
    else:
        T, F, C = q.split()
        if (F == '1') ^ (reverse == 1):
            pre.append(C)
        else:
            after.append(C)
if reverse:
    after.reverse()
    ans = ''.join(after) + S[::-1] + ''.join(pre)
else:
    pre.reverse()
    ans = ''.join(pre) + S + ''.join(after)
print(ans)


Measured memory_bytes: 62428
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int N;cin >> N;
    vector<ll> A(N),B(N);
    rep(i,N)cin >> A[i] >> B[i];
    ll res = 0;
    for(int i=N-1;i>=0;i--){
        A[i]+=res;
        if(B[i]!=1&&A[i]%B[i]!=0)res += B[i]-(A[i]%B[i]);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

#define DEBUG

#ifdef DEBUG
#define var_dump(...) fprintf(stdout, __VA_ARGS__)
#define dump(a) cout << a << "\n";
#else
#define var_dump(...) 42
#define dump(a) 42
#endif

//https://beta.atcoder.jp/contests/abc044/tasks/abc044_b 

int main() {

    string w; cin >> w;
    map<char, int> mp;

    REP(i, w.length()) {
        mp[w[i]]++;
    }

    for(map<char, int>::iterator it = mp.begin(), end = mp.end(); it != end; ++it) { // it->first, it->second
        if (it->second % 2 != 0) {
            cout << "No" << "\n";
            return 0;
        }
    }

    cout << "Yes" << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define MAXN 1000000007
using namespace std;
long long n,a[200010],b[200010],sum=0,ans=0;
int main(){
	scanf("%d",&n);
	b[0]=0;
	for(register int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum=(sum+a[i])%MAXN;
		b[i]=(b[i-1]+a[i])%MAXN;
	}
	for(register int i=1;i<n;i++){
		long long use=(sum+MAXN-b[i])%MAXN;
		ans=(ans+(use*a[i])%MAXN)%MAXN;
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 6892
import numpy as np
H,W = list(map(int,input().split()))
data = [input().strip().split() for _ in range(H)]
data_ = np.array([list(str(data[i])) for i in range(H)])[:,2:-2]

d = [[0,1],[1,0],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]

for y in range(H):
	for x in range(W):

		if data_[y][x] == '#':
			continue

		count = 0
		for dy,dx in d:
			if 0 <= y+dy < H and 0 <= x+dx < W and data_[y+dy][x+dx] == '#':
				count += 1

		data_[y][x] = count

[print(''.join(i) ) for i in data_]

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

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

    vector<int> p(N);
    for (int &x : p)
    {
        cin >> x;
    }

    vector<int> sorted(p);
    sort(sorted.begin(), sorted.end());

    int count = 0;
    for (int i = 0; i < N; i++)
    {
        if (p[i] != sorted[i])
        {
            count++;
        }
    }
    if (count <= 2)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

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

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }

main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <pii> a(n);
    for (auto &i : a) cin >> i.x >> i.y;
    vector <int> p(n);
    ld ans = 0, cnt = 0;
    for (int i = 0; i < n; i++) p[i] = i;
    do {
        ++cnt;
        for (int i = 0; i + 1 < n; i++) {
            ans += sqrt(sqr(a[p[i]].x - a[p[(i + 1) % n]].x) + sqr(a[p[i]].y - a[p[(i + 1) % n]].y));
        }
    } while (next_permutation(all(p)));
    cout << fixed;
    cout.precision(10);
    cout << ans / cnt << '\n';
}


Measured memory_bytes: 3812