akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;  cin >> N  >> M;
    vector<int> div;
    for(int i=1; i*i<=M; i++){
        if(M%i==0){
            div.push_back(i);
            div.push_back(M/i);
        }
    }

    sort(div.begin(), div.end());
    int n = div.size();
    for(int i=n-1; i>=0; i--){
        if(div[i] <= M/N){
            cout << div[i] << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
import collections
n=int(input())
A=[int(i) for i in input().split()]
a=collections.Counter(A).most_common()[0][0]
AA=[i for i, x in enumerate(A) if x==a]
a1,a2,d=AA[0],AA[1],AA[1]-AA[0]

mod=10**9+7
n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

for i in range(n+1):
  ans=comb(n+1,i+1)%mod
  if 0<=i<=a1+n-a2:
    ans-=comb(a1+n-a2,i)
  print(ans%mod)



Measured memory_bytes: 73960
def read():
    A, B, C = list(map(int, input().strip().split()))
    return A, B, C

def solve(A, B, C):
    na = sorted([A, B, C])
    is_poor = False
    if na[0] == na[1] and na[1] < na[2]:
        is_poor = True
    elif na[0] < na[1] and na[1] == na[2]:
        is_poor = True
    return 'Yes' if is_poor else 'No'


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


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

// mod(2*K) の空間にして、2次元累積和する。
// K=3
// 	        x
// 	  0 1 2 3 4 5 6
// 	0 0 0 0|0 0 0|0
// 	1 0 # #|     |#
// 	  -----+-----+-
// y	2 0    |# # #| 
// 	3 0    |# # #| 
// 	4 0    |# # #| 
// 	  -----+-----+-
// 	5 0 # #|     |#
// 	6 0 # #|     |#


int bk[2020][2020];

int main() {
  int N, K;
  cin >> N >> K;
  REP(i,N) {
    int x,y; char c;
    cin >> x >> y >> c;
    // 白はKずらして黒にする
    if (c == 'W') y += K;
    bk[ (x%(2*K))+1 ][ (y%(2*K))+1 ]++;
  }
  // 二次元累積和
  for (int y=1; y<=2*K+1; y++)
    for (int x=1; x<=2*K+1; x++)
      bk[x][y] += bk[x][y-1];
  for (int x=1; x<=2*K+1; x++)
    for (int y=1; y<=2*K+1; y++)
      bk[x][y] += bk[x-1][y];

  int ans = 0;
  for (int y=1; y<=K; y++) {
    for (int x=1; x<=K; x++) {
      int num = bk[x-1][y-1];
      num += bk[2*K][2*K] - bk[2*K][y+K-1] - bk[x+K-1][2*K] + bk[x+K-1][y+K-1];
      num += bk[2*K][y-1] - bk[x+K-1][y-1];
      num += bk[x-1][2*K] - bk[x-1][y+K-1];
      num += bk[x+K-1][y+K-1] - bk[x+K-1][y-1] - bk[x-1][y+K-1] + bk[x-1][y-1];
      ans = max( num, ans );
      ans = max( N-num, ans );
    }
  }
  cout << ans << endl;
/*
  REP(y,2*K+1) {
    REP(x,2*K+1) {
      cout << bk[x][y] << " " ;
    }
    cout << endl;
  }
  */

}



Measured memory_bytes: 16000
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, I = get_ints

puts N - I + 1


Measured memory_bytes: 14420
#include <iostream>
#include <cstdio>
using namespace std;
int a[40][40],b[40][40],n,m,k,ans = 0;
string str[40];
void fall(int a[40][40])
{
    for (int j = 0;j < m;j++)
    {
        int bot = n-1,tmp[40];
        for (int i = n-1;i >= 0;i--)
        {
            tmp[i] = 0;
            if (a[i][j])
            {
                tmp[bot] = a[i][j];
                bot--;
            }
        }
        for (int i = n-1;i >= 0;i--) a[i][j] = tmp[i];
    }
}
int check(int a[40][40])
{
    int ret = 0;
    for (int i = 0;i < n;i++)
    {
        int num = 0,tot = 0;
        for (int j = 0;j < m;j++)
        {
            if (a[i][j] != num)
            {
                if (tot >= k)
                {
                    ret += tot*num;
                    for (int x = 1;x <= tot;x++) a[i][j-x] = 0;
                }
                tot = 1;
                num = a[i][j];
            } else tot++;
        }
        if (tot >= k)
        {
            ret += tot*num;
            for (int x = 1;x <= tot;x++) a[i][m-x] = 0;
        }
    }
    return ret;
}
int calc(int x,int y)
{
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            b[i][j] = a[i][j];
    b[x][y] = 0;
    fall(b);
    int ans = 0,c = 1;
    while (1)
    {
        int tmp = check(b);
        if (tmp == 0) break;
        ans += c*tmp;
        c *= 2;
        fall(b);
    }
    return ans;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 0;i < n;i++) cin >> str[i];
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            a[i][j] = str[i][j] - '0';
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
        {
            int tmp = calc(i,j);
            ans = tmp>ans?tmp:ans;
        }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;


int main()
{
 int n,m,c;
 cin >> n >> m >> c;
 int arr[m];
 int ans=0;
 for (int i=0;i<m;i++) cin >> arr[i];
 
 while(n--)
 {
     int subans =0;
     for(int i=0;i<m;i++)
     {
         int a;
         cin >> a;
         subans += a*arr[i];
     }
     subans +=c;
     if(subans>0) ans+=1;
 }
 cout << ans;
 return 0;
}

Measured memory_bytes: 384
#include <cstdio>

inline int abs(int x) {
	return (x > 0) ? x : -x;
}

int main()
{
	int N, x[100], y[100], h[100];
	int i, ix, iy, ic, ih, proh;
	bool ezero = 1;

	std::scanf("%d", &N);
	for (i = 0; i < N; i++) {
		std::scanf("%d %d %d", x+i+ezero, y+i+ezero, h+i+ezero);
		if (ezero && h[i+ezero]) {
			x[0] = x[i+ezero], y[0] = y[i+ezero], h[0] = h[i+ezero];
			ezero = 0;
		}
	}

	for (ix = 0; ix <= 100; ix++) {
		for (iy = 0; iy <= 100; iy++) {
			if (ezero)
				ih = 1;
			else
				ih = h[0] + abs(x[0] - ix) + abs(y[0] - iy);

			for (ic = 1; ic < N; ic++) {
				proh = ih - abs(x[ic] - ix) - abs(y[ic] - iy);
				(proh < 0) ? proh = 0 : 0;

				if (proh != h[ic])
					goto next;
			}

			std::printf("%d %d %d\n", ix, iy, ih);
			return 0;

		next:;
		}
	}
}

Measured memory_bytes: 128
{-# LANGUAGE BangPatterns #-}

solve :: (String, String) -> Int
solve (xss, yss) = lcs xss yss befMemo [0]
  where
    lcs [] _ memo _     = last memo
    lcs (x:xs) [] _  as = lcs xs yss (reverse as) [0]
    lcs xs ys (b:bs) as = lcs xs (tail ys) bs (m : as)
      where
        !m = if (head xs) == (head ys) then b + 1 else max (head as) (head bs)
    befMemo = replicate (length yss + 1) 0

main :: IO ()
main =  getLine
        >>  fmap lines getContents
        >>= toPair []
        >>= mapM_ (print . solve)
  where
    toPair pairs [] = return $ reverse pairs
    toPair pairs (xs:ys:rest) = toPair ((xs, ys) : pairs) rest



Measured memory_bytes: 7504
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld long double
#define pb push_back
#define fi0(i,n) for(int i=0; i<n; i++)
#define fi1(i,n) for(int i=1; i<n; i++)
#define fll0(i,n) for(long long i=0; i<n; i++)
#define fll1(i,n) for(long long i=1; i<n; i++)
#define vll vector<long long>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define N 1000000000000000000
int main()
   {
   	  ll n;
   	  cin>>n;
   	  vll v(n);
   	  ll zero=0;
   	  fll0(i,n)
   	    {
   	    	cin>>v[i];
   	    	if(v[i]==0)  zero++;
   	    }
   	 if(zero>0)  cout<<"0"<<endl;
   	 else {
   	 	 ll a=0;
   	 	 ll p=1;
   	 	 fll0(i,n)
   	 	   {
   	 	   	  if(v[i]<=N/p)  p=p*v[i];
   	 	   	  else {a++; cout<<"-1"<<endl; break;}
   	 	   }
   	 	if(a==0)  cout<<p<<endl;
   	 }
   	
   }

Measured memory_bytes: 4008
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main(){ _;
  int a,b,c,x,y;cin>>a>>b>>c>>x>>y;
  int result=x*a+y*b;
  result=min(result,(x-min(x,y))*a+(y-min(x,y))*b+min(x,y)*c*2);
  result=min(result,max(x,y)*c*2);
  cout<<result<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

int main() {
   int n, x;
   cin >> n >> x;
   int d = 0, ans = 1;
   rep(i, 0, n) {
      int l;
      cin >> l;
      d += l;
      if (d <= x) ans++;
   }
   cout << ans << endl;
   return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  sort(a.begin(),a.end());
  vector<ll> v(n);
  v[0] = a[0];
  rep(i,n-1) v[i+1] = v[i] + a[i+1];

  int ans = 1;
  int i = 0;
  while(n-2-i >= 0){
    if(2*v[n-2-i] >= a[n-1-i]) ans++;
    else break;
    i++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4828
#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <list>

#define FOR(i,n)	for(int i = 0 ; i < n ; i++)
#define FORrev(i,n)	for(int i = n - 1 ; i >= 0 ; i--)
#define ALL(a)		a.begin(),a.end()
#define pii			pair<int , int>
#define mp(a , b)	make_pair(a , b)


typedef long long int ll; 

using namespace std;

bool mark[1000006];

ll gcd(ll a , ll b) {
	if(a == 0)
		return b;
	return gcd(b % a , a);
}

int main() {
	ll a , b;
	cin>>a>>b;
	ll g = gcd(a , b);
	vector<ll> primes;
	memset(mark , false , sizeof(mark));
	primes.push_back(2);
	for(int i = 3 ; i < 1000006 ; i += 2) {
		if(mark[i] == false) {
			primes.push_back(i);
			for(int j = i ; j < 1000006 ; j += i) {
				mark[j] = true;
			}
		}
	}
	int count = 1;
	FOR(i , (int)primes.size()) {
		if(g % primes[i] == 0) {
			count++;
			while(g % primes[i] == 0) {
				g /= primes[i];
			}
		}
	}
	if(g > primes[primes.size() - 1] )
		count++;
	cout<<count;
}

Measured memory_bytes: 2424
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

map<ll, ll> mp;
ll X;
bool test(int n) {
  ll tmp = 1;
  rep(i, 5) tmp *= n;
  if(mp.count(tmp-X)) {
    cout << n << ' ' << mp[tmp-X] << endl;
    return true;
  } else if(mp.count(-tmp+X)) {
    cout << n << ' ' << -mp[-tmp+X] << endl;
    return true;
  } else {
    mp[tmp] = n;
    return false;
  }
}
int main() {
  cin >> X;
  ll tmp = 1;
  mp[0] = 0;
  while(!test(tmp)) { tmp++; }
  return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include <cstdio>
 
using namespace std;
 
void bubblesort(int A[], int N) {
 
    int i, j, temp, count = 0;
    bool flag = 1;
 
    for (i = 0; flag; i++) {
        flag = 0;
        for (j = N-1; j >= i+1; j--){
            if (A[j] < A[j - 1]) {
                swap(A[j], A[j - 1]);
                count++;
                flag = 1;
            }
        }
    }
 
    for (i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << count << endl;
}
 
int main() {
     
    int N, i, A[100];
 
    cin >> N;
    for (i = 0; i < N; i++)
        cin >> A[i];
 
    bubblesort(A, N);
 
    return 0;
 
}

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

int main(){
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  while (A > 0 && C > 0){
    C -= B;
    if (C <= 0)
      break;
    A -= D;
  }
  if (A <= 0)
    cout << "No" << endl;
  else
    cout << "Yes"  << endl;
}


Measured memory_bytes: 3544
#include <stdio.h>

int main(void) {
	int i,p,s,q,pd[128],f[32]={0},c,m;
	while(scanf("%d,%d",&p,&s) , p != 0){
		f[s] = 1;
		pd[p] = s;
	}
	while(scanf("%d",&q) != EOF){
		m = pd[q];
		c = 0;
		for(i = 30;i >= 0;i--){
			if(f[i] == 1){c++;}
			if(m == i){break;}
		}
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acos(-1);

int N;
vector<int> a, ans;
Graph<int> G;

void dfs(int v, int p, vector<int> &dp) {
    auto itr = lower_bound(dp.begin(), dp.end(), a[v]);
    swap(*itr, a[v]);
    ans[v] = lower_bound(dp.begin(), dp.end(), INT_MAX) - dp.begin();

    for (auto nv : G[v]) {
        if (nv == p)
            continue;
        dfs(nv, v, dp);
    }

    swap(*itr, a[v]);
}

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

    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i];
    G.resize(N);
    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    ans.resize(N);
    vector<int> dp(N, INT_MAX);
    dfs(0, -1, dp);

    for (auto i : ans)
        cout << i << '\n';
    return 0;
}


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

int main() {
    int X;
    cin >> X;
    if(X==3 || X==5 || X==7){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, d;
	cin >> n >> d;
	long long dist = d * 1ll * d;
	int resp = 0;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (x * 1ll * x + y * 1ll * y <= dist)
			resp++;
	}
	cout << endl;
	cout << resp << endl;
	
	return 0;
}

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

int main()
{
	long long int N;

	cin >> N;

	int min_sum = 0;
	int min_max = 1;

	while (1)
	{
		if (min_sum + min_max > N)
		{
			min_sum += min_max;
			break;
		}

		min_sum += min_max;
		min_max++;
	}

	int remove = min_sum -N;

	for (int i = 1; i <= min_max; i++)
	{
		if (i != remove)
		{
			cout << i << endl;
		}
	}

	return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n) cin >> d[i];

    int sum = 0;
    rep(i,n)rep(j,n-i-1) sum += d[i] * d[i+j+1];
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
A=int(input())
B=int(input())
C=int(input())
X=int(input())
d=0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500*a+100*b+50*c==X:
                d+=1
print(d)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	int n; cin >> n;
	vector<string>s(n);
	set<string>st;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		st.insert(s[i]);
	}
	if (st.size() < s.size()){
		cout << "No";
		return 0;
	}
	
	int cnt = 0;
	for(int i = 0; i < n-1; i++) {
		int len = s[i].length();
		if (s[i].back() == s[i + 1].front()) {
			cnt++;
		}
		else {
			break;
		}
	}
	if (cnt == n-1)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}


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

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

    int h[N+1], DP[N+1];
    for(int i = 1; i <= N; i++) cin >> h[i];

    DP[1] = 0;
    DP[2] = abs(h[1] - h[2]);
    for(int i = 3; i <= N; i++) DP[i] = min(DP[i-1]+abs(h[i]-h[i-1]), DP[i-2]+abs(h[i]-h[i-2]));

    cout << DP[N] << '\n';
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
 
#define PB push_back
#define MP make_pairA
#define REP(i,n) for(int i=0;i<(n);i++)
int main()
{
    int k;
    cin>>k;
    cout<<(k/2)*((k+1)/2)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> data(n);
  REP(i, n) {
    int a;
    cin >> a;
    vector<pair<int, int>> vi;
    REP(j, a) {
      int x, y;
      cin >> x >> y;
      vi.push_back(make_pair(x - 1, y));
    }
    data[i] = vi;
  }
  /*
  REP(i, n) {
    for (auto e : data[i]) {
      cout << e.first << " " << e.second << endl;
    }
  }*/
  int ans = 0;
  for (int bit = 0; bit < (1 << n); ++bit) {
    vector<int> now_honest;
    for (int i = 0; i < n; ++i) {
      if (bit & (1 << i)) {
        now_honest.push_back(i);
      }
    }

    bool judge = true;
    for (auto x : now_honest) {
      for (auto statement : data[x]) {
        bool a = statement.second == 1 &&
                 (find(ALL(now_honest), statement.first)) == now_honest.end();
        bool b = statement.second == 0 &&
                 (find(ALL(now_honest), statement.first)) != now_honest.end();
        if (a || b) {
          judge = false;
        }
      }
    }

    if (judge) {
      int len = now_honest.size();
      ans = max(ans, len);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import defaultdict, Counter

K, N = map(int, input().split())
A = list(map(int, input().split()))
M = A[0]+K-A[-1]
for i in range(N-1):
    M = max(M, A[i+1]-A[i])
print(K-M)

Measured memory_bytes: 72012
#include <cctype>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 6e5 + 7;
const int MOD = 924844033; 

inline int read() {
	char in = getchar();
	int res = 0, flag = 1;
	while(!isdigit(in)) { if(in == '-') flag = -1; in = getchar(); }
	while(isdigit(in)) { res = (res << 1) + (res << 3) + in - '0'; in = getchar(); }
	return res * flag;
}

int n, Lim = 1, Log;
int cnt[MAXN], siz[MAXN], P, a[MAXN << 1], b[MAXN << 1];
int fac[MAXN + 7], rev[MAXN], ifac[MAXN + 7];
int dex, head[MAXN], nxt[MAXN << 1], to[MAXN << 1];

inline void Link(int x, int y) { ++dex; nxt[dex] = head[x]; to[dex] = y; head[x] = dex; }

inline int fpm(int x, int y) {
	int res = 1;
	while(y) {
		if(y & 1) res = 1ll * x * res % MOD;
		x = 1ll * x * x % MOD;
		y >>= 1;
	}
	return res;
}

void dfs(int u, int fa) {
	siz[u] = 1;
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
	}
	--cnt[siz[u]]; --cnt[n - siz[u]];
}

inline void Transform(int *A, int type) {
	for(int i = 1; i < Lim; ++i) if(i < rev[i]) 
		swap(A[i], A[rev[i]]);
	for(int mid = 1; mid < Lim; mid <<= 1) {
		int Wn = fpm(5, ((MOD - 1) / mid) >> 1);
		if(type == -1) Wn = fpm(Wn, MOD - 2);
		for(int r = (mid << 1), j = 0; j < Lim; j += r) {
			for(int l = 0, k = 1; l < mid; ++l, k = 1ll * Wn * k % MOD) {
				int x = A[j + l];
				int y = 1ll * A[j + l + mid] * k % MOD;
				A[j + l] = (x + y) % MOD;
				A[j + l + mid] = (1ll * x - y + MOD) % MOD;
			}
		}
	}
	int C = fpm(Lim, MOD - 2);
	if(type == -1) for(int i = 0; i < Lim; ++i) A[i] = 1ll * A[i] * C % MOD;
}

inline void init() {
	n = read();
	for(int i = 1; i < n; ++i) {
		int x = read();
		int y = read();
		Link(x, y); Link(y, x);
	}
	dfs(1, 0); cnt[n] = n;
	fac[0] = 1; n <<= 1; n += 2;
	while(Lim < n) Lim <<= 1, ++Log;
	n -= 2; n >>= 1;

	for(int i = 1; i < Lim; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (Log - 1));
	for(int i = 1; i <= MAXN; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
	ifac[MAXN] = fpm(fac[MAXN], MOD - 2);
	for(int i = MAXN - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;

	for(int i = 1; i <= n; ++i) a[i] = 1ll * cnt[i] * fac[i] % MOD;
	for(int i = 0; i <= n; ++i) b[i] = ifac[n - i];
}

inline void solve() {
	Transform(a, 1); Transform(b, 1);
	for(int i = 0; i < Lim; ++i) a[i] = 1ll * a[i] * b[i] % MOD;
	Transform(a, -1);
	for(int i = 1; i <= n; ++i) printf("%lld\n", (1ll * a[n + i] * ifac[i] % MOD + MOD) % MOD);
}

int main() {
init();
	solve();
	return 0;
}


Measured memory_bytes: 40320
#include<bits/stdc++.h>
using namespace std;
 
#define int             long long
#define ld              long double
#define fi              first
#define se              second
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define fo(i,n)         for(i=0; i<n; i++)
#define fo1(i,n)        for(i=1; i<=n; i++)
#define Fo(i,k,n)       for(i=k; k<=n?i<=n:i>=n; k<=n?i++:i--)
#define all(x)          x.begin(), x.end()
#define rall(x)         x.rbegin(), x.rend()
#define sortall(x)      sort(all(x))
#define sortrall(x)     sort(rall(x))
#define clr(x)          memset(x, 0, sizeof(x))
#define tr(it, a)       for(auto it = a.begin(); it != a.end(); it++)
#define pii             pair<int, int>
#define mk(arr,n,type)  type *arr = new type[n];
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqmx            priority_queue<int>
#define pqmn            priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define trailzrobits(x) __builtin_ctzll(x)
#define leadzrobits(x)  __builtin_clzll(x)
#define paritybits(x)   __builtin_parityll(x)
#define gcd             __gcd
#define lcm(x, y)       (x * y) / gcd(x, y)
#define mod             1000000007
#define endl            '\n'
#define PI              3.1415926535897932384626
#define inf             1e18
#define sp(x,y)         fixed<<setprecision(y)<<x
void __print(int32_t x) {cout<<x;}
void __print(int x) {cout<<x;}
void __print(ld x) {cout<<x;}
void __print(double x){cout<<x;}
void __print(float x){cout<<x;}
void __print(bool x) {cout<<(x?"true":"false");}
void __print(char x){cout <<'\''<<x<<'\'';}
void __print(const char *x){cout <<'\"' <<x<<'\"';}
void __print(const string &x) {cout<<'\"'<<x<<'\"';}
template<typename T,typename V>     void __print(const pair<T,V> &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
template<typename T>                void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}void _print() {cout << "]\n";}
template <typename T,typename... V> void _print(T t, V... v) {__print(t);if(sizeof...(v))cout<<", ";_print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_print(x)
#else 
#define dbg(x...)
#endif
int power(int base, int exp){ int res = 1; base %= mod; while(exp > 0){ if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp = exp >> 1; } return res; }
int inv(int x){ return power(x, mod - 2) % mod; }
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




const int N = 1e6 + 6, M = N;
int i, j;

void solve(){
    
    int x,y; cin>>x>>y;

    int c1=x*2,c2=x*4;
    if(c1<=y and y<=c2 and (y&1)==0) cout<<"Yes";
    else cout<<"No";
    
    
    
}




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

Measured memory_bytes: 3652
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	
	int n=in();int q=in();
	string s;
	cin>>s;
	vector<int> pre(n+1);
	for(int i=1;i<n;i++)
	{
		pre[i+1]=pre[i]+(s[i]=='C' and s[i-1]=='A');
	}
	
	int l,r;
	//for(auto i:pre)cout<<i<<" ";cout<<"\n";
	while(q--)
	{
		l=in();r=in();
		cout<<pre[r]-pre[l]<<"\n";
	}
}

Measured memory_bytes: 4388
import java.lang.*;
import java.util.*;
import java.io.*;

public class Main
{
	public static void main (String[] arg)throws IOException
	{
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String line;
		line=input.readLine();
		int a = Integer.parseInt(line);
		long sum = 1;
		for (int i=1; i <= a;i++){
			sum*=i;
		}
		System.out.println(sum);
			
	}
}	
		

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

int main() {
  int H, N, A, Sum=0;
  cin >> H >> N;
  rep(i, N){
    cin >> A;
    Sum+=A;
  }
  if(Sum>=H) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#coding:utf-8
#1_5_D

def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
            cnt += len(L) - 1 - i

def merge_sort(array, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(array, left, mid)
        merge_sort(array, mid, right)
        merge(array, left, mid, right)

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0
sentinel = 10 ** 9 + 1
merge_sort(numbers, 0, len(numbers))
print(cnt)

Measured memory_bytes: 29552
t=int(input())
ac=0
wa=0
tle=0
re=0
for i in range(t):
    n=input()
    
    if n == "AC" :ac+=1
    if n == "WA" :wa+=1
    if n == "TLE" :tle+=1
    if n == "RE" :re+=1
print('AC x ',ac)
print('WA x ',wa)
print('TLE x ',tle)
print('RE x ',re)

Measured memory_bytes: 9208
#include <bits/stdc++.h>
#define rep(i, e, n) for (int i = e; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const ll inf=1000000000007;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> val(1000001,0);
  rep(i,0,n) cin >> a[i];
  rep(i,0,n) {
    int vali=a[i];
    for(int j=2; j*j<=vali;j++){
      if(vali%j==0){
        val[j]++;
        vali/=j;
      }
      while(vali%j==0){
        vali/=j;
      }
    }
    if(vali!=1) val[vali]++;
  }
//  cout << val[2] << endl;
  bool pair=true;
  rep(i,2,1000001){
    if(val[i]==n){
      cout << "not coprime" << endl;
      return 0;
    }
    if(val[i]>=2) pair=false;
  }
  if(pair){
      cout << "pairwise coprime" << endl;
      return 0;
  }
  cout << "setwise coprime" << endl;
  return 0;
}

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

int main(void)
{
    int A, B;
    char op[2];
    scanf("%d%s%d", &A, op, &B);

    if (!strcmp(op, "+")) {
        printf("%d\n", A+B);
    } else {
        printf("%d\n", A-B);
    }
    return 0;
}

Measured memory_bytes: 128
N, M, X, Y = map(int, input().split())
x = input().split()
y = input().split()
x = [int(i) for i in x]
y = [int(i) for i in y]
x.sort()
y.sort()
if (x[-1] < y[0]) and (Y > x[-1]) and (X < y[0]):
    print("No War")
else:
    print("War")

Measured memory_bytes: 3064
///#pragma GCC optimize("Ofast")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
///#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

///#include<ext/pb_ds/assoc_container.hpp>
///#include<ext/pb_ds/tree_policy.hpp>
///using namespace __gnu_pbds;
///template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
///(X).order_of_key(value) /// return lower_bound(value)
///(*X).find_by_order(index) /// return value (0 index)

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;

const int N = 100001;
const int MOD = 1000000007;
const ll INF = LLONG_MAX;

#define fast() ios_base::sync_with_stdio(false),cin.tie(NULL)
#define next(x) next_permutation(all(x))
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define pb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define space ' '
#define nl '\n'
#define PI acos(-1)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())
#define dbg(x) cerr<<#x<<" is "<<x<<'\n';
#define fix(x) cout<<fixed<<setprecision(x)
#define leastonepos(x) __builtin_ffs(x)
#define leadingoff(x) __builtin_clz(x)
#define trailingoff(x) __builtin_ctz(x)
#define numofone(x) __builtin_popcount(x)

#define coutv(v) for(auto it:v)cout<<it<<space;cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;

///................Graph's Move.................
///const int dx[] = {+1,-1,+0,+0}; ///Rock's Move
///const int dy[] = {+0,+0,+1,-1}; ///Rock's Move
///const int dx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's Move
///const int dy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int dx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's Move
///const int dy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's Move
///*.....................-_-........................*///

ll ff(ll x)
{
    ll res=0;
    for(int i=1; i<=x; i++)
    {
        res++;
        x-=i;
    }
    return res;
}
ll f(ll n)
{
    ll ans=0,i;
    for(i=2; i*i<=n; i++)
        if(n%i==0)
        {
            ll c=0;
            while(n%i==0)
            {
                c++;
                n/=i;
            }
            ans+=ff(c);
        }
    if(n>1)
        ans++;
    return ans;
}

int main()
{
    fast();
    int tc=1,cs=0;
    //cin>>tc;
    while(tc--)
    {
        ll n;
        cin>>n;
        cout<<f(n)<<nl;
    }
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2000000010;
constexpr ll INF= 2000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;
typedef pair<int,P> PP;

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

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

void mod(ll &val, ll M) {
    val = val % M;
    if(val < 0) {
        val += M;
    }
}

template<typename T>
T RS(T N, T P, T M){
    if(P == 0) {
        return 1;
    }
    if(P < 0) {
        return 0;
    }
    if(P % 2 == 0){
        ll t = RS(N, P/2, M);
        if(M == -1) return t * t;
        return t * t % M;
    }
    if(M == -1) {
        return N * RS(N,P - 1,M);
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    int N,K;
    cin >> N >> K;
    vector<bitset<31>> A(N);
    vector<ll> B(N);
    for(int i = 0;i < N;i++) {
        int cnt;
        cin >> cnt;
        A.at(i) = cnt;
        cin >> B.at(i);
    }
    bitset<31> bit(K);
    ll ret = 0;
    for(int i = 0;i < 31;i++) {
        if(bit[i] == 0) {
            ll cost = 0;
            for(int j = 0;j < N;j++) {
                if((bit & A.at(j)) == A.at(j)) {
                    cost += B.at(j);
                }
            }
            chmax(ret,cost);
        }
        else {
            bitset<31> bit2 = bit;
            bit2[i] = 0;
            for(int j = 0;j < i;j++) {
                bit2[j] = 1;
            }
            ll cost = 0;
            for(int j = 0;j < N;j++) {
                if((bit2 & A.at(j)) == A.at(j)) {
                    cost += B.at(j);
                }
            }
            chmax(ret,cost);
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 4768
kingaku,=gets.chomp.split.map(&:to_i)
i=kingaku
kirai_array=gets.chomp.split.map(&:to_i)
 
while 1
	if (i.to_s.split("").map(&:to_i) - kirai_array).size == i.to_s.split("").map(&:to_i).size
		puts i
        break
    end
i+=1
end

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    if (a <= b && a + w >= b || a <= b + w && a + w >= b + w) { 
        cout << 0 << endl;
    } else if (a + w < b) {
        cout << b - (a + w) << endl;
    } else if (b + w < a) {
        cout << a - (b + w) << endl;
    } else {
        cout << 0 << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>

using namespace std;

typedef long long ll;

const int NMAX = 1 << 17;
const int INF = (1LL << 31) - 1;

template<class T> class SegT {
   
   public:
      T dat[2 * NMAX - 1];
      int N;

      void init(int n_) {
         N = 1;
         while(N < n_) N <<= 1;
         for (int i = 0; i < 2 * N - 1; i++) dat[i] = INF;
      }
      
      //k: 0-indexed
      void update(int k, int a) {
         k += N - 1;
         dat[k] = a;
         while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
         }
      }

      T find(int a, int b, int k, int l, int r) {
         if (r <= a || b <= l) return INF;
         if (a <= l && r <= b) return dat[k];
         else {
            int vl = find(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = find(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
         }
      }
      // get min in [a, b)
      T getmin(int a, int b) {
         return find(a, b + 1, 0, 0, N);
      }
};

int main() {
   int n, Q;
   cin >> n >> Q;
   SegT<int> segt;
   segt.init(n);
   int c, x, y;
   for (int q = 0; q < Q; q++) {
      cin >> c >> x >> y;
      if (c == 0) segt.update(x, y);
      else cout << segt.getmin(x, y) << endl;
   }
   return 0;
}



Measured memory_bytes: 4140
/**
  *  Author: dhruv_gheewala
  *  Problem: C - A x B + C
  *  Date:   19.09.2020
  *  Time:   23:00:12
**/

#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;
    
    #define fundri 108
    #define debug(...) 1729
#endif

#define int int64_t
typedef pair<int, int> pii;
typedef vector<int> vi;

const bool testcases = false;
#define ff first
#define ss second
#define endl '\n'
#define all(s) s.begin(), s.end()

// if vector isn't soted then it will remove consecutive same elements
#define make_unique(vec) vec.erase(unique(all(vec)), vec.end())
#define test int TC = 1;if(testcases)cin >> TC;for(int tc = 1 ; tc <= TC ; tc++)solve(), fundri
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})
// clears stdin
#define flush(ch) cin.ignore(std::numeric_limits<std::streamsize>::max(), ch) // default, EOF

int seed; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = INT_MAX) {return uniform_int_distribution<int>(l, r)(rng);}

inline bool in_range(int a, int l, int r) {return (a >= l && a <= r);}
template<typename H, typename ...T>void inp(H &head) {cin >> head;}
template<typename H, typename ...T>void inp(H &head, T &...tail) {cin >> head;inp(tail...);}
template<typename T>bool isPrime(T n) {for(T i = 2; i * i <= n; i++)if(n % i == 0)return false; return n >= 2;}
template<typename T>inline istream &operator >>(istream &in, vector<T> &a) {for(T &x : a)in >> x; return in;}
template<typename T, typename U>inline istream &operator >>(istream &in, pair<T, U> &a) {in >> a.ff >> a.ss; return in;}

void solve();
void fast_io();

int32_t main(int32_t argc, char **argv)
{
    fast_io();
    test;
    return 0;
}

// using vector(if factorization is needed)
vi sieve;
const int mxs = 4000000;  // 4 * 10^6
bool isPrime(int n) {return sieve[n] == -1;}

void build_sieve(int maximum = mxs)
{
    sieve.assign(maximum + 1, -1);
    sieve[0] = sieve[1] = 0;
    
    for(int i = 2 ; i * i <= maximum ; i++) {
        if(isPrime(i)) {
            for(int j = i * i ; j <= maximum ; j += i) {
                if(isPrime(j))
                    sieve[j] = i;
            }
        }
    }
}

void sfact(int n, map<int, int> &ans)
{
    if(n <= 1) {
    	ans[n]++;
    	return;
    }

    if(!sieve.size()) build_sieve();
    
    while(true) {
        if(isPrime(n)) {
            ans[n]++;
            break;
        }
        
        ans[sieve[n]]++;
        n /= sieve[n];
    }
}

void solve()
{
    int n;
    cin >> n;
    build_sieve(n + 5);

    int ans = 1;
    for(int i = 2 ; i < n ; i++) {
    	map<int, int> res;
    	sfact(i, res);

    	int mul = 1;
    	for(const auto &p: res)
    		mul *= (p.ss + 1);
    	// debug(i, res, mul, ans);
    	ans += mul;
    }
    cout << ans << endl;
}

void fast_io()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef DHRUV_GHEEWALA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif
}

Measured memory_bytes: 11068
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	s := next()
	for _, v := range s {
		if v == '1' {
			v = '9'
		} else if v == '9' {
			v = '1'
		}
		fmt.Printf("%c", v)
	}
	fmt.Printf("\n")
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,x,ans;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
int main()
{
    int i,j,k,l;
    scanf("%lld%lld",&n,&x);
    ans=3LL*(n-gcd(n,x));
    printf("%lld\n",ans);
    return 0;
}


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

int main(){
  int A,B;

  cin >> A >> B;

  int a,b,c;

  a = A + B;
  b = A - B;
  c = A * B;

  a = max(a,b);

  a = max(a,c);

  cout << a << endl;
  
  return 0;
}


Measured memory_bytes: 256
/*
 If you want to aim high, aim high
 Don't let that studying and grades consume you
 Just live life young
 ******************************
 If I'm the sun, you're the moon
 Because when I go up, you go down
 *******************************
 I'm working for the day I will surpass you
 https://www.a2oj.com/Ladder16.html
 */
 import java.util.*;
 import java.io.*;
 import java.math.*;
  
    public class Main
    {
       public static void main(String omkar[]) throws Exception
       {
          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
          StringTokenizer st = new StringTokenizer(infile.readLine());
          int N = Integer.parseInt(st.nextToken());
          int P = Integer.parseInt(st.nextToken());
          String input = infile.readLine();
          int[] arr = new int[N];
          for(int i=0; i < N; i++)
             arr[i] = Integer.parseInt(input.charAt(i)+"");
          if(P == 2)
          {
            long res = 0L;
            for(int i=0; i < N; i++)
               if(arr[i]%2 == 0)
                  res += i+1;
            System.out.println(res);
            return;
          }
          if(P == 5)
          {
            long res = 0L;
            for(int i=0; i < N; i++)
               if(arr[i]%5 == 0)
                  res += i+1;
            System.out.println(res);
            return;
          }
          long[] count = new long[P];
          long res = 0L;
          int coef = 1;
          int curr = 0;
          for(int i=N-1; i >= 0; i--)
          {
             curr += coef*arr[i];
             curr %= P;
             res += count[curr];
             if(curr == 0)
                res++;
             count[curr]++;
             coef *= 10;
             coef %= P;
          }
          System.out.println(res);
       }
    }

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

typedef long long int lli;

lli MOD = 1e9+7;

lli n;
map<tuple<int, int, bool>, lli> memo;
lli f(int bit, int carry, bool eq) {
  if (bit == -1)
    return (carry==1?0:1);
  tuple<int, int, bool> key(bit, carry, eq);
  if (memo.count(key))
    return memo[key];
  int nbit = (n>>bit)&1;
  lli ans=0;
  for (int u=0; u<=1; ++u) for (int v=0; v<=1; ++v) for (int a=0; a<=1; ++a) {
    int b = a^u;
    if (b > a)
      continue;
    int nextCarry = 2*carry+v - (a+b);
    if (nextCarry!=0 && nextCarry != 1)
      continue;
    if (eq && v > nbit)
      continue;
    lli res = f(bit-1, nextCarry, eq && (v==nbit));
    ans = (ans + f(bit-1, nextCarry, eq && (v==nbit)))%MOD;
  }
  memo[key] = ans;
  return ans;
}

int main() {
  cin >> n;
  cout << f(60, 0, true) << endl;
}

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

struct Union_Find
{
    vector <int> parent;
    Union_Find(int N) : parent(N)
    {
        for(int i = 0; i < N; i++) parent[i] = i;
    }
    int root(int n)
    {
        if (parent[n]==n) return n;
        else
        {
            return root(parent[n]);
        }
    }

    void unite(int i,int j)
    {
        int rx,ry;
        rx=root(i);
        ry=root(j);
        if (rx==ry) return;
        else
        {
            int k;
            if (rx<ry)
            {
                parent[ry]=rx;
                return;
            }
            else
            {
                parent[rx]=ry;
                return;
            }
        }
    }
    bool same(int i, int j)
    {
        if (root(i)==root(j)) return true;
        else return false;
    }
};

int main()
{
    int V,E;
    cin >> V>> E;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> que;
    int s,t,d;
    for (int i=0;i<E;i++)
    {
        cin >> s >> t >> d;
        que.push(mp(d,mp(s,t)));
    }
    Union_Find solve(V);
    int ans=0;
    for (int i=0;i<E;i++)
    {
        s=que.top().second.first;
        t=que.top().second.second;
        d=que.top().first;
        que.pop();
        if (!solve.same(s,t))
        {
            solve.unite(s,t);
            ans+=d;
        }
    }
    cout << ans << endl;
return 0;
}



Measured memory_bytes: 4444
#include <bits/stdc++.h>
using namespace std;
#define ll                  long long int
#define ull                 unsigned long long int
#define ld                  long double
#define fi                  first
#define se                  second
#define pb                  push_back
#define pbb                 pop_back
#define mp                  make_pair
#define pii     	        pair<int,int>
#define all(x)              x.begin(), x.end()
#define uniq(x)             x.erase(unique(x.begin(),x.end()),x.end())
#define mem(array, value)   memset(array, value, sizeof(array))
#define PI      	        2*acos(0.0)
#define EPS     	        1e-8
#define line                cout << "\n==========\n"
#define fastRead 	        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define trace(...)          __f( #__VA_ARGS__ , __VA_ARGS__ )
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " , ";
    __f(comma + 1, args...);
}

const int INF = 1e9+9;


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

    int n, l;
    cin >> n >> l;

    int total = 0;
    for (int i = 1; i <= n; i++){
        total += l + i - 1;
    }
    int ans;
    int diff = INF;
    for (int i = 1; i <= n; i++){
        if (abs(total - (total - (l + i -1))) < diff){
            diff = abs(total - (total - (l + i -1)));
            ans =  total - (l + i -1);
        }
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    long n;
    char s[11];
    long m, a, r, c, h;
    m = a = r = c = h = 0;
    long i;
    scanf("%ld", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%s", s);
        if (s[0] == 'M')
            m++;
        if (s[0] == 'A')
            a++;
        if (s[0] == 'R')
            r++;
        if (s[0] == 'C')
            c++;
        if (s[0] == 'H')
            h++;
    }
    long ans = 0;
    ans += (m*a*r);
    ans += (m*a*c);
    ans += (m*a*h);
    ans += (m*r*c);
    ans += (m*r*h);
    ans += (m*c*h);
    ans += (a*r*c);
    ans += (a*r*h);
    ans += (a*c*h);
    ans += (r*c*h);
    printf("%ld\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int get_val(char a)
{
    if(a == 'R')return 0;
    if(a == 'G') return 1;
    return 2;
}
int rem_guy(int a, int b)
{
    int j;
    FOR0(j, 3) if(j != a && j != b) return j;
}
int main()
{
    she_told_me_dont_worry
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll i, j;
    ll pos[n+5][4] = {};
    FORD(i, n-1, 0)
    {
        pos[i][get_val(s[i])] = 1;
        if(i < n-1)
        FOR0(j, 3) pos[i][j] += pos[i+1][j];
    }
    ll ans = 0;
    FOR0(i, n)
    {
        FOR(j, i+1, n)
        {
            if(s[j] == s[i] || j == n-1) continue;
            int guy = rem_guy(get_val(s[i]), get_val(s[j]));
            int dif = j - i;
            ll cur = pos[j+1][guy];
            if( j+dif < n && get_val(s[j+dif]) == guy) cur--;
            ans += cur;
        }
    }
    cout<<ans<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S,T;
  cin >> S >> T;
  
  string ans ="Yes";
  for(int i=0; i<S.size(); i++){
    if(S[i]!=T[i]) ans = "No";
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3624