akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 01:34:43 2020

@author: liang
"""

"""
Union-Find クラス
素集合の併合・判定アルゴリズム
グラフの問題を集合と見なして解く時に使用する
"""

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.par = [-1]*(n+1)
    
    def find(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        
    def same(self,x,y):
        x = self.find(x)
        y = self.find(y)
        return x==y
    
N, M = map(int,input().split())

uf = UnionFind(N)
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
ans = sum([uf.par[i] < 0 for i in range(N)]) - 1
print(ans)
    

Measured memory_bytes: 11556
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int X, Y, A, B, C;
  while (cin >> X >> Y >> A >> B >> C) {
    vector<ll> p(A), q(B), r(C);
    for (auto& x : p) cin >> x;
    for (auto& x : q) cin >> x;
    for (auto& x : r) cin >> x;
    sort(p.rbegin(), p.rend());
    sort(q.rbegin(), q.rend());
    p.resize(X);
    q.resize(Y);
    vector<ll> v;
    for (ll x : p) v.push_back(x);
    for (ll x : q) v.push_back(x);
    for (ll x : r) v.push_back(x);
    sort(v.rbegin(), v.rend());
    ll res = accumulate(v.begin(), v.begin() + X + Y, 0ll);
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 8816
#include <iostream>
#include <bits/c++io.h>

using namespace std;

int main()
{
 int x,t=0,maxi=0;

 cin>>x;
  char s[x];
  for(int i=0;i<x;i++)
 {
     cin>>s[i];
 }
 for(int i=0;i<x;i++)
 {
     if(s[i]=='I')
        t++;
     else if(s[i]=='D')
        t--;
     if(t>maxi)
        maxi=t;
 }
 cout<<maxi<<endl;
}


Measured memory_bytes: 3596
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
            System.out.println("Possible");
        } else {
            System.out.println("Impossible");
        }
    }

}


Measured memory_bytes: 21844
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();
		int inputAns = Integer.parseInt(br.readLine());

		//真面目に計算する方
		int numArray1[] = new int[input.length()/2 + 1];
		//左からしか計算しない方
		int numArray2[] = new int[input.length()/2 + 1];

		for(int i = 0; i < numArray1.length; i++){
			numArray1[i] = numArray2[i] = input.charAt(i*2) - '0';
		}

		int ans1=0, ans2=0;

		//真面目に計算する方（掛け算->足し算で考える）
		for(int i = 0; i < input.length() / 2; i++){
			if(input.charAt(i*2 + 1) == '*'){
				numArray1[i + 1] = numArray1[i]*numArray1[i+1];
				numArray1[i] = 0;
			}
		}
		for(int i = 0; i < numArray1.length; i++){
			ans1 += numArray1[i];
		}

		//左から計算する方
		for(int i = 0; i < input.length() / 2; i++){
			if(input.charAt(i*2 + 1) == '*'){
				numArray2[i + 1] = numArray2[i]*numArray2[i+1];
			}
			else {
				numArray2[i + 1] = numArray2[i]+numArray2[i+1];
			}
		}
		ans2 = numArray2[numArray2.length - 1];

		String result = null;
		if(ans1 == inputAns && ans2 != inputAns){
			result = "M";
		}
		else if(ans1 != inputAns && ans2 == inputAns){
			result = "L";
		}
		else if(ans1 == inputAns && ans2 == inputAns){
			result = "U";
		}
		else {
			result = "I";
		}

		System.out.println(result);
	}

}



Measured memory_bytes: 24440
N = int(input())
A =  list(map(int, input().split()))
count = 0
flag = 0

while flag == 0:
    for i in range(N):
        if (A[i] % 2 == 0):
            A[i] = A[i] / 2
        else:
            flag = 1
    count += 1

print(count - 1)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int aa[10][10];
bool ans=false;
bool ok;
vector<int> v;
void dfs(int n,int step)
{
	if (step==4) {ans=true;return;} 
	for (int i=1;i<=4;i++)
	{
		for (int j=0;j<v.size();j++) 
			if (v[j]==i) ok=true;
		if ((aa[n][i]==1 || aa[i][n]==1) && !ok) {ok=false;v.push_back(i);dfs(i,step+1);v.pop_back();}
		ok=false;
	}
	return;
}
int main()
{
	int a,b;
	for (int i=1;i<=3;i++)
	{
		cin>>a>>b;
		aa[a][b]=1;
	}
	for (int i=1;i<=4;i++)
	{
		v.push_back(i);
		dfs(i,1);
		v.pop_back();
	}
	if (ans) cout<<"YES";
	else cout<<"NO";
	return 0;
}


Measured memory_bytes: 256
n = int(input())
s = []
for i in range(n):
    s.append(input())
s = sorted(s)
m = 0
a = 0
r = 0
c = 0
h = 0
for i in range(n):
    x = s[i]
    if x[0]=='M': m+=1
    elif x[0]=='A': a+=1
    elif x[0]=='R': r+=1
    elif x[0]=='C': c+=1
    elif x[0]=='H': h+=1
ans = m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h
print(ans)

Measured memory_bytes: 10984
from collections import deque
s = deque(input())
q = int(input())
cnt = 0
for i in range(q):
  query = input()
  if query == '1':
    cnt += 1
  else:
    t, f, c = query.split()
    if (f == '1' and cnt % 2 == 0) or (f == '2' and cnt % 2 == 1):
      s.appendleft(c)
    else:
      s.append(c)
if cnt % 2 == 0:
  print(''.join(s))
else:
  s.reverse()
  print(''.join(s))

Measured memory_bytes: 8436
#include<stdio.h>

int main(){
	int a,b;
	int length = 0;
	int area = 0;
	
	scanf("%d %d", &a, &b);
	
	length = 2 * a + 2 * b;
	area = a * b;
	
	printf("%d %d\n", area, length);
	
	return 0;
}
	


Measured memory_bytes: 2048
/*
https://o-treetree.hatenablog.com/entry/ABC173
勉強させて頂いた解説
最大値を取れる場所一つと引き換えに、
新しく二つ値が取れる場所を挿入するというのは、
思いつかなかった……
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

int main(){
    int n,m=INF;
    ll ans=0;
    cin>>n;
    vector<ll> a(n);
    rep(i,n)cin>>a[i];
    sort(ALL(a),greater<ll>());
    /*
    priority_queueを使わなくても、数列はsortされているため、
    取り出す値は最大値であることが保証されているため、
    queuegが使える。
    */
    queue<ll> que;
    rep(i,n){
        if(i==0){
            que.push(a[i]);
        }else{
            ans+=que.front();
            que.pop();
            que.push(a[i]);
            que.push(a[i]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 6424
from collections import deque
N,Q = map(int,input().split())
AB = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  AB[a-1].append(b-1)
  AB[b-1].append(a-1)

count = [0]*N
for i in range(Q):
  p,x = map(int, input().split())
  count[p-1] += x
que = deque([0])
used = [0]*N
used[0] = 1
while que:
  q = que.popleft()
  for p in AB[q]:
    if used[p] == 1:
      continue
    count[p] += count[q]
    used[p] = 1
    que.append(p)
print(*count)

Measured memory_bytes: 56060
N=int(input())
V=[[i,N//2*2-i+1] for i in range(1,N//2+1)]
if N&1:
    V+=[[N]]
E=[]
for u in range(len(V)):
    for v in range(len(V)):
        if u!=v:
            for x in V[u]:
                for y in V[v]:
                    if x<y:
                        E.append((x,y))
print(len(E))
for x,y in E:
    print(x,y)

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();

        if (A != 2 && B != 2) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
n=int(input())
c=input()

r=0
w=0

for i in range(n):
    if c[i]=="R":
        r+=1
    else:
        w+=1

umeru=0

for j in range(r):
    if c[j]=="W":
        umeru+=1

if r>=umeru:
    print(umeru)
else:
    print(umeru + (r-umeru))

Measured memory_bytes: 9484
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int MAX_N {100};
const int MAX_M {1000};
const int INF {(int)1e8};

int N, M;
bool used[MAX_N];
int dist[MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

void dijkstra(int s) {
  fill(used, used + N, false);
  dist[s][s] = 0;
  while (1) {
    int u = -1;
    rep(v, N) {
      if (!used[v] && (u == -1 || dist[s][v] < dist[s][u])) u = v;
    }
    if (u == -1) break;
    used[u] = true;
    rep(v, N) {
      dist[s][v] = min(dist[s][v], dist[s][u] + cost[u][v]);
    }
  }
}

main() {
  int cnt {};
  cin >> N >> M;
  fill((int*)cost, (int*)(cost + N), INF);
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    cost[a][b] = cost[b][a] = c;
  }
  fill((int*)dist, (int*)(dist + N), INF);
  rep(s, N) dijkstra(s);
  rep(i, N) {
    rep(j, N) {
      if (i >= j) continue;
      bool shortest {};
      rep(s, N) {
        if (dist[s][j] == dist[s][i] + cost[i][j]) {
          shortest = true;
          break;
        }
      }
      if (shortest) cnt++;
    }
  }
  cout << M - cnt << endl;
}


Measured memory_bytes: 384
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
// bool operator<(const pair<int, int> &a, const pair<int, int> &b)
// {
//     if (a.first == b.first)
//         return a.second < b.second;
//     return a.first < b.first;
// };

/*unsigned int xor128(void)
{
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned int xor128rnd(unsigned int m)
{
    return xor128() % m;
}*/

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}
ll dp[100010][4];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(10);

    string S;
    cin >> S;
    int n = (int)S.size();

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            if (S[i] != '?')
                dp[i + 1][j] += dp[i][j];
            else
                dp[i + 1][j] += dp[i][j] * 3;
        }
        if (S[i] == 'A')
        {
            dp[i + 1][1] += dp[i][0];
        }
        if (S[i] == 'B')
        {
            dp[i + 1][2] += dp[i][1];
        }
        if (S[i] == 'C')
        {
            dp[i + 1][3] += dp[i][2];
        }
        if (S[i] == '?')
        {
            dp[i + 1][1] += dp[i][0];
            dp[i + 1][2] += dp[i][1];
            dp[i + 1][3] += dp[i][2];
        }
        dp[i + 1][0] %= MOD;
        dp[i + 1][1] %= MOD;
        dp[i + 1][2] %= MOD;
        dp[i + 1][3] %= MOD;
    }

    cout << dp[n][3] << endl;
    return 0;
}


Measured memory_bytes: 3664
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
Load = [0 for i in range(N)]
# print(Load)

for i in range(M):
    a, b = map(int, input().split())
    Load[a-1] += 1
    Load[b-1] += 1

for i in range(N):
    print(Load[i])

# print(Load)


Measured memory_bytes: 9168
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

constexpr int max_n = 200'000 + 5;

int n;
vector<int> cs(max_n);
vector<vector<int>> adjs(max_n);
vector<ll> res(max_n);
// vector<pair<bool,int>> euler_tour; // { is_down, vertex }
// vector<int> et_in(max_n), et_out(max_n);
int et_size;
vector<int> sums(max_n); // sums[c] = 色cの現在の累積和
// vector<int> memo(2 * max_n); // memo[i] = euler_tour[i]でのメモ

void dfs(int cur = 1, int par = 0) {
    int par_color = cs[par], cur_color = cs[cur];
    // int in_i = euler_tour.size();
    int in_i = et_size;
    // memo[in_i] = sums[color];
    int memo = sums[par_color];
    // et_in[cur] = in_i;
    // euler_tour.push_back({true, cur});
    et_size++;
    for (auto ch : adjs[cur]) {
        if (ch == par) { continue; }
        dfs(ch, cur);
    }
    // int out_i = euler_tour.size();
    int out_i = et_size;
    // et_out[cur] = out_i;
    // euler_tour.push_back({false, cur});
    et_size++;

    sums[cur_color]++;
    int tree_size = (out_i - in_i + 1) / 2;
    ll component_size = tree_size - (sums[par_color] - memo);
    res[par_color] += component_size * (component_size + 1) / 2;
    sums[par_color] += component_size; // = tree_size + memo
}

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    cin >> n;
    rep(i, n) {
        int c; cin >> c;
        cs[i+1] = c;
    }
    rep(i, n-1) {
        int a,b; cin >> a >> b;
        adjs[a].push_back(b);
        adjs[b].push_back(a);
    }

    dfs();

    rep(i, n) {
        int tree_size = et_size / 2;
        ll component_size = tree_size - sums[i+1];
        res[i+1] += component_size * (component_size + 1) / 2;

        res[i + 1] = (ll)n * (n + 1) / 2 - res[i + 1];
        cout << res[i + 1] << '\n';
    }

    return 0;
}


Measured memory_bytes: 32996
import java.util.Arrays
import java.util.ArrayList

const val MOD: Long = (1e9+7).toLong()
fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun <T : Comparable<T>> Iterable<T>.argmax(): Int? = withIndex().maxBy{it.value}?.index
fun <T : Comparable<T>> Iterable<T>.argmin(): Int? = withIndex().minBy{it.value}?.index

fun main(args: Array<String>) {
    val reader = System.`in`.bufferedReader()
    val n = reader.readLine()!!.toInt()
    val s = Array(n, {reader.readLine()!!})

    val m = Array(n, {mutableMapOf<Char, Int>()})
    for ((index, t) in s.withIndex()) {
        for (i in 0..25) {
            m[index]['a'+i] = t.count{'a'+i == it}
        }
    }

    val list = Array(26, {0})
    for (i in 0..25) {
        var min = Int.MAX_VALUE
        for (j in 0..n-1) {
            min = Math.min(m[j]['a'+i]!!, min)
        }
        list[i] = min
    }

    val sb = StringBuilder("")
    for (i in 0..25) {
        val c = 'a'+i
        repeat(list[i]) {
            sb.append(c.toString())
        }
    }

    println(sb)
}


Measured memory_bytes: 32248
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void solve(long long N, long long W, std::vector<long long> w, std::vector<long long> v){
    ll Vsum = 0;
    REP(i, N) Vsum += v[i];
    vector<vll> dp(N+1, vll(Vsum+1, INF));
    dp[0][0] = 0;
    REP(i, N){
        REP(j, Vsum+1){
            dp[i+1][j] = dp[i][j];
            if(j >= v[i]){
                chmin(dp[i+1][j], dp[i][j-v[i]]+w[i]);
            }
        }
    }
    ll res = 0;
    REP(j, Vsum+1){
        if(dp[N][j] <= W)
            chmax(res, j);
    }
    cout<<res<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long W;
    scanf("%lld",&W);
    std::vector<long long> w(N);
    std::vector<long long> v(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&w[i]);
        scanf("%lld",&v[i]);
    }
    solve(N, W, std::move(w), std::move(v));
    return 0;
}


Measured memory_bytes: 80256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            long n = long.Parse(Console.ReadLine());
            long a = long.Parse(Console.ReadLine());
            n = n % 500;
            Console.WriteLine(a >= n ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using P = pair<int, int>;
int main()
{
    double a,b,c,d;
    cin >> a >> b >> c >> d;
    int cnt = 0;
    while(a >0){
        cnt++;
        a -= d;
    }
    if(c - b*cnt <= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3720
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    int a,b,c;
    cin >> a;

    if (a == 1) {
        cout << "Hello World" << endl;
    }else if (a == 2) {
        cin >> b >> c;
        cout << b + c << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

int main()
{
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    ll tmp = A - B;
    if (K % 2 == 0) {
        print(tmp);
    } else {
        print(tmp * -1);
    }
    return 0;
}

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

using i64 = int64_t;

constexpr i64 MOD = 1e9 + 7;

i64 repeated_squaring(i64 x, i64 n) {
    i64 res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int main(){
    string s;
    cin >> s;
    i64 ans = 0, cnt = 0;
    for(i64 i=0;i<s.size();++i){
        if(s[i] == '0')continue;
        i64 tmp = repeated_squaring(3, ((i64)s.size()-i-1)) * repeated_squaring(2, cnt) % MOD;
        ans += tmp;
        ans %= MOD;
        cnt++;
    }
    ans += repeated_squaring(2, cnt);
    ans %= MOD;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    vector<vector <int>> hito(K);
    for (int i = 0; i < K; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int bango;
            cin >> bango;
            hito[i].push_back(bango);
        }
    }
    int key = 0;
    vector<int> count(N+1);
    for (int h = 1; h <= N; h++) {
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < hito[i].size(); j++) {
                if (hito[i][j] == h) {
                    count[h]++;
                }
            }
        }
        if (count[h] > 0) {
            key++;
        }
    }
     cout << N - key << endl;
}

Measured memory_bytes: 3640
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        // 主処理
        String result = s.substring(0, 4) + " " + s.substring(4);

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 22608
///////////////////////////////////////////////////////////
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
///////////////////////////////////////////////////////////
#define ll long long
#define ull unsigned lon long
///////////////////////////////////////////////////////////
int absolute(int n); double absolute(double n);
void input(vector<int>& vec);
void print(vector<int> vec); void print(vector<double> vec);
int sum(vector<int> vec); double sum(vector<double> vec);
void upsort(vector<int>& vec);
void downsort(vector<int>& vec);
int maxvec(vector<int> vec);
int minvec(vector<int> vec);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
int main()
{
    string s("000"),t("000");
    for(int i=0;i<3;++i){
        cin>>s.at(i);
    }
    for(int i=0;i<3;++i){
        cin>>t.at(i);
    }
    short ans=0;
    for(int i=0;i<3;++i){
        if(s.at(i)==t.at(i)){
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
int absolute(int n)
{
    if (n < 0) {
        return (-n);
    }
    return n;
}

double absolute(double n)
{
    if (n < 0) {
        return (-n);
    }
    return n;
}

void input(vector<int>& vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cin >> vec.at(i);
    }
}

void print(vector<int> vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec.at(i) << " ";
    }
    cout << endl;
}

void print(vector<double> vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec.at(i) << " ";
    }
    cout << endl;
}

int sum(vector<int> vec)
{
    int s = accumulate(vec.begin(), vec.end(), 0);
    return s;
}

double sum(vector<double> vec)
{
    double s = accumulate(vec.begin(), vec.end(), 0.0);
    return s;
}

void upsort(vector<int>& vec)
{
    sort(vec.begin(), vec.end());
}

void downsort(vector<int>& vec)
{
    sort(vec.begin(), vec.end(), greater<int>());
}

int maxvec(vector<int> vec)
{
    int m = vec.at(0);
    for (size_t i = 0; i < vec.size(); ++i) {
        m = max(m, vec.at(i));
    }
    return m;
}

int minvec(vector<int> vec)
{
    int m = vec.at(0);
    for (size_t i = 0; i < vec.size(); ++i) {
        m = min(m, vec.at(i));
    }
    return m;
}
///////////////////////////////////////////////////////////

Measured memory_bytes: 256
/*                    ___          |\    /|           ____   ____   ____  ____
   |     |    /\    /    \ |     | | \  / |    /\    |    \ |    \ |     |    \
   |_____|   /__\   \____  |_____| |  \/  |   /__\   |____/ |____/ |__   |____/
   |     |  /    \       \ |     | |      |  /    \  |      |      |     |   \
   |     | /      \ \____/ |     | |      | /      \ |      |      |____ |    \
*/
#include<bits/stdc++.h>
using namespace std;
#define isko_lga_dala_to_life_jhinga_la_la ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lb lower_bound
#define ub upper_bound
#define pf push_front
#define pb push_back
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define pld pair<long double,long double>
#define endl '\n'
#define loop(i,n) for(ll i=0;i<n;i++)
#define mod ((ll)(1e9+7))
#define in(x) scanf("%lld",&x)
#define in2(x,y) scanf("%lld %lld",&x,&y)
#define in3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define inv(v) for(auto&i:v) in(i)
#define vl vector<ll>
#define ml unordered_map<ll,ll> 
#define vpl vector<pair<ll,ll>>
#define INF 0x3f3f3f3f

template<typename T, typename TT>
ostream& operator<<(ostream &os, const pair<T, TT> &t) { return os<<t.first<<" "<<t.second; }
template<typename T>
ostream& operator<<(ostream& os, const vector<T> &t) { for(auto& i: t) os<<i<<" "; return os; }

int main() {
    ll n;
    in(n);
    string a,b;
    cin>>a>>b;
    loop(i,n) {
        cout<<a[i]<<b[i];
    }
    
    return 0;
}

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

int main(){
  char t[200005];  scanf("%s", t);
  long len = strlen(t);
  for(int i=0; i<len-1; i++){
    if(t[i] == '?'){
      if(t[i+1] == 'D' && t[i-1] != 'P'){
	printf("P");
      }else{
	printf("D");
      }
    }else{
      printf("%c", t[i]);
    }
  }
  if(t[len-1] == '?'){
    printf("D\n");
  }else{
    printf("%c\n", t[len-1]);
  }
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  for(int i = 0; i < n; i++) {
    cin >> s.at(i);
  }
  string ans;
  int alp = 26;
  for(int i = 0; i < alp; i++) {
    int cnt = 10000;
    for(int j = 0; j < n; j++) {
      int tmp = 0;
      for(int k = 0; k < s.at(j).size(); k++) {
        if('a' + i == s.at(j).at(k)) {
          tmp++;
        }
      }
      cnt = min(tmp, cnt);
    }
    for(int l = 0; l < cnt; l++) {
      ans.push_back('a' + i);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
	static Scanner input = new Scanner(System.in);
	
	public static void main(String[] args){
		int n;
		n = input.nextInt();
		int A[] = new int[n+1];
		int cnt = 0;
		for(int i = 1 ;i <= n ; i++)
			A[i] = input.nextInt();
		for(int i = 1 ;i <= n ; i++){
			for(int j = i+1 ;j <= n ; j++){
				if(A[i] != i && A[j] == i){
					A[j] = A[i];
					A[i] = i;
					cnt++;
				}
			}
		}
		if(cnt <= 1)
			System.out.println("YES");
		else
			System.out.println("NO");
	}	
}

Measured memory_bytes: 22996
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        // str = reverse(str);
        // System.out.println(str.substring(6, 11));
        String[] divide = new String[]{"dream", "dreamer", "erase", "eraser"};
        for(int i=0;i<4;i++){
            divide[i] = reverse(divide[i]);
        }
        str = reverse(str);
        boolean can = true;
        for(int i=0;i<str.length();){
            boolean can2 = false;
            for(int j=0;j<4;j++){
                String d = divide[j];
                try {
                    if(str.substring(i, i+d.length()).equalsIgnoreCase(d)){
                        can2 = true;
                        i += d.length();
                    }
                } catch (StringIndexOutOfBoundsException e) {
                    continue;
                }
                
            }
            if(!can2){
                can = false;
                break;
            }
        }
        if(can){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
    public static String reverse(String arg){
        char[] chStr = arg.toCharArray();
        StringBuilder builder = new StringBuilder();
        for(int i=chStr.length; i>0; i--){
            builder.append(chStr[i-1]);
        }
        return builder.toString();
    }
}

Measured memory_bytes: 29536
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define inf std::numeric_limits<int>::max();
#define highest_2_pow(n)  __builtin_clzll((long long)0)- __builtin_clzll((long long)n) - 1
//-----------------------------------------------------------------------------------------------------
#define lli long long int 
#define int long long
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi vector<int>
#define vlli vector<long long int>
#define si set<int>
#define slli set<long long int>
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
//---------------------------------------------------
using namespace std;
// GCD and LCM are available
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}

void faster(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
int get_occ(string &s,int pos){
    auto fpos = s.find("AB",pos);
    if(fpos==string::npos) return 0;
    else return 1+get_occ(s,min(fpos+2,s.size()-1));

}
void solve(){
    int n;
    cin>>n;
    int occ = 0;
    string s;
    int ba=0,b=0,a=0;
    rep(i,0,n){
        cin>>s;
        occ+=get_occ(s,0);
        if(s.front()=='B' && s.back()=='A') ba++;
        else if(s.front()=='B') b++;
        else if(s.back()=='A') a++;
    }
    if(a>0 && b>0){
        occ+=(ba-1)+2;
        a--;b--;
        occ+=min(a,b);
    }
    else if(a==0 && ba>0) occ+=ba-1+(b>0);   
    else if(b==0 && ba>0) occ+=ba-1+(a>0);

    cout<<occ<<endl;
}
signed main()
{
    faster();
    int t=1;
    //cin>>t;
    while(t--) solve();
}

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

int main() {
  int N;
  int sum = 0;
  cin >> N;
  while(N--) {
    int a;
    cin >> a;
    if(a >= 2) {
      ++sum;
      for(int i = 2; i*i <= a; ++i) {
	if(a % i == 0) {
	  --sum;
	  break;
	}
      }
    }
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 1160
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let a = read::<i64>();
    let b = read::<i64>();
    let mut hseq = vec![0; n];
    for i in 0..n {
        hseq[i] = read::<i64>();
    }
    hseq.sort();
    let mut left = 0;
    let mut right = 1 << 30;
    while right - left > 1 {
        let mid = (left + right) / 2;
        let mut rest = mid;
        let d = a - b;
        for i in 0..n {
            let cnt = (std::cmp::max(0, hseq[i] - b * mid) + d - 1) / d;
            rest -= cnt;
        }
        if rest < 0 {
            left = mid;
        } else {
            right = mid;
        }
    }
    println!("{}", right);
}


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

using namespace std;


int main() {
  char input[4];

  for(int i = 0; i < 4; i++){
    scanf("%c", &input[i]);
  }

  int ans = 0;

  for(int i = 0; i < 4; i++){
    if(input[i] == '-'){
      ans--;
    }else{
      ans++;
    }
  }

  printf("%d", ans);

  return 0;
}


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

#define int long long

const int N = 3e5 + 7;
const int mod = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int mul(int a, int b) {
    return (a * (ll) b) % mod;
}

int pw(int x, int n) {
    int res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = mul(res, x);
            n--;
        }
        x = mul(x, x);
        n /= 2;
    }
    return res;
}

int fact[N];
int rfact[N];

int C(int n, int k) {
    return mul(fact[n], mul(rfact[n - k], rfact[k]));
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = mul(fact[i - 1], i);
    }
    rfact[N - 1] = pw(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) {
        rfact[i] = mul(rfact[i + 1], i + 1);
    }
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    int ans = 0;
    for (int j = b + 1; j <= w; j++) {
        int i = h - a;
        int cnt = C(i - 1 + j - 1, i - 1);
        int kek = C(h - i + w - j - 1, h - i - 1);
        add(ans, mul(cnt, kek));
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 4992
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

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

ll lcm(ll a,ll b){
	return a * b / gcd(a,b);
}





signed main(){
	ll n,ans = 0,memo = 0;
	cin >> n;

	ll h[n];

	rep(i,0,n) cin >> h[i];

	repr(i,1,n){

		if(h[i] <= h[i-1]){
			memo++;
		}
		else{
			ans = max(ans,memo);
			memo = 0;
		}
	}

	ans = max(memo,ans);
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
R = I()
G = I()
x = G - R
print(G + x)

Measured memory_bytes: 68548
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
typedef long long ll;

#define MAX 2000000 

int h;
int a[MAX];

int parent(int i){return i/2;};
int left(int i){return 2*i;};
int right(int i){return 2*i+1;};

void maxHeapify(int i){
  int l = left(i);
  int r = right(i);
  int max = a[i];
  if(l <= h && a[l] > max) max = a[l];
  if(r <= h && a[r] > max) max = a[r];
  if(max == a[l]){
    swap(a[i], a[l]);
    maxHeapify(l);
  }
  if(max == a[r]){
    swap(a[i], a[r]);
    maxHeapify(r);
  }
}

int main(){
  cin >> h;

  REP(i, 1, h) cin >> a[i];

  REPR(i, h/2, 1) maxHeapify(i);

  REP(i, 1, h) cout << " " << a[i];
  cout << endl;

  return 0;
}





Measured memory_bytes: 5000
import collections

n = int(input())

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

arr3 = collections.Counter(arr)

flg = 1
ans = 0

for i,j in arr3.items():
	if i != j:
		if i < j:
			ans += j - i
		else:
			ans += j
print(ans)
		


Measured memory_bytes: 18676
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        if(s.charAt(0) != 'A'){
            System.out.println("WA");
            return;
        }
        int cnt = 0;
        boolean can = false;
        for(int i = 1;i < s.length();i++){
            if(s.charAt(i) == 'C' && (i == s.length()-1 || i == 1)){
                can = false;
                break;
            }
            if(s.charAt(i) == 'C'){
                can = true;
                cnt++;
                if(cnt >= 2){
                    can = false;
                    break;
                }
                continue;
            }
            if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'){
                can = false;
                break;
            }
        }
        if(can){
            System.out.println("AC");
            return;
        }
            System.out.println("WA");
    }
}


Measured memory_bytes: 23252
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

vector<int> a(105);

int main(){
    int n;
    double m;
    cin >> n>> m;
    int num=0;
    double tol=0;
    rep(i,n){
        cin >> a[i];
        tol+=a[i];
    }
    rep(i,n){
        if(a[i]>=tol/(4*m))num++;
    }
    if(num>=m){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int ROOT = 0;

const int maxn = 4005;
vector<int> g[maxn];
int n, k;

int ans = inf;

int d[maxn][maxn];
int cnt[maxn];
void dfs(int u, int prev = -1) {
    cnt[u] = 1;
    for (int v: g[u]) {
        if (v == prev)
            continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
    d[u][0] = cnt[u] - 1;
    for (int i = 1; i <= k; ++i) {
        d[u][i] = d[u][i - 1];
        int sum = 0;
        int allh = min(i, k - i);
        int bestd = 0;
        for (int v: g[u]) {
            if (v != prev) {
                int need = (allh == 0 ? cnt[v] : d[v][allh - 1]);
                sum += need;
                bestd = min(bestd, d[v][i - 1] - need);
            }
        }
        d[u][i] = min(d[u][i], sum + bestd);
        //cerr << u + 1 << ' ' << i << ' ' << d[u][i] << '\n';
        ans = min(ans, d[u][i] + n - cnt[u]);
    }
}

int main() {
    #ifdef LOCAL
    assert(freopen("c.in", "r", stdin));
    #else
    #endif
    cin >> n >> k;
    forn (i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(ROOT);
    cout << ans << '\n';
}


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

using namespace std;

typedef long long ll;


const int N=2e5+10;
const int MOD=1e9+7;


int n;

map <int,int> ma;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int val;
        scanf("%d",&val);
        ma[val]++;
    }
    int m;
    scanf("%d",&m);
    while (m--){
        int val;
        scanf("%d",&val);
        if (!ma[val]) {
            cout<<"NO";
            return 0;
        }
        ma[val]--;
    }
    cout<<"YES";
}


Measured memory_bytes: 9600
n, m = map(int,input().split())
ps = [1]
nw = 1
mi = m//n
while nw**2 < m:
    if m%nw == 0:
        if mi >= nw:
            ps.append(nw)
        if mi >= m//nw:
            ps.append(m//nw)
    nw += 1
if nw**2 == m and nw <= mi:
    ps.append(nw)

print(max(ps))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long LL;
typedef unsigned long long ULL;
const LL LINF = 0x3f3f3f3f3f3f3f3f; 
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const ULL P = 131;
const int N = 2e5+7;


int main()
{
	LL n,t,flag=1,ans=0;
	cin>>n;
	__int128_t num = 1;
	LL k = 1e18;
	for(int i=1;i<=n;i++) {
		cin>>t;
		num*=t;
		if(num > k) ans=-1;
		if(t==0) flag=0; 
	}
	if(ans!=-1) ans = num;
	if(flag==0) cout<<"0\n";
	else cout<<ans<<endl;
	return 0;
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  ll a, b, c;
  cin >> a >> b >> c;

  cout << b + min(c, a + b + 1) << endl;




  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool chk(long long x,long long y,long long d){if((x*x+y*y-d*d)>0){return false;}return true;}
int main()
{
    long long n,d,ans=0,x,y;
    cin >>n>>d;
    for(long long i=0;i<n;i++){cin >>x>>y;if(chk(x,y,d)){ans++;}}
    cout <<ans<<'\n';
    return 0;
}

Measured memory_bytes: 3584
import sys


def num_list(nums):
    if len(nums) == 1:
        return [nums]
    result = []
    for num in nums:
        next_nums = nums.copy()
        next_nums.remove(num)
        result += list(map(lambda x: [num] + x, num_list(next_nums)))
    return result


def solve(inp):
    N = int(inp.readline().strip())
    P = list(map(int, inp.readline().strip().split(' ')))
    Q = list(map(int, inp.readline().strip().split(' ')))

    nl = num_list(list(range(1, N + 1)))
    p = nl.index(P)
    q = nl.index(Q)

    return str(abs(p - q))


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9716
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }

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

ll in(){long long int x; scanf("%lld", &x); return x;}
ld fin(){double x; scanf("%lf", &x); return x;}
char yuyushiki[1000010]; string stin(){scanf( "%s", yuyushiki ); return yuyushiki;}

// head

ll n;
ll a[64];

int main(){

  n = in();
  REP(i, n){
    a[i] = in();
  }

  ll ans = 0;
  while(1){
    int p = max_element(a, a+n) - a;
    if(a[p] < n){
      break;
    }
    ll c = a[p] / n;
    REP(i, n){
      if(i != p){
        a[i] += c;
      } else {
        a[i] = a[i] % n;
      }
    }
    ans += c;
  }

  printf("%lld\n", ans);
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main() {
	int Adj[100][100];
	int n, u, k, v;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Adj[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			cin >> v;
			v--;
			Adj[u][v] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j != 0) cout << " ";
			cout << Adj[i][j];
		}
		cout << endl;
	}
}
	

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

bool palindrome(string s, int a, int b) {
    for (int i = a-1, j = b-1; i < j; i++, j--) {
        if (s[i] != s[j]) return false;
    }

    return true;
}

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

    int s_size = s.size();
    bool ok = palindrome(s, 1, s_size) && palindrome(s, 1, (s_size-1)/2) && palindrome(s, (s_size + 3)/2, s_size);
    if (ok) cout << "Yes" << '\n';
    else cout << "No" << "\n";
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

int a,b,c;
int main(void){
  cin>>a>>b>>c;

  int x,y,z;
  x=max(a,max(b,c));
  z=min(a,min(b,c));
  y=a+b+c-x-z;

  int res=0;
  res+=(x-y)/2;
  res+=(x-z)/2;


  y+=((x-y)/2)*2;
  z+=((x-z)/2)*2;


  if(x==y && y==z){
    cout<<res<<endl;
  }
  else if(y==z){
    cout<<res+1<<endl;
  }
  else{
    cout<<res+2<<endl;
  }
  return 0;
}

Measured memory_bytes: 256