akhauriyash/Code-Regression huggingface dataset:
// Problem : F - Tree and Constraints
// Contest : AtCoder Beginner Contest 152
// URL : https://atcoder.jp/contests/abc152/tasks/abc152_f
// Memory Limit : 1024.000000 MB 
// Time Limit : 4000.000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

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

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll=long long;
using pii=pair<int, int>;
#define int ll
const int MOD = 1000000007;

vector<int> elist[55];
int fa[55][8], dep[55];

void dfs(int node, int par) {
	int v = 0;
	fa[node][v] = par;
	while(fa[node][v] != -1) {
		fa[node][v+1] = fa[fa[node][v]][v];
		v++;
	}
	while(v != 8) fa[node][v++] = -1;
	if(par == -1) dep[node] = 0;
	else dep[node] = dep[par]+1;
	for(int i:elist[node]) if(i != par) dfs(i, node);
}

int lca(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	for(int i=7; i>=0; i--)
		if(fa[a][i] != -1 && dep[a] - (1<<i) >= dep[b]) a = fa[a][i];
	for(int i=7; i>=0; i--)
		if(fa[a][i] != -1 && fa[b][i] != -1 && fa[a][i] != fa[b][i]) {
			a = fa[a][i];
			b = fa[b][i];
		}
	if(a != b) return fa[a][0];
	return a;
}

uint64_t mask[25];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n; cin >> n;
	rep(i, n-1) {
		int u, v; cin >> u >> v;
		elist[u].pb(v);
		elist[v].pb(u);
	}
	dfs(1, -1);
	int m; cin >> m;
	rep(i, m) {
		int a, b; cin >> a >> b;
		int lc = lca(a, b);
		while(b != lc) {
			mask[i] |= (1ull<<b);
			b = fa[b][0];
		}
		while(a != lc) {
			mask[i] |= (1ull<<a);
			a = fa[a][0];
		}
	}
	uint64_t ans = 0;
	rep(bm, 1ull<<m) {
		uint64_t tree = 0;
		int cnt = 0, free = 0;
		rep(i, m) {
			if(bm & (1ull<<i)) {
				tree |= mask[i];
				cnt++;
			}
		}
		iter(i, 2, n+1) if(!(tree & (1ull<<i))) free++;
		if(cnt%2) ans -= (1ull<<free);
		else ans += (1ull<<free);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define pi acos(-1)
using namespace std;
int main()
{
    ll i,f=0;
   char a[5];
   cin>>a;
   for(i=0;i<3;i++)
   {
       if(a[i]==a[i+1])
       {
           f=1;
           break;
       }
   }
   if(f==1)
    cout<<"Bad"<<endl;
   else
    cout<<"Good"<<endl;


    return 0;
}



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


int main() {
  int n ;
  cin >> n ;
  string s ;
  cin >> s ;
  
  string a , b ;
    for(int i=0;i<n/2 ;i++){
      a+=s.at(i);
      b+=s.at(i+n/2);
    }
  
  if(n%2==1){
    cout << "No" << endl;
  }
  
  
  else if(a==b){
      cout << "Yes" << endl;
    }
  
  else{
      cout << "No" << endl;
    }
  
  

}

Measured memory_bytes: 256
W,H,N = map(int,input().split())
L,R,D,U = 0,W,0,H

for i in range(N):
  x,y,a = map(int,input().split())
  if a==1:
    L=max(L,x)
  elif a==2:
    R=min(R,x)
  elif a==3:
    D=max(D,y)
  else:
    U=min(U,y)

print(max(0,R-L)*max(0,U-D))

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

using namespace std;
using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

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

    ll mn = 1e10;
    for (int i = 0; i <= N; i++) {
        ll val = 1;
        for (int k = 0; k < i; k++) {
            val *= 2;
        }
        for (int k = 0; k < (N-i); k++) {
            val += K;
        }
        mn = min(mn, val);
    }

    cout << mn << endl;

    return 0;
}

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

int main(){
    char S[103];
    int N;
    scanf("%s",S);
    N = strlen(S);
    int flg = 1;
    for(int i = 0 ; i <= (N-1)/2 ; i++){
        if(S[i] != S[(N-1)-i]){
            flg = 0; 
            break;
        }
    }
    if(flg == 1){
        for(int i = 0 ; i <= (N-1)/2 - 1 ; i++){
            if(S[i] != S[(N-1)/2 - 1 - i]){
                flg = 0; 
                break;
            }
        }
        for(int i = (N+3)/2 -1 ; i <= (N-1) / 2 ; i++){
            if(S[i] != S[ (N-1)/2 - i + (N+3)/2 - 1]){
                flg = 0; 
                break;
            }
        }
    }
    if(flg == 0){
        printf("No");
    }else{
        printf("Yes");
    }
    return 0;
}

Measured memory_bytes: 128
x,y = [int(it) for it in input().split()]

s = 10000000000

ds = y-x
if (ds>=0):
  s = min(s,ds)
ds = y+x
if (ds>=0):
  s = min(s,1+ds)
ds = -y-x
if (ds>=0):
  s = min(s,1+ds)
ds = -y+x
if (ds>=0):
  s = min(s,2+ds)
print (s)
  


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int q = scanner.nextInt();
		DisjoinSet ds = new DisjoinSet(n);
		for (int i = 0; i < q; i++) {
			int t = scanner.nextInt();
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			if (t == 0)
				ds.unite(a, b);
			else {
				if (ds.same(a, b))
					System.out.println(1);
				else
					System.out.println(0);
			}

		}

	}

	class DisjoinSet {
		int[] rank;
		int[] p;

		DisjoinSet() {
		}

		DisjoinSet(int size) {
			rank = new int[size];
			p = new int[size];
			for (int i = 0; i < size; i++) {
				makeSet(i);
			}
		}

		void makeSet(int x) {
			p[x] = x;
		}

		boolean same(int x, int y) {
			return findSet(x) == findSet(y);
		}

		private int findSet(int x) {
			if (x != p[x]) {
				p[x] = findSet(p[x]);
			}
			return p[x];
		}

		void unite(int x, int y) {
			link(findSet(x), findSet(y));
		}

		private void link(int x, int y) {
			if (rank[x] > rank[y]) {
				p[y] = x;
			} else {
				p[x] = y;
				if (rank[x] == rank[y]) {
					rank[y]++;
				}
			}
		}
	}
}

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

int main() {
    int n;
    cin >> n;
    int a[n];
    int64_t m = 1;
    rep(i,n) {
        cin >> a[i];
        if (a[i] % 2 == 0) m *= 2; 
    }
    int64_t ans = pow(3, n) - m;
    cout << ans << endl;
}

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

using namespace std;

#define print(s) cout << (s) << endl;
#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n) 
#define all(a) a.begin(), (a).end()
#define inf = 9876543210
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    if (k%2 == 0){
        print(pow(k/2, 2));
    } else {
        print((k/2) * (k/2+1));
    }
return 0;
}

Measured memory_bytes: 256
def check():
    for i in range(3):
        f1 = True
        f2 = True
        for j in range(3):
            f1 = f1 and card[i][j]
            f2 = f2 and card[j][i]
        if f1 or f2:
            return 'Yes'
    f1 = True
    f2 = True
    for i in range(3):
        f1 = f1 and card[i][i]
        f2 = f2 and card[i][2-i]
    if f1 or f2:
        return 'Yes'
    return 'No'

card = [[False] * 3 for _ in range(3)]
A = []
for _ in range(3):
    a = list(map(int, input().split()))
    A += a
N = int(input())
for _ in range(N):
    b = int(input())
    if b in A:
        idx = A.index(b)
        card[idx // 3][idx % 3] = True
print(check())

Measured memory_bytes: 9148
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
using ll=long long;

const ll INF = pow(10,18)+1;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}
 
int main(){
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << (H-h)*(W-w) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 0;
        int b = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0)
                a++;
            else
                b++;

        }
        
        System.out.println((double) b / (a + b));
    }
}

Measured memory_bytes: 23892
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as B
import Data.List

solve :: V.Vector String -> String
solve xss = V.foldl' step (V.head xss) (V.tail xss)
        where
            step :: String -> String -> String
            step [] _ = []
            step (x:xs) ys
                | x `elem` ys = x : step xs (delete x ys)
                | otherwise = step xs ys

main = do
    n <- readLn :: IO Int
    xss <- V.replicateM n (B.unpack . B.sort <$> B.getLine)
    putStrLn $ solve xss

Measured memory_bytes: 1020
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

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

    int r, n;
    while(cin >> r >> n, r != 0){
        vector<int> maxHigh(40, 0);

        REP(i, n){
            int x, y, z;
            cin >> x >> y >> z;
            REP(j, y-x) maxHigh[20+x+j] = max(z, maxHigh[20+x+j]);
        }

        double ans = 20;
        for(int i = -r+1; i <= r-1; i++){
            int high = min(maxHigh[19+i], maxHigh[20+i]);
            double t = high + r - sqrt(r*r -i*i);
            ans = min(t, ans);
        }

        printf("%.9f\n", ans);
    }
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int,int>
#define endl "\n"
#define MAXN 100005
#define mod 1000000007
using namespace std;

void solve()
{
    
}
ll find(ll x, vector<ll> & parent)
{
    if(parent[x] == x)
    {
        return x;
    }
    ll node = find(parent[x], parent);
    parent[x] = node;
    return node;
}
void union_set(ll x, ll y, vector<ll> & parent, vector<ll> &size)
{
    x = find(x, parent);
    y = find(y, parent);
    if(x != y)
    {
        if( size[x] < size[y] )
        {
            parent[x] = y;
            size[y] += size[x];
        }
        else
        {
            parent[y] = x;
            size[x] += size[y];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
    ll n,m;
    cin>>n>>m;
    vector<ll> parent(n + 1, -1);
    vector<ll> size(n + 1, 1);
    for(ll i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    for(ll i=0; i<m; i++)
    {
        ll a,b;
        cin>>a>>b;
        union_set(a, b, parent, size);
    }
    ll ans = -1;
    for(ll i=1; i<=n; i++)
    {
        ans = max(ans, size[i]);
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 6344
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
//const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    map<ll,int> mp;
    REP(i,N){
        ll a;
        cin >> a;
        mp[a]++;
    }
    ll ans = 0;
    int i=0;
    while(i < N && !mp.empty()){
        ll cur = mp.rbegin() -> first;
        mp[cur]--;
        if(mp[cur] == 0) mp.erase(cur);
        ll p = 1;
        while(p <= cur) p *= 2;
        ll rest = p - cur;
        if(mp.count(rest)){
            ans++;
            mp[rest]--;
            if(mp[rest] == 0) mp.erase(rest);
        }
        i++;
    }
    cout << ans << endl;
}

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

int main(void)
{
    char S[3];
    int ans=0;
    scanf("%s",&S);

    if (strcmp(S,"RRR")==0) ans=3;
    if (strcmp(S,"RRS")==0) ans=2;
    if (strcmp(S,"SRR")==0) ans=2;
    if (strcmp(S,"RSS")==0) ans=1;
    if (strcmp(S,"SRS")==0) ans=1;
    if (strcmp(S,"SSR")==0) ans=1;
    if (strcmp(S,"RSR")==0) ans=1;
    if (strcmp(S,"SSS")==0) ans=0;

    printf("%d\n",ans);
}   

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

int main()
{
	int l=0,r=1,len,sum=0,bl[100050];
	string s;
	cin>>s;
	len=s.size();
	for(int i=0;i<=len;i++)
	bl[i]=0;
	while(r<len)
	{
		//cout<<l<<" "<<r<<endl;
		if(s[l]+s[r]-'0'-'0'==1)
		{
			bl[l]=1;bl[r]=1;
			sum+=2;r++;
			while(l>=0)
			{
				if(bl[l]==1)l--;
				else break;
			}
			if(l<0)
			{
				r++;
				l=r-1;
			}
		}
		else
		{
			r++;
			//l++;
			l=r-1;
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

int main(){
    ll N,ac=0,wa=0,tle=0,re=0;
    cin >> N;
    
    vector<string> v(N);
    for(ll i = 0;i < N;i++)
        cin >> v.at(i);

    for(ll i = 0;i < N;i++){
        if(v.at(i) == "AC")
            ac++;
        else if(v.at(i) == "WA")
            wa++;
        else if(v.at(i) == "TLE")
            tle++;
        else
            re++;
    } 

    cout << "AC" << "  " << "x" <<"  "<<ac << endl;
    cout << "WA" << "  " << "x" << "  " <<wa << endl;    
    cout << "TLE" << "  " << "x" << "  " <<tle << endl;
    cout << "RE" << "  " << "x" << "  "<<re << endl;
}

Measured memory_bytes: 6424
gets.to_i
as = gets.split(' ').map { |e| e.to_i }

m = Hash.new(0)
as.each { |e| m[e] += 1 }

res = m.select { |k,v| v > 1 }.sort { |a, b| b[0] <=> a[0] }

if res.empty?
  puts 0
elsif res[0][1] >= 4
  puts res[0][0] * res[0][0]
elsif res.length > 1
  puts res[0][0] * res[1][0]
else
  puts 0
end  



Measured memory_bytes: 16264
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using intl = int64_t;
using graph = vector<vector<int> >;
int main(){
    int n;
    cin >> n;
    vector<string> s;
    for(int i=0;i<n;i++){
        string l;
        cin >> l;
        s.push_back(l);
    }
    //for(int i=0;i<n;i++) cout << s.at(i) << endl;

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

    // for(int i=0;i<n;i++) cout << s.at(i) << endl;

    map<string,int> vote;
    vote[s.at(0)]=1;
    for(int i=1;i<n;i++){
        if(s.at(i-1)==s.at(i)){
            vote.at(s.at(i-1))++;
        }else{
            vote[s.at(i)]=1;
        }
    }

    int counter=0;
    for(auto p: vote){
        auto key=p.first;
        auto value=p.second;

        counter= max(vote.at(key),counter);
    } 

    for(auto p: vote){
        auto key=p.first;
        auto value=p.second;

        if(vote.at(key)==counter) 
            cout << key << endl;
    } 
}

Measured memory_bytes: 25068
S = input()
s = [S[:2], S[2:]]

if (int(s[0]) <= 12) and (int(s[0]) > 0):
    if (int(s[1]) <= 12) and (int(s[1]) > 0):
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if (int(s[1]) <= 12) and (int(s[1]) > 0):
        print("YYMM")
    else:
        print("NA")

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
using namespace std;


int main(){
	int n;
	int a[100005];
	int x=2;
	long long s=0;
	for (int i = 0; i < 100005; i++){
		a[i] = 0;
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
       scanf("%d", &a[i]);
	}
	s = s + a[0] - 1;
	for (int i = 1; i < n; i ++){
		if (a[i] >x){
			s = s + ((a[i] - 1) / x);
		}
		else if (a[i] == x ){
			x++;
		}
	}
	printf("%lld", s);
	return 0;
}

Measured memory_bytes: 640
/*
对应原理
其实每次只有两种选择，所有这个题的对拍很好写
怎么确定能不能达到最大值呢
跑步的速度是可以加快的，每次贪心选择能行吗
有一些能够拿两次，最终答案一定是要将什么拿两次的

最快的办法当然是永不回头，但是最慢的办法并不是一步一回头
我们要积累7+7+1=15
顺时针能够拿两次
为了把很大的一个数拿两次，必须他的补集中有能够回去的，并且那个数字一定是我右边紧邻的那个
为了拿到这一个7两次，顺时针必须留一个，
就意味着逆时针3次对应顺时针1次
并且必须先逆3
为了拿到这个4两次，顺时针留一个
则逆2顺2 且逆先
为了拿到3两次，顺时针留一个
逆1顺3

i n-i
当i<n-i时
左i 右(i+1)减去最左边 最后一次是顺时针 a[1...i]*2+((i+1)*2*n-a[i+1...i+i+1]*2)-(n-a[i+1])
左i减去最右边 右i 最后一次是逆时针     a[1...i]*2+(i*2*n-a[i+1...i+i]*2)-a[i]

i=n-i时
左i右i 减去左或减去右   a[1...i]*2+(i*2*n-a[i+1...i+i]*2)-a[i]/a[1...i]*2+(i*2*n-a[i+1...i+i]*2)-a[i+1]
i>n-i时
左n-i+1减去最右边 右n-i
左n-i，右n-i减去最左边
*/
#include<bits/stdc++.h>
#define MAXN 200005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const ll INF=1e18;
ll n,x,mypow[35],ans;
multiset<ll>ms;
void init()
{
    mypow[0]=1;
    for(ll i=1;i<=32;i++)
    {
        mypow[i]=mypow[i-1]*2;
    }
}
int main()
{
    init();
//    ms.insert(2);
//    ms.insert(2);
//    printf("%d",ms.find(2)==ms.begin());
//    freopen("c://duipai//939cdata.txt", "r", stdin);
//    freopen("c://duipai//939cwa.txt", "w", stdout);
    while(~scanf("%lld",&n))
    {
//        string str;
//        cin>>str;
//        cout<<str<<endl;
        for(ll i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            ms.insert(x);
        }
        for(multiset<ll>::reverse_iterator it=ms.rbegin();it!=ms.rend();it++)
        {
            x=*it;
            ll p=upper_bound(mypow+1,mypow+1+32,x)-mypow;
            ll y=mypow[p]-x;
            multiset<ll>::iterator it1=ms.find(y);
            if(it1==ms.end())
            {
                continue;
            }
            multiset<ll>::iterator it2=(++it).base();
            if(it2!=it1)
            {
                ms.erase(it1);
                ans++;
            }
            it--;
        }
        printf("%lld\n",ans);
    }
}
/*
*/


Measured memory_bytes: 9600
import numpy as np
N = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
  
def z(p):
    n = (-1+np.sqrt(1+8*p))/2
    return int(n)
arr = factorization(N)
if N == 1:
    print(0)
else:
    print(np.sum([z(a[-1]) for a in arr]))

Measured memory_bytes: 27280
n, MOD = int(input()), 10 ** 9 + 7

memo = [{} for _ in range(n+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in "AGCT":
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Measured memory_bytes: 3880
#include<stdio.h>
int main(void){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a<b){
        printf("a < b\n");
    }
    else if(a>b){
        printf("a > b\n");
    }
    else{
        printf("a == b\n");
    }
    return 0;
}


Measured memory_bytes: 2056
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,y;
    cin>>x>>y;
    if((x+y)%3){
        cout<<"0"<<endl;
        return 0;
    }
    int n=(x+y)/3,r=x-n;//nCr
    if(r<0 || r>n){
        cout<<"0"<<endl;
        return 0;
    }
    if(r==0 || r==n){
        cout<<"1"<<endl;
        return 0;
    }
    const int mod=1000000007;
    long long a=1;
    for(int i=1;i<=r;i++){
        a*=i;
        a%=mod;
    }
    long long b=a;
    a=1;
    for(int i=mod-2;i;i/=2){
        if(i%2){
            a*=b;
            a%=mod;
        }
        b*=b;
        b%=mod;
    }
    for(int i=n;i>n-r;i--){
        a*=i;
        a%=mod;
    }
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define Rrep(i,y,x) for(ll i=y;i>x;i--)
#define SIZE(a) ll(a.size())
#define vll vector<ll>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define print(x) cout << (x) << endl
#define printvec(x) for(ll i=0;i<x.size();i++) cout << (x.at(i)) <<' ' 
typedef long long ll;
using namespace std;

int main(){
    ll N;
    cin>>N;
    vector<ll> A(N);
    rep(i,0,N){
        cin>> A.at(i);
    }
    vector<ll> B(N);
    rep(i,0,N){
        cin>> B.at(i);
    }
    vector<ll> num(30);
    vector<ll> L(N),K(N);
    rep(i,0,30){
        ll t = (ll)pow(2,i);
        rep(i,0,N){
            K.at(i)=A.at(i)%(2*t);
            L.at(i)=B.at(i)%(2*t);
        }
        sort(L.begin(),L.end());
        ll a=0;
        rep(i,0,N){
            ll k=K.at(i);
            ll x= lower_bound(L.begin(),L.end(),2*t-k)-lower_bound(L.begin(),L.end(),t-k);
            ll y= lower_bound(L.begin(),L.end(),4*t-k)-lower_bound(L.begin(),L.end(),3*t-k);
            a = (a+x+y)%2;
        }
        num.at(i)=a;
    }
    ll ans=0,s=1;
    rep(i,0,30){
        ans+=num.at(i)*s;
        s*=2;
    }
    print(ans);


}




Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
    string s; cin >> s;
    int Q; cin >> Q;
    deque<char> q;
    for(char c : s) q.push_back(c);
    bool flag = true;
    rep(i,Q){
        int t;cin >> t;
        if(t == 1) flag = !flag;
        else {
            int f; char c; cin >> f >> c;
            if(flag && f == 1) q.push_front(c);
            else if(flag && f == 2) q.push_back(c);
            else if(!flag && f == 1) q.push_back(c);
            else q.push_front(c);
        }
    }
    if(!flag) reverse(ALL(q));
    string ans;
    for(char c : q) ans += c;
    cout << ans << endl;
}

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

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

  long long A = 2, B = 1, C;

  for (int i = 0; i < N - 1; i++) {
    C = A + B;
    A = B;
    B = C;
  }

  cout << B << "\n";
}

Measured memory_bytes: 256
a, v = gets.split.map(&:to_f)
b, w = gets.split.map(&:to_f)
t = gets.to_i

if w - v == 0
  puts 'NO'
elsif w > v
  puts 'NO'
elsif t >= (a - b).abs / (v - w)
  puts 'YES'
else
  puts 'NO'
end

Measured memory_bytes: 14392
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

#define all(c) (c).begin(), (c).end()

int main(){
    int N, Q;
    while(cin >> N >> Q, N|Q){
        typedef tuple<int, int, string> Data;
        vector<Data> era;
        era.reserve(N);
        while(N--){
            string name;
            int eyear, wyear;
            cin >> name >> eyear >> wyear;
            era.emplace_back(wyear - eyear + 1, wyear, name);
        }
        sort(all(era));
        auto comp = [](Data& d, int x){return get<1>(d) < x;};
        while(Q--){
            int query, one = 0, known = 0;
            string name;
            cin >> query;
            if(query <= get<1>(era.back()))tie(one, known, name) = *lower_bound(all(era), query, comp);
            if(one <= query && query <= known)cout << name << " " << query - one + 1 << '\n';
            else cout << "Unknown\n";
        }
    }
    return 0;
}

Measured memory_bytes: 1284
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int count = 0;
        for (int i = 1; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= 9; k++) {
                    if (i * 10001 + j * 1010 + k * 100 >= a && i * 10001 + j * 1010 + k * 100 <= b) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 23892
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int primeCount = 0;
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            if (isPrime(num)) {
                primeCount++;
            }
        }
        System.out.println(primeCount);
    }

    private static boolean isPrime(int num) {
        for (int i = 2; i <= (int) Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}


Measured memory_bytes: 42372
// Author : Mohamed Sameh
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
#define Flush fflush(stdout);
typedef long long ll ;
using namespace std ;
const int M = 100 ;
const int MAXV = 1e5+1; 
const ll MAX = 2e18+9;
ll dp[M][MAXV];
int w[M],v[M];
int N , W ;
int ans ;
int main ()
{   
    scanf ("%d%d" , &N ,&W); 
    for (int i =0 ; i < N ;i++)
    {
        scanf ("%d%d" ,w+i , v+i); 
    }
    // dp[i][j] means 
    // what is the minumum weight to get the value j in range [0 : i]
    for (int i =0 ; i < N ;i++)
        for (int j =0 ; j < MAXV ;j++)
            dp[i][j] = MAX ; 
    for (int i =0 ;i < N ;i++)
        dp[i][ v[i] ] = w[i];
    for (int i =1 ; i < N ; i++)
    {
        for (int j = 1 ; j < MAXV ;j++)
        {
            dp[i][j] = min(dp[i][j] , dp[i-1][j]);
            if (j >= v[i])
            {
                dp[i][j] = min (dp[i][j] , dp[i-1][ j - v[i] ] + w[i]  );
            }
        }
    }
    
    for (int i= 0 ; i < MAXV ;i++)
    {
        if (dp[N-1][i] <= W )
            ans = max (ans , i); 
    }
    printf ("%d\n" , ans); 

}

Measured memory_bytes: 78336
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>

using namespace std;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	ll a[10000];
	ll b[10000];
	ll aSum = 0;
	ll bSum = 0;
	for(int i = 0; i < N; i++){
		cin >> a[i];
		aSum += a[i];
	}
	for(int i = 0; i < N; i++){
		cin >> b[i];
		bSum += b[i];
	}
	
	ll opeCount = bSum - aSum;
	if(opeCount < 0){
		cout << "No" << endl;
		return 0;
	}
	
	ll evenOpe = opeCount;
	ll oddOpe = opeCount;
	
	for(int i = 0; i < N; i++){
		if(a[i] < b[i]){
			evenOpe -= (b[i] - a[i] + 1) / 2;
			oddOpe -= (b[i] - a[i]) % 2;
		}
		else if(b[i] < a[i]){
			oddOpe -= (a[i] - b[i]);
		}
	}
	
	if( evenOpe >= 0 && oddOpe >= 0 && oddOpe == evenOpe * 2){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	
	return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 1000111

typedef long long ll;
typedef long double ld;

int main(){
	string str;
	cin >> str;
	int n = str.length();
	for(int i = 0; i < n - 8; i++)
		cout << str[i];


	return 0;
}

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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, int> P;
const ll INF = 1e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<string, vector<string>, greater<string> > PQ_ASK;


class UnionFind {
public:
    // 親の番号を格納する。親だった場合-size
    vector<int> parents;

    UnionFind(int n) {
        parents = vector<int>(n, -1);
    }

    // aがどのグループに属しているか
    int root(int a) {
        if (parents[a] < 0) {
            return a;
        }
        return parents[a] = root(parents[a]);
    }

    int size(int a) {
        return -parents[root(a)];
    }

    // aとbをくっつける
    bool connect(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra == rb) {
            return false;
        }
        // 大きいほうにA
        if (size(ra) < size(rb)) {
            swap(ra, rb);
        }
        parents[ra] += parents[rb];
        parents[rb] = ra;
        return true;
    }

    bool is_union(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        return ra == rb;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n + m);

    auto lang_id = [&](int l) {
        return n + l;
    };

    rep(i, n) {
        int k;
        cin >> k;
        rep(j, k) {
            int l;
            cin >> l;
            l--;
            uf.connect(i, lang_id(l));
        }
    }

    rep(i, n) {
        if (!uf.is_union(0, i)) {
            cout << "NO" << endl;
            ret();
        }
    }
    cout << "YES" << endl;

}


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

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

int find(string str, const string& word) {
  int count = 0;
  for (string::size_type pos = 0; (pos = str.find(word, pos)) != string::npos; pos += word.size()) {
    ++count;
  }
  return count;
}

int main(){
    long long w, h;
    long long x, y;
    cin >> w >> h >> x >> y;
    long long w_x, h_y;
    double s;
    int ans = 0;
    w_x = w - x;
    h_y = w - x;
    if(w_x == 0 || h_y == 0){
        s = (double)w * (double)h / 2.0;
        ans = 0;
    } 
    else{
        s = (double)w * (double)h / 2.0;
        if((double)x == (double) w /2 && (double)y == (double)h / 2){
            ans = 1;
        }
    }
    cout << s <<' '<<ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stdlib.h>
#include <list>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define inf 0x3f3f3f3f
#define PI acos(double(-1))
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
char s[3][11];

int main()
{
    scanf("%s%s%s",s[0],s[1],s[2]);
    printf("%c%c%c\n",s[0][0]-'a'+'A',s[1][0]-'a'+'A',s[2][0]-'a'+'A');
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
s=set()
fr=0
for i in a:
  x=i//400
  if(x<8):s.add(x)
  else:fr+=1
ki=len(s)
ma=ki+fr
mi=max(ki,1)
print(mi,ma)


Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>
long minf(long a,long b){
  if(a>b){
    return b;
  }else{
    return a;
  }
}

long maxf(long a,long b){
  if(a>b){
    return a;
  }else{
    return b;
  }
}

int main(){
  long n = 0;
  long a[100000][3] = {};
  long dp[100000][3] = {};
  long k = 0;
  long i = 0;
  long j = 0;
  long min = -1;
  long max = -1;
  
  scanf("%ld",&n);
  
  for(i=0;i<n;i++){
    scanf("%ld %ld %ld",&a[i][0],&a[i][1],&a[i][2]);
  }
  
  dp[0][0] = a[0][0];
  dp[0][1] = a[0][1];
  dp[0][2] = a[0][2];
  
  for(i=1;i<n;i++){
    for(j=0;j<3;j++){
      max = -1;
      for(k=0;k<3;k++){
        if(j != k){
          if(max == -1){
            max = dp[i-1][k] + a[i][j];
          }else{
            max = maxf(max,dp[i-1][k] + a[i][j]);
          }
        }
      }
      dp[i][j] = max;
      //printf("%ld.%ld-%ld,",max,i,j);
    }  
  }
  max = maxf(dp[n-1][0],dp[n-1][1]);
  max = maxf(max,dp[n-1][2]);
  printf("%ld",max);
  return 0;
}
    

Measured memory_bytes: 4864
import itertools
N = int(input())
S = input()
ls = list(S)

nr = len([r for r in S if r == 'R'])
nb = len([b for b in S if b == 'B'])
ng = len([g for g in S if g == 'G'])

ALL = nr * nb * ng
count = 0

RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))

for i in range(N):
  for j in range(N-i*2):
    if (S[j], S[j+i], S[j+i*2]) in RGBs:
      count += 1
      
print(ALL - count)

Measured memory_bytes: 9200
import java.io.*;
import java.util.*;
public class Main {
     public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer s = new StringTokenizer(br.readLine()," ");
	int[] input = new int[3];
	input[0] = Integer.parseInt(s.nextToken());
	input[1] = Integer.parseInt(s.nextToken());
	input[2] = Integer.parseInt(s.nextToken());

	for(int i=input.length;i>1;i--){
		for(int j=0;j<i-1;j++){
		if(input[j]>input[j+1]){
			int temp = input[j];
			input[j] = input[j+1];
			input[j+1] = temp;
			}
		}
	}
	System.out.println(input[0] + " " + input[1] +" " + input[2]);
    }
}

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

void show_result(int N)
{
	int max;
	max = sqrt((double)N / (double)6);
	int count = 0;
	for (int x = 1; x <= max; x++)
	{
		int y_max = sqrt((double)(N - x * x) / (double)3) + (double)x * x / (double)9;
		for (int y = x; y <=y_max; y++)
		{
			int z = sqrt((double)(N - x * x - y * y - x * y) + (double)((x + y) * (x + y)) / (double)4) - (double)(x + y) / (double)2;
			if (z < y)
				continue;
			if (x * x + y * y + z * z + x * y + y * z + z * x == N)
			{
				if (x == y && y == z)
					count += 1;
				else if (x == y && y < z)
					count += 3;
				else if (x < y && y == z)
					count += 3;
				else
					count += 6;
			}
		}
	}
	printf("%d\n", count);
}

int main ()
{
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		show_result(i);
	}

	return (0);
}


Measured memory_bytes: 2092
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int bingo[3][3];
bool flag[3][3];
int cnt[2][105];
int h, w;
int choco[1010][1010];
int s[11][11];

int main() {
	int n;
	cin >> n;
	int n2 = sqrt(n);
	int ans = n2 * n2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
//
// Created by watemus on 04.07.2020.
//

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define FF first
#define SS second

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

template<typename T>
using vec = std::vector<T>;

template<typename T>
using uset = std::unordered_set<T>;

template<typename T1, typename T2>
using umap = std::unordered_map<T1, T2>;

constexpr ll INFL = 1'000'000'000'000'000'228;
constexpr int INFI = 1'000'000'228;
const ld PI = acos(-1);
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

vec<pair<int, int>> DD = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

#ifdef LOCAL
#else
#endif

void run() {
  char ch;
  cin >> ch;
  if (isupper(ch)) {
    cout << "A\n";
  } else {
    cout << "a\n";
  }
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

signed main() {
#ifdef LOCAL
  std::freopen("input.txt", "r", stdin);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  int t = 1;
  //cin >> t;
  while (t--) {
    run();
  }
  return 0;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#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(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    rep(i,3) {
	    if (s[i] == '1') {
		    s[i] = '9';
	    } else if (s[i] == '9') {
		    s[i] = '1';
	    }
    }
    cout << s << endl;
    
}


Measured memory_bytes: 256
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
string a,b,sum;
void check(int z,int x);
int A,B;
int main(void){
    int n;
    cin>>n;
    while(n--){
        a="",b="",sum="";
        cin>>a>>b;
        A=a.length(),B=b.length();
        reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
        if(A<B)swap(A,B),swap(a,b);
        for(int i=0;i<=A-B;i++)b+="0";
        check(0,0);
        if(sum.length()>80){
            sum="overflow";
            goto end;
        }
        reverse(sum.begin(),sum.end());
        end:;
        cout<<sum<<endl;
    }
    return 0;
}
void check(int z,int x){
    int i;
    if(a[z]==0)a[z]='0';
    if(b[z]==0)b[z]='0';
    if(z==81||(z>A&&z>B&&x==1)||(z>=A&&z>=B&&x==0)){
            x=0;
            return;
    }
    i=(int)a[z]-'0' + (int)b[z]-'0' + x,x=0;
    if(i>=10)x=1,i-=10;
    sum+=i+'0';
    check(z+1,x);
}

Measured memory_bytes: 1204
import scala.io.StdIn.{readInt,readLine}

object Main {

  def printStable(l:Array[(Char,Int)],a:Array[(Char,Int)]) = {
    val s = l.groupBy(_._2).filter(_._2.length > 1)
    var stable = true

    for {
      i <- s
      if stable
    }
      if(a.filter(_._2 == i._1).toSeq != i._2.toSeq)
        stable = false

    if(stable)
      println("Stable")
    else
      println("Not stable")
  }

  def swap(a:Array[(Char,Int)],x:Int,y:Int) = {
    val t = a(x)
    a(x) = a(y)
    a(y) = t
  }

  def bubbleSort(a:Array[(Char,Int)]) =
    for(i <- 0 until a.length)
      for(j <- a.length-1 to i+1 by -1)
        if(a(j)._2 < a(j-1)._2)
          swap(a,j,j-1)

  def selectionSort(a:Array[(Char,Int)]) =
    for(i <- 0 until a.length) {
      var mini = i
      for(j <- i until a.length)
        if(a(j)._2 < a(mini)._2) mini = j
      swap(a,i,mini)
    }

  def main(args:Array[String]) = {
    val n = readInt
    val l = readLine.split(" ").map(s => (s(0),s.drop(1).toInt))
    val a = l.clone
    val b = a.clone
    bubbleSort(a)
    selectionSort(b)

    println(a.map((x)=>x._1.toString+x._2).mkString(" "))
    printStable(l,a)
    println(b.map((x)=>x._1.toString+x._2).mkString(" "))
    printStable(l,b)
  }
}

Measured memory_bytes: 43936
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 標準入力からデータを読み込む準備
Scanner sc = new Scanner(System.in);
// 要素数nを読み込み、配列にn個の整数を読み込む 
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt(); }
// 以下で配列aの中身を逆順に表示しよう
// 改行なしで表示する時は System.out.print(表示する値) を使おう 
// 改行だけを表示する時は System.out.println() を使おう
for(int j=n-1;j>=0;j--){
	if(j!=0){
	System.out.print(a[j]+" ");
} else{
	System.out.print(a[j]);
}}System.out.println();
} }


Measured memory_bytes: 26324
#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i = (a);i <= (b);++i)
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res = 1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
struct graph
{
    int head[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],sz;
    void init(){memset(head,-1,sizeof(head));}
    graph(){init();}
    void push(int a,int b,int c=0){nxt[sz]=head[a],to[sz]=b,w[sz]=c,head[a]=sz++;}
    int& operator[](const int a){return to[a];}
}g;
char s[maxn];
int vis[maxn][2];
void dfs(int now,bool flag)
{
    vis[now][flag]=1;
    for(int i = g.head[now];~i;i = g.nxt[i]){
        if(flag==1){
            if(s[g[i]]!=s[now]){
                if(!vis[g[i]][!flag]){
                    dfs(g[i],!flag);
                }
                if(vis[g[i]][!flag]==1){
                    printf("Yes\n");
                    exit(0);
                }
            }
        }
        else{
            if(s[g[i]]==s[now]){
                if(!vis[g[i]][!flag]){
                    dfs(g[i],!flag);
                }
                if(vis[g[i]][!flag]==1){
                    printf("Yes\n");
                    exit(0);
                }
            }
        }
    }
    vis[now][flag]=2;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i = 1,a,b;i <= m;++i){
        scanf("%d%d",&a,&b);
        g.push(a,b),g.push(b,a);
    }
    for(int i = 1;i <= n;++i){
        if(!vis[i][0])dfs(i,0);
        if(!vis[i][1])dfs(i,1);
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 20448
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#define ll long long
#define ld long double

int main() {

  cout << fixed << setprecision(16);

  ll N, M;
  cin >> N >> M;

  vector<pair<ll, ll>> a(N);

  for (ll i = 0; i < N; i++) {
    cin >> a[i].first >> a[i].second;
  }

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

  ll i = 0;
  ll ans = 0;
  while(i < M) {
    for (ll j = 0; j < N; j++) {
      if (i + a[j].second > M) {
        ans += a[j].first * (M - i);
        i = M;
      } else {
        ans += a[j].first * a[j].second;
        i += a[j].second;
      }
    }
  }

  cout << ans << endl;

  return 0;

}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int N,M,A[100001];
    priority_queue<long long int,vector<long long int> > que;
    cin >> N >> M;
    for(int i=0;i<N;i++){
        cin >> A[i];
        que.push(A[i]);
    }
    for(int i=0;i<M;i++){
        long long int d = que.top();
        que.pop();
        d = d / 2;
        que.push(d);
    }
    long long int sum = 0;
    while(!que.empty()){
        sum += que.top();
        que.pop();
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1912
import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    // this should be DP Frog.
    // we aslo can use queue
    // Lunlun Number abcde
    // we can build from abcd

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
 
        //useQueue();
        useDP();
    }
    public static void useDP() throws IOException {
        int K = nextInt();
        
        long dp[] = new long[100000+1]; //max
   
        for (int x=1; x<10; x++) {
            dp[x] = x;
        }

        int index = 10;
        for (int x=1; x<=K; x++) {
            long cur = dp[x];
            long mod = cur % 10;
            if(mod != 0){
                dp[index] = 10*cur+mod-1;
                index++;
                if(index>K){break;}
            }
            dp[index] = 10*cur+mod;
            index++;
            if(index>K){break;}
            if(mod != 9){
                dp[index] = 10*cur+mod+1;
                index++;
                if(index>K){break;}
            }
        }

        System.out.println(dp[K]); 
    }

    public static void useQueue() throws IOException {
        int K = nextInt();
        
        LinkedList<Long> queue = new LinkedList<Long>();

        for (int x=1; x<10; x++) {
            queue.add((long)x);
        }

        for (int x=1; x<K; x++) {
            long cur = queue.poll();
            long mod = cur % 10;
            if(mod != 0){
                queue.add(10*cur+mod-1);
            }
            queue.add(10*cur+mod);
            if(mod != 9){
                queue.add(10*cur+mod+1);
            }
        }

        System.out.println(queue.poll()); 
    }
 

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}

Measured memory_bytes: 33552
#include<iostream>
#include<math.h>
#include<complex>
#include<cstdlib>
#include<algorithm>
#include<functional>

typedef long long ll;

using namespace std;





int main(void) {
	int n;
	int ans = 1;

	cin >> n;
	int d[n] = {};


	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		d[b]++;
	
	}

	int hantei = 1;


	if (n % 2 == 0) {
		if (d[0] != 0) hantei = 0;
		for (int i = 1; i <= n / 2; i++) {
			if (d[2 * i - 1] != 2) hantei = 0;
		}
	}
	else {
		if (d[0] != 1) hantei = 0;
		for (int i = 1; i < n / 2; i++) {
			if (d[2 * i] != 2) hantei = 0;
		}
	}



	if (hantei == 1) {
		for (int i = 0;i < n / 2; i++) {
			ans = ans * 2 % 1000000007;
		}
	}
	else {
		ans = 0;
	}

	cout << ans << endl;

	return 0;
}


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

const double PI = acos(-1);
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second

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

  int a,b,c;
  cin >>a>>b>>c;
  cout << (a+b+c - max({a,b,c})) << endl;
  return 0;
}


Measured memory_bytes: 384