akhauriyash/Code-Regression huggingface dataset:
/*Coded by::
    **Avinash Tiwary**
    **BE/10298/2015**
    **Production Engineer**
    **Producing <code>**
*/
#include<bits/stdc++.h>
#define buf ios_base::sync_with_stdio (0), cin.tie (0)
typedef long long ll;
typedef double dob;
#define MAX 50010
#define M5 500009
#define M6 2000009
#define M 1000000007
#define inf LLONG_MAX
using namespace std;
typedef vector<ll> V;
typedef queue<ll > Q;
typedef stack<ll> S;
typedef pair<ll,ll> P;
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
ll fac[M6],not_prime[M6],ar[M6];
ll power(ll x,ll n,ll p)
{   if(n==0) return 1;
    else if(n%2 == 0) return power((x*x)%p,n/2,p);
    else return (x*power((x*x)%p,(n-1)/2,p))%p;
}
void fact(){
    fac[0]=1;
    for(ll i=1;i<21;i++) fac[i]=(i*fac[i-1]);
}
void sieve(){
    not_prime[1]=1; not_prime[0]=1;
    for(ll p=2;p*p<M6;p++){
        if(!not_prime[p]){
            for(ll i=p*2;i<=M6;i+=p) not_prime[i]=1;
        }
    }
}
ll modi(ll a, ll m){
    ll m0 = m, t, q; ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1){  q = a / m; t = m; m = a % m, a = t;t = x0;x0 = x1 - q * x0; x1 = t;}
    if (x1 < 0) x1 += m0;return x1;
}
ll red[101],blue[101],ub[101],ur[101];
int main(){
    buf; 
    //sieve(); 
    fact();
    ll i,j,k,test,flag,ans,n,p,m,t,a,b,c; string s1;
    //cin>>test;
    test=1;
    while(test--){
        cin>>s1;
        for(i=0;i<s1.size();i++){
            if(s1[i]=='A'&&s1[i+1]=='C'){ cout<<"Yes"; return 0;}
        }
        cout<<"No";
    }
    return 0;
} 

Measured memory_bytes: 2304
#include<cstdio>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
char n[100];
char word[105];
int main()
{
    scanf("%s",word);
    int lo=strlen(word);
    int cnt=0;
    for(int i=0;i<lo;++i)
    {
        if(word[i]!='1')
            break;
        cnt++;
    }
    long long k;
    cin>>k;
    if(k<=cnt)
        printf("1\n");
    else
        printf("%c\n",word[cnt]);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>

ll H,A;
int main(){
    cin>>H>>A;
    ll cnt=0;
    while(H>0){
        H-=A;
        cnt++;
    }
    cout<<cnt;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; double T, A;
    cin >> N >> T >> A;
    double x = 10000000;
    int ans = -1;
    for(int i = 0; i < N; i++) {
        double H;
        cin >> H;
        if(abs(A-(T - H*0.006))<x) {
            x = abs(A-(T - H*0.006));
            ans = i+1;
        }
    }
    cout << ans << endl;
}


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


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

lli A[200001] = {};
lli ans[200001] = {};


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

	for (int i = 1; i <= N; i++)
		cin >> A[i], ans[i] = -1;

	for (int i = N; i > 0; i--) {
		lli count = 0;
		for (int k = 2 * i; k <= N; k += i) {
			count += ans[k];
		}

		ans[i] = (count + A[i]) % 2;
	}

	lli count = 0;

	for (int i = 1; i <= N; i++)
		if (ans[i] == 1)count++;

	COUT(count);
	for (int i = 1; i <= N; i++) {
		if (ans[i] == 1)
			cout << i << (i == N ? "\n" : " ");
	}

	return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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; }


#define MAX_N 200000
int par[MAX_N+1]; //親
int ran[MAX_N+1]; //木の深さ

//n要素で初期化
void init(int n) {
    rep(i,n) {
		par[i] = i; ran[i] = 0;
	}
}

//木の根を求める
int root(int x){ return par[x]==x ? x : par[x]=root(par[x]); }

//x,yの属する集合の併合
void unite(int x, int y) {
	x = root(x); y = root(y);
	if(x == y) return ;

	if(ran[x] < ran[y]) par[x] = y;
	else {
		par[y] = x;
		if(ran[x] == ran[y]) ran[x]++;
	}
}

//x,yが同じ集合に属するか
bool same(int x, int y) { return root(x) == root(y); }

#define MAXE 100005
struct edge { int u, v; ll cost; };
bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

edge es[2*MAXE];
int V, E;

ll kruskal() {
    sort(es, es+2*E, comp);
    init(V);
    ll res = 0;
    rep(i,2*E) {
        edge e = es[i];
        if(!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}


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

    cin >> V; E = V - 1;

    vector<l_l> x(V), y(V);
    rep(i,V) {
        ll a, b; cin >> a >> b;
        x[i].fs = a; x[i].sc = i;
        y[i].fs = b; y[i].sc = i;        
    }
    sort(all(x)); sort(all(y));
    rep(i,E) {
        es[i] = (edge) { x[i].sc, x[i+1].sc, abs( x[i].fs - x[i+1].fs ) };
        es[i+E] = (edge) { y[i].sc, y[i+1].sc, abs( y[i].fs - y[i+1].fs ) };
    }

    cout << kruskal() << endl;
    return 0;
}



Measured memory_bytes: 7680
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def lcm(a, b):
    gcd = fractions.gcd
    n_gcd = gcd(a, b)
    return a * b // n_gcd

def main():
    N = I()
    T = []
    for _ in range(N):
        T.append(I())
    n_lcm = lcm(T[0], T[0])
    for i in range(1, N):
        n_lcm = lcm(n_lcm, T[i])
    print(n_lcm)
main()



Measured memory_bytes: 6352
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

calc :: [Int] -> [Int] -> Int -> Int -> Int
calc [] [] _ s = s
calc [a] [] b' s = calc [] [] 0 (s + minimum [a, b'])
calc (a : as) (b : bs) b' s = calc as bs b'' s'
  where
    a' = minimum [a, b']
    ax = a - a'
    bx = minimum [ax, b]
    b'' = b - bx
    s' = s + a' + bx

main = do
  n <- getInt
  as <- getIntList
  bs <- getIntList
  print $ calc as bs 0 0


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

int main()
{
    long long n,i,j,k=0,mod=1e9+7;
    cin>>n;
    vector<long long> a(n),pref(n+1);
    pref[0]=0;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        pref[i+1]=pref[i]+a[i];
        pref[i+1]%=mod;
    }
    for(i=n-1;i>0;i--)
    {
        //cout<<a[i]<<" "<<pref[i-1]<<'\n';
        k=(k+(a[i]*pref[i])%mod)%mod;
    }
    cout<<k<<'\n';
  return 0;
}


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

using namespace std;

const char en = '\n';
using  ll =          long long;
using ull = unsigned long long;

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

const ll INFL = 810000001919114514;
const int INF =         1919114514;

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

	deque<int> v;

	int buf;
	REP(i, 28){
		cin>>buf;
		v.push_back(buf);
	}

	sort(v.begin(),v.end());

	FOR(i,1,31){
		if(i!=v.front()){
			cout<<i<<en;
		} else{
			v.pop_front();
		}
	}

	return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = 1e9 + 7;
const int INF = 1e9;
int main() {
	cin.sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<int>num(N + 1);
	int cnt = 0;
	rep(i, N) {
		int A;
		cin >> A;
		if (num[A] == 0)cnt++;
		num[A]++;
	}
	int x = cnt - K;
	int ans = 0;
	if (x <= 0)cout << 0 << endl;
	else {
		sort(num.begin(), num.end());
		rep(i, N) {
			if (num[i] != 0) {
				ans += num[i];
				x--;
			}
			if (x == 0) {
				cout << ans << endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cmath>

using namespace std;

double Calculate(double n);

int main(){
  double n, sum;
  while(1){
    cin >> n;
    if(n == 0) break;
    sum = Calculate(n/2);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(0);
    cout << sum << endl;
  }
  return 0;
}

double Calculate(double n){
  double i, m, x, y, sum;

  if(modf(sqrt(n), &m) != 0) ++m;
  if(m == n){
    m = 2*n;
    return 2*m*m + 8*m;
  }
  for(i=m-1, y=m, sum=0; i>=1; --i){
    if(modf(n/i, &x) != 0) ++x;
    sum += (i+1)*(x-y);
    y=x;
  }
  return 8*(m*m + 2*sum) + 16*n;
}

Measured memory_bytes: 1280
use std::io;
use std::str::FromStr;

fn input_tuple() -> (u64, u64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn input_vec() -> Vec<u64> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn main() {
    let (n, m) = input_tuple();
    let a_vec = input_vec();
    let mut sum = 0;
    for a in a_vec {
        sum += a;
    }
    if n < sum  {
        println!("-1");
    } else {
        println!("{}", n - sum);
    }
}


Measured memory_bytes: 2264
from collections import defaultdict
from math import gcd

def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    zero = 0
    d = defaultdict(lambda: defaultdict(int))
    for i in range(N):
        A, B = map(int, input().split())
        if A == 0 and B == 0:
            zero += 1
            continue
        if B < 0:
            A = -A
            B = -B
        flag = False
        if A <= 0:
            A, B = B, -A
            flag = True
        g = gcd(A,B)
        A //= g
        B //= g
        if flag:
            d[(A,B)]['first'] += 1
        else:
            d[(A,B)]['second'] += 1
    ans = 1
    for i, j in d.items():
        now = 1
        now += pow(2,j['first'],MOD) - 1
        now += pow(2,j['second'],MOD) - 1
        ans *= now
        ans %= MOD
    ans -= 1
    ans += zero
    ans %= MOD
    print(ans)




    

if __name__ == "__main__":
    main()

Measured memory_bytes: 181588
#include<stdio.h>
#include<stdlib.h>
int int_sort(const void *,const void *);
int main(void){
  
  int N,a[200001],i,j,w;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
  }

  qsort(( void * )a , N , sizeof( int )
                       , int_sort );
 
  for(i=0;i<N-1;i++){
    if(a[i]==a[i+1]){
      printf("NO\n");
      return 0;
    }
  }
 printf("YES\n");
}



int_sort( const void * a , const void * b ) {
  /* 引数はvoid*型と規定されているのでint型にcastする */
  if( *( int * )a < *( int * )b ) {
    return -1;
  }
  else
  if( *( int * )a == *( int * )b ) {
    return 0;
  }
  return 1;
}

Measured memory_bytes: 1788
// AOJ DPL_3_A Largest Square
// 2018.5.4 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

short dp[1405][1405];
char map[1405][1405];

int main()
{
	int H, W, r, c, t, ans;

	H = in(), W = in();
	for (r = 1; r <= H; r++) for (c = 1; c <= W; c++) {
		map[r][c] = gc() & 0xf, gc();
	}

	ans = 0;
	for (r = 1; r <= H; r++) for (c = 1; c <= W; c++) {
		if (map[r][c]) dp[r][c] = 0;
		else {
			t = dp[r-1][c-1];
			if (t > 0 && dp[r  ][c-1] < t) t = dp[r  ][c-1];
			if (t > 0 && dp[r-1][c  ] < t) t = dp[r-1][c  ];
			dp[r][c] = ++t;
			if (t > ans) ans = t;
		}
	}
	printf("%d\n", ans*ans);
	return 0;
}



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

int main() {
	string a ;
  	cin >> a ;
	int count=0;
  	if(a.at(0)=='1') count++;
  	if(a.at(1)=='1') count++;
  	if(a.at(2)=='1') count++;
  	cout << count <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100000

int a[NMAX+1];
int len;
int Lent[NMAX+1];

int main() {
	int n,i,j;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++) scanf("%d",&a[i]);
	
	Lent[0]=a[0];
	len=1;
	
	for(i=1;i<n;i++) {
		if(Lent[len-1]<a[i]) {
			Lent[len++]=a[i];
		} else {
			*lower_bound(Lent,Lent+len,a[i])=a[i];
		}
	}
	
	printf("%d\n",len);
	
	return 0;
}


Measured memory_bytes: 3940
#include<iostream>
#include<algorithm>

using namespace std;

void dump(int a[],int n){
	for(int i=0;i<n;i++){
		cout << a[i] << (i==n-1?"\n":" ");
	}
}

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

	int n; cin >> n;
	int a[n];
	long long sum=0;
	for(int i=0;i<n;i++){
		cin >> a[i];
		sum+=a[i];
	}
	sort(a,a+n,greater<int>());
	long long b=0;
	int i=0;
	for(;i<n-1;i++){
		sum-=a[i];
		if(2*sum < a[i]){
//			cout << "break " << i << "\n";
			break;
		}
	}

//	dump(a,n);

	cout << i+1 << "\n";
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define PI 3.14159265358979323
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
      FastIO
      string s;
      cin >> s;
      lld n, i;
      n = s.length();
      lld c = 0;
      for(i = 0; i < (n/2); i++)
      {
            if (s[i] !=s[n-i-1])
            {
                  c++;
            }
      }
      cout<< c;
      return 0;
}

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

int main()
{
  int m , n , ans1 , ans2 , N , K ;
  cin >> K >> N ;
  int A[N] ;
  ans1 = 0 ;

  for(m=0;m<N;m++){
    cin >> A[m];}
  
  for(m=1;m<N;m++){
    if(A[m]-A[m-1] > ans1 )
		ans1 = A[m] - A[m-1];}
  if(K-A[N-1]+A[1] > ans1)
    ans1 = K - A[N-1] + A[0];
  
  cout << K - ans1 ;
  
return 0;
}

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

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {

            //ABC085C


            var NY = ReadSplitInt();
            var N = NY[0];
            var Y = NY[1];


            for (int i = 0; i <= N; i++)
            {
                for (int j = 0; j <= N - i; j++)
                {
                    var k = N - i - j; 
                    bool p = Y == ((10000 * i) + (5000 * j) + (1000 * (k)));
                    if (p)
                    {
                        Console.WriteLine($"{i} {j} {k}");
                        return;
                    }

                }
            }

            Console.WriteLine("-1 -1 -1");


            Console.ReadKey();
        }



        #region MyRegion

        public static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        /// <summary>
        /// 空白区切の数値を取得する
        /// </summary>
        /// <returns>The read split int.</returns>
        public static int[] ReadSplitInt()
        {
            return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        }

        /// <summary>
        /// 空白区切の数値を取得
        /// </summary>
        /// <returns>The read split long.</returns>
        public static long[] ReadSplitLong()
        {
            return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        }


        public static int[][] ReadSplitIntLines(int n)
        {
            return Enumerable.Range(0, n).Select(x => ReadSplitInt()).ToArray();
        }

        public static long[][] ReadSplitLongLines(int n)
        {
            return Enumerable.Range(0, n).Select(x => ReadSplitLong()).ToArray();
        }

        public static long[][] ReadSplitLongLines(long n)
        {
            var ret = new List<long[]>();
            for (long i = 0; i < n; i++)
            {
                ret.Add(ReadSplitLong().ToArray());
            }

            return ret.ToArray();
        }

        #endregion

    }
}


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

#define ll long long

template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

void solve() {
  int a,b,c; cin >> a >> b >> c;
  
  cout << (b-a==c-b?"YES":"NO") << '\n';

  return;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T=1;
  //cin >> T;
  while(T--) solve();

  return 0;
}


Measured memory_bytes: 3644
import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {

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

        int t = b - a;
        int tt = (t + 1) * t / 2;


        System.out.println(tt - b);





    }
}

Measured memory_bytes: 22608
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size(), ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int flag = 0;
            for (int k = i; k < j+1; k++) {
                if (!(s[k] == 'A' || s[k] == 'C' || s[k] == 'G' || s[k] == 'T')) flag = 1;
            }
            if (flag == 0 && j-i+1 > ans) {
                    ans = j-i+1;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int dp[100000];
int s[100000];

int main() {
	int x;
	cin >> x;
	REP(i, 100000) {
		int k = i;
		while (k) {
			s[i] += k % 10;
			k /= 10;
		}
	}
	priority_queue<PII, vector<PII>, greater<PII>> q;
	memset(dp, 0x7f, sizeof(dp));
	int ans = 0x7f7f7f7f;
	FOR(i, 1,10) {
		int n = x * i;
		q.push(MP( n % 10, n / 10));
	}
	while (!q.empty()) {
		auto tmp = q.top();
		q.pop();
		if (dp[tmp.second] < tmp.first)continue;
		ans = min(ans, s[tmp.second] + tmp.first);
		REP(i, 10) {
			int n = x * i + tmp.second;
			int k = n % 10 + tmp.first;
			if (dp[n / 10] > k) {
				dp[n / 10] = k;
				q.push(MP(k, n / 10));
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
	string s; cin >> s;
	long long ans = 0, tmp;
	for (int b = 0; b < (1 << s.size() - 1); b++) {
		tmp = s[0] - '0';
		for (int i = 0; i < s.size() - 1; i++) {
			if (b & (1 << i)) {
				ans += tmp;
				tmp = 0;
			}
			tmp = tmp * 10 + s[i + 1] - '0';
		}
		ans += tmp;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import math

def readInts():
  return [int(s) for s in input().split(" ")]

def isDistanceInt(X1, X2):
  d = 0
  for i in range(len(X1)):
    d += (X1[i] - X2[i]) ** 2

  dr = int(math.sqrt(d))
  return dr ** 2 == d

def main():
  N, D = readInts()
  Xs = [readInts() for _ in range(N)]
  ans = 0
  for i in range(N-1):
    for j in range(i+1, N):
      if isDistanceInt(Xs[i], Xs[j]):
        ans += 1
  print(ans)


if __name__ == "__main__":
  main()


Measured memory_bytes: 3064
from collections import deque

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0

for si in range(H):   #スタート位置の設定
    for sj in range(W):
        if S[si][sj] == '#':
            continue       # continue はスキップ
        q = deque([(si, sj)])
        dist = [[INF] * W for _ in range(H)]
        dist[si][sj] = 0
        while q:
            i, j = q.popleft()
            for d in range(4):
                ni = i + di[d]      # 右　左　上　下　入力
                nj = j + dj[d]
                if (ni < 0 or ni >= H or nj < 0 or nj >= W):
                    continue
                if S[ni][nj] == '#':     #壁があったらスキップ
                    continue
                if dist[ni][nj] != INF:  #探索済みかどうか
                    continue
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1

        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    ans = max(ans, dist[i][j])
print(ans)

Measured memory_bytes: 3316
#include "bits/stdc++.h"
using namespace std;
#define int long long

signed main() {
	int n;
	cin >> n;
	int N = sqrt(n);

	int ans = INT_MAX;

	for ( int i = 1; i <= N; i++ ) {
		if ( n % i == 0 ) {
			int a = i, b = n / i;
			int digit = max(to_string(a).size(), to_string(b).size());
			ans = min(digit, ans);
		}
	}

	cout << ans << endl;

}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

ll rec(ll n, ll x)
{
    if (n == 0)
        return 1;
    ll a = (1LL << (n + 1)) - 3;
    ll p = (1LL << n) - 1;
    if (x == 1)
        return 0;
    else if (x <= a + 1)
        return rec(n - 1, x - 1);
    else if (x == a + 2)
        return p + 1;
    else if (x <= 2 * a + 2)
        return p + 1 + rec(n - 1, x - a - 2);
    else if (x == 2 * a + 3)
        return 2 * p + 1;
}

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

    OP(rec(n, x));

    return 0;
}

Measured memory_bytes: 256
from functools import reduce
import fractions
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
n = int(input())

inp_list = list(map(int,(input().split())))

lcm = lcm_list(inp_list)

ans = 0
mod = 10**9+7

for i in inp_list:
    ans += lcm // i



print(ans % mod)


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

using namespace std;

// 平行四辺形状の領域に入ってからの移動距離
long long f(long long yoko, long long tate) {
    long long y = yoko, t = tate;
    if (y < t) swap(y, t);
    if (y % t == 0) { // このときはゴールできる
        return 2LL * y - t;
    } else {
        return f(y % t, t - y % t) + 2LL * y;
    }
}

int main() {
    long long n, x;
    cin >> n >> x;

    cout << n + f(x, n - x) << endl;
    return 0;
}

Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int V, E;
struct edge { LL to, cost; };
int start;
LL d[100100]; //距離
vector<edge> vec[101010];

void dijkstra() {
	for (int i = 0; i < 100100; i++)d[i] = HINF<LL>();
	priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
	d[start] = 0;
	pq.push(make_pair(d[start], start));//cost,to
	while (!pq.empty()) {
		pii p = pq.top();
		pq.pop();
		int i = p.second;
		if (d[i] < p.first)continue;
		for (int k = 0; k < vec[i].size(); k++) {
			edge e = vec[i][k];
			if (d[e.to] <= d[i] + e.cost)continue;
			d[e.to] = d[i] + e.cost;
			pq.push(make_pair(d[e.to], e.to));
		}
	}
}

int main() {
	cin >> V;
	REP(i, V) {
		int u;
		cin >> u;
		int num;
		cin >> num;
		REP(j, num) {
			int v, c;
			cin >> v >> c;
			vec[u].emplace_back(edge{ v,c });
		}
	}
	dijkstra();
	REP(i, V) {
		cout << i << " " << d[i] << endl;
	}
}


Measured memory_bytes: 15004
#include<iostream>
using namespace std;
const int MAX = 200001;
int main(){
	int N,A[MAX];
	long long int sum[MAX][3],ans=0;
	bool visit[MAX][3]={0};
	cin>>N;
	for(int i=0;i<N;i++)cin>>A[i];
	for(int i=0;i<N-N%2;i+=2)ans+=A[i];
	
	if(N<=3){
		ans=A[0];
		for(int i=1;i<N;i++){
			if(ans<A[i])ans=A[i];
		}
		cout<<ans;
		return 0;
	}
	
	if(N%2){
		sum[0][2]=A[0];visit[0][2]=true;
		sum[1][1]=A[1];visit[1][1]=true;
		sum[2][0]=A[2];visit[2][0]=true;
	}else{
		sum[0][1]=A[0];visit[0][1]=true;
		sum[1][0]=A[1];visit[1][0]=true;
	}

	for(int i=0;i+2<N;i++)for(int j=0;j<3;j++){
		if(!visit[i][j])continue;
		for(int k=0;k<=min(j,N-i-3);k++){
			if(visit[i+2+k][j-k])sum[i+2+k][j-k]=max(sum[i+2+k][j-k],sum[i][j]+A[i+2+k]);
			else sum[i+2+k][j-k]=sum[i][j]+A[i+2+k];
			visit[i+2+k][j-k]=true;
			if(i+2+k>=N-(j-k+1))ans=max(ans,sum[i+2+k][j-k]);
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 9680
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def to_list(v):
    b = bin(v)
    l = []
    for i, flg in enumerate(reversed(b[2:])):
        if flg == '1':
            l.append(i)
    return l

def check(field, hl, wl):
    count_black = 0
    #print('hl', 'wl', hl, wl) # debug
    for h in hl:
        for w in wl:
            if field[h][w] == '#':
                count_black += 1
    #print('count_black', count_black) # debug
    return count_black


def solve(field, h, w, k):
    mh = 2 ** h
    mw = 2 ** w
    whole = check(field, to_list(mh - 1), to_list(mw - 1))
    #print('whole') # debug
    #print(whole) # debug
    #
    count = 0
    for hh in range(mh):
        hl = to_list(hh)
        if len(hl) == 0:
            continue
        for ww in range(mw):
            wl = to_list(ww)
            if len(wl) == 0:
                continue
            kk = check(field, hl, wl)
            if k == kk:
                count += 1
    return count



if __name__ == '__main__':
    h, w, k = list(map(int, input().split()))
    field = []
    for _ in range(h):
        l = input()
        field.append(l)
    ans = solve(field, h, w, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef map<ll, ll> mii;
const int MOD = 1e9 + 7;

#define fastIO() \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 

ll N;
vector<vi> a, dp;

ll solve(ll n, ll k) {
    //(n + 1) bits are set in k
    if (dp[n][k] >= 0)  return dp[n][k];
    if (!(k&(k-1)) && n == 0)   return dp[0][0] = a[0][__builtin_ctzll(k)];
    dp[n][k] = 0;
    for (int r = 0; r < N; ++r) {
        if ((k & (1ll << r)) && a[n][r]) {
            //rth bit is set
            int k_r = k ^ (1ll << r);
            if (dp[n - 1][k_r] != -1)
                dp[n][k] = (dp[n][k] + dp[n - 1][k_r]) % MOD;
            else
                dp[n][k] = (dp[n][k] + solve(n - 1, k_r)) % MOD;
        }
    }
    return dp[n][k];
}

int main() {
    ll n;
    cin >> N;
    n = N;
    a.resize(n, vi(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    dp.resize(n, vi(1ll << n, -1));
    ll ans = solve(n - 1, (1ll << n) - 1);
    cout << ans << endl;
    return 0;
}


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

int par[100001];
void init(int n){
    for(int i = 1; i <= n; i++)par[i] = i;
}
int root(int x){
    if(par[x] == x){
        return x;
    }
    else{
        return par[x] = root(par[x]);
    }
}
bool same(int x, int y){
    return root(x) == root(y);
}
void unite(int x, int y){
    int v, w;
    v = root(x);
    w = root(y);
    if(v==w)return;

    par[v] = w;
}
int main(){
    int n, m;
    cin >> n >> m;
    init(n);
    int p[n+1];
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    int x, y;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        unite(x, y);
    }
    for(int i = 1; i <= n; i++){
        root(i);
    }
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(par[p[i]] == par[i]) sum++;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
#include"bits/stdc++.h"
#include<iostream>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i, c) for(int i = 0; i < (int)c; i++)
const ll inf = 1000000007;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n) {
		cin >> a[i];
	}
	
	rep(i, n) {
		if (a[i]%2==0 && (a[i] % 3 != 0 && a[i] % 5 != 0)) {
			cout << "DENIED" << endl;
			return 0;
		}
	}

	cout << "APPROVED" << endl;
	return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <cstring>
char s[200050];
int main()
{
  scanf("%s",s);
  int len=strlen(s);
  for(int i=0;i<len;++i)
    if(s[i]=='?')
      s[i]='D';
  printf("%s\n",s);
  return 0;
}

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

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

	vector<int> P(N);
	rep(i,N) cin >> P.at(i);

	int tmp = 200001,ans=0;
	rep(i,N){
		if(P.at(i) < tmp){
			ans++;
			tmp = P.at(i);
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 4028
#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
inline ll read(){
	ll x=0; bool f=1; char c=getchar();
	for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
	for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
	if(f) return x;
	return 0-x;
}
int n,m,top; ll a[N],ans[N];
struct scx{
	ll x,coe;
	inline bool operator <(const scx& a)const{
		return x<a.x;
	}
}; priority_queue<scx> pq;
int main(){
	n=a[0]=read(), m=read();
	ll x;
	for(int i=1; i<=m; ++i){
		x=read();
		while(top && a[top]>=x) --top;
		a[++top]=x;
	}
	pq.push((scx){a[top],1});
	for(int i=top-1; i>=0; --i){
		ll tmp = 0; scx u = pq.top();
		while(u.x>a[i]){
			pq.pop();
			tmp += (u.x/a[i])*u.coe, u.x %= a[i];
			if(u.x) pq.push(u);
			if(pq.empty()) break;
			u = pq.top();
		}
		if(tmp) pq.push((scx){a[i],tmp});
	}
	while(!pq.empty()){
		scx u = pq.top(); pq.pop();
		ans[u.x] += u.coe;
	}
	for(int i=n-1; i>=1; --i) ans[i]+=ans[i+1];
	for(int i=1; i<=n; ++i) printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 4976
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        if(a+b==0)printf("Impossible\n");
        else if((a+b)%3==0||a%3==0||b%3==0)printf("Possible\n");
        else printf("Impossible\n");
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<long double,long double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<61;
const double pi=acos(-1);
const double eps=1e-10;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n,x,y;
string s;
vi X,Y;

bool f(vi a,int t){
	set<int> st;
	st.insert(0);
	for(int i=0;i<a.size();i++){
		set<int> ST;
		for(auto it=st.begin();it!=st.end();it++){
			ST.insert(*it+a[i]);
			ST.insert(*it-a[i]);
		}
		st=ST;
	}
	return st.find(t)!=st.end();
}

int main(){
	cin>>s>>x>>y;
	s+='T';
	n=s.size();
	bool b=0;
	int I=-1;
	for(int i=0;i<n;i++) if(s[i]=='T'){
		if(!b) X.push_back(i-I-1);
		else Y.push_back(i-I-1);
		I=i;
		b^=1;
	}
/*	for(int i=0;i<X.size();i++) cout<<X[i]<<' ';
	cout<<endl;*/
	x-=X[0];
	X.erase(X.begin());
	if(f(X,x)&&f(Y,y)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;

namespace AGC001_A_BBQ_Easy
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			string[] l = Console.ReadLine().Split(' ');
			
			List<int> lArrs = new List<int>();

			for (int i = 0; i < 2 * n; i++)
			{
				lArrs.Add(int.Parse(l[i]));
			}
			
			lArrs.Sort();

			int countX = 0;

			for (int i = 0; i < 2 * n; i += 2)
			{
				countX += lArrs[i];
			}
			
			Console.WriteLine(countX);
		}
	}
}

Measured memory_bytes: 13140
import queue
n, m = map(int, input().split())
graph = [[] for i in range(n)]
depth = [-1] * n
route = []
result = [0] * (n - 1)
for i in range(m):
    temp = list(map(int, input().split()))
    graph[temp[0] - 1].append(temp[1] - 1)
    graph[temp[1] - 1].append(temp[0] - 1)
    route.append(temp)
q = queue.Queue()
q.put(0)
depth[0] = 0
for i in range(n-1):
    item = q.get()
    for j in graph[item]:
        if(depth[j] == -1):
            q.put(j)
            depth[j] = depth[item] + 1
print("Yes")
for i in route:
    if(i[0] == 1):
        result[i[1] - 2] = 1
    elif(i[1] == 1):
        result[i[0] - 2] = 1
    elif(depth[i[0] - 1] - depth[i[1] - 1] == 1):
        result[i[0] - 2] = i[1]
    elif(depth[i[1] - 1] - depth[i[0] - 1] == 1):
        result[i[1] - 2] = i[0]
for i in result:
    print(i)

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

int main(void)
{
	int N, i, cnt=0;
	char S[50];
	
	scanf("%d", &N);
	scanf("%s", S);
	
	for(i=0; i<N-2; i++){
		if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C'){cnt++;}
	}
	
	printf("%d", cnt);
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
const int INF = 1 << 20;

typedef long long ll;


 int dp[110][11010];

int main(){
  int n,w;
  cin >> n >> w;
 
  REP(i,n){

    int a,b;
    cin >> a >> b;
    REP(j,10010){
      dp[i+1][j] = max(dp[i][j],dp[i+1][j]);
      dp[i+1][j+b] = max(dp[i+1][j+b],dp[i][j]+a);
      dp[i][j+1] = max(dp[i][j],dp[i][j+1]);
    }
    
  }
  cout << dp[n][w] << endl;
  return 0;
}



Measured memory_bytes: 7412
mod = 10**9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

def CommomSubsequencesCount(s, t):

    n1 = len(s)
    n2 = len(t)
    dp = [[0 for i in range(n2 + 1)]
             for i in range(n1 + 1)]
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            if (s[i - 1] == t[j - 1]): 
                dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % mod
            else:
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % mod
    return dp[n1][n2]
ans = CommomSubsequencesCount(s, t)
ans += 1
ans %= mod
print(ans)

Measured memory_bytes: 74460
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node{
  int key;
  struct Node *right;
  struct Node *left;
  struct Node *parent;
};

struct Node *root;
struct Node *NIL;


struct Node *find(struct Node *u, int k){
  while (u != NIL && k != u->key){
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

void insert(int k){

  struct Node *y = NIL;
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));

  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x-> key) x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NIL) root = z;
  else{
    if(z->key < y->key) y->left = z;
    else y -> right = z;
  }
}

void inorder(struct Node *u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
 
  inorder(u->right);
}

void preorder(struct Node *u){
  if(u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){

  int n;
  int i,j;
  int x;
  
int count=0;
int cnt[10];
int tmp=0;

  struct Node *t;
  char *com;
  char *comin = "insert";
  char *compr = "print";

  com = (char*)malloc(7*sizeof(char));  

  scanf("%d", &n);

  for(i=0; i<n; i++){
    scanf("%s", com);
    if(com[0] == 'f'){
      scanf("%d", &x);
      t = find(root, x);
      if(t != NIL){
	printf("yes\n");
      }
      else{
	printf("no\n");
      }
    }
      else if(strncmp(com,comin,6)==0){
	scanf("%d",&x);
	insert(x);
      }
      else if(strncmp(com,compr,5)==0){

	inorder(root);
	printf("\n");
	preorder(root);
	printf("\n");
      }
    }

    return 0;
  }



Measured memory_bytes: 20552
N,K = map(int, input().split())
A = list(map(int, input().split()))
B ={}
for i in A:
    if i not in B.keys():
        B[i] = 1
    else:
        B[i] += 1
C = sorted(B.items(), key=lambda x: -x[1])
count = 0
while len(C) > K:
    a,b = C.pop()
    count += b
print(count)

Measured memory_bytes: 39092
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    A, B = map(int, input().split())

    if 1 <= A and A <= 9 and 1 <= B and B <= 9:
        print(A * B)
    else:
        print('-1')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public long n;
        public long a;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextLong();
            a = in.nextLong();
            long ans = n;
            for (int take = 1; take <= 40; take++) {
                BigInteger lo = BigInteger.valueOf(2);
                if (lo.pow(take).compareTo(BigInteger.valueOf(2 * n)) > 0) break;
                BigInteger hi = BigInteger.valueOf(n);
                while (lo.compareTo(hi) < 0) {
                    BigInteger mid = (lo.add(hi).shiftRight(1));
                    if (mid.pow(take + 1).compareTo(BigInteger.valueOf(n)) < 0) lo = mid.add(BigInteger.ONE);
                    else hi = mid;
                }
                long same = lo.longValue() - 1;
                BigInteger total = BigInteger.ONE;
                for (int i = 0; i <= take; i++) total = total.multiply(BigInteger.valueOf(same));
                long tmp = a * take + same * (take + 1);
                while (total.compareTo(BigInteger.valueOf(n)) < 0) {
                    total = total.divide(BigInteger.valueOf(same));
                    total = total.multiply(BigInteger.valueOf(same + 1));
                    tmp++;
                }
                ans = Math.min(ans, tmp);
            }

            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}



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

int BsearchQ(int A[],int n,int key){
	int l = 0;
	int r = n;
	while(l<r){
		int mid=(l+r)/2;
		if(A[mid]==key){
			return 1;
		}else if(A[mid]<key){
			l=mid+1; 		
		}else {
			r=mid;
		}
		
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n,A[100000+5],q,key,sum=0;
	
	cin>>n;
	for(int i=0;i<n;i++) cin>>A[i];
	
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>key;
		sum+=BsearchQ(A,n,key);
	} 
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3484
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
ll lc(ll a,ll b){
  return a/gcd(a,b)*b;
}
signed main(){
  init_io();
  ll n,m,l;
  cin >> n >> m;
  vector<ll> a(n),ad(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    ad[i] = a[i]/2;
  }
  l = ad[0];
  for(int i=1;i<n;i++){
      l = lc(ad[i],l);
      if(l>m) break;
  }
  if(l>m){
    cout <<"0\n";
  }else{
    ll v = m/l;
    if(v!=0){
      v = (v+1)/2;
    }
    for(int i=0;i<n;i++){
      ll tmp = l/ad[i];
        if(tmp%2==0){
          v = 0;
          break;
      }
    }
    cout << v<<endl;
  }
}


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

int main() {
  int A,B,C;
  cin >> A >> B;
  if (A > 9) {
    C = -1;
  } else if (B > 9) {
    C = -1;
  } else {
    C = A*B;
  }
  cout << C << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
int main()
{
    ll n ;
    cin >> n ;
    ll arr[n][3] , brr[n][3] ;
    
    for( ll i =0 ; i < n ;i++)
    {
        
        cin>>arr[i][0] >> arr[i][1] >>arr[i][2] ;
    }
    brr[n-1][0] = arr[n-1][0] ;
    brr[n-1][1] = arr[n-1][1] ;
    brr[n-1][2] = arr[n-1][2] ;
    
        
    
    for( ll i = n-2 ; i >=0 ;i-- )
    {
        brr[i][0] = max(brr[i+1][1] , brr[i+1][2]) +arr[i][0] ;
        brr[i][1] = max(brr[i+1][0] , brr[i+1][2]) +arr[i][1] ;
        brr[i][2] = max(brr[i+1][0] , brr[i+1][1]) +arr[i][2] ;
        
    }
    
    
    cout<<max(max(brr[0][0] , brr[0][1] ) ,brr[0][2]) ;
    
    
    return 0 ;
    
}

Measured memory_bytes: 4992
#include <stdio.h>
#include <math.h>

int main(void){
  unsigned int a, d, n;
  //unsigned int sosu[999999] = {0};
  unsigned int* sosu = new unsigned int[999999];
  unsigned int sosunum;

  unsigned int sqnum = (int)sqrt((double)999999);


  for(unsigned int i=0; i<999999; i++){
    sosu[i] = 1;
  }

  sosu[0] = 0;

  for(unsigned int i=1; i<sqnum; i++){
    if(sosu[i]==1){
      for(unsigned int j=i+1; (i+1)*j<=999999; j++){
	sosu[(i+1)*j-1] = 0;
      }
    }
  }

  while(1){
    sosunum = 0;
    scanf("%d%d%d", &a, &d, &n);
    if(a==0 && d==0 && n==0){
      break;
    }
    while(sosunum != n){
      if(sosu[a-1]){
	sosunum++;
      }
      a += d;
    }
    printf("%d\n", a-d);
  }
  return 0;
}

Measured memory_bytes: 4936
'use strict';
function main(input) {
  const arr = input.trim().split(' ');
  const a = Number(arr[0]);
  const b = Number(arr[1]);
  
  console.log(Math.ceil(a / (b * 2 + 1)));
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 8584