akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define se second
#define pb push_back
#define ft fflush(stdout)
 
 
using namespace std;
 
 
const int N = 2e5 + 123;
const int PLS = 3e5 + 123;
const int mod = 1e9 + 7;
const ll inf = 1e16;


ll n, a[N], k;
bool dp[N];


int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dp[0] = 0;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++)
            if (i >= a[j])
                dp[i] |= 1 - dp[i - a[j]];
    if (dp[k])
        cout << "First";
    else
        cout << "Second";
}

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

// #define fi first
// #define se second
#define rep(i, n) for (ll i=0;i<(n); i++)
#define ALL(v) (v).begin(), (v).end()
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;

const ll M=1000000007ll;
const ll MOD=1000000007ll;
const ll MAX=100000001ll;
//const ll M = 1000000000+7;

ll cnt = 0; 

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint f(ll n){
  if(n==0) return 1;
  mint ans = f(n/2);
  ans *= ans;
  if(n%2==1) ans*= 2;
  return ans;
}

mint choose(ll n, ll k){
  mint x=1, y=1;
  rep(i,k){
    x *= (n-i);
    y *= (i+1);
  }
  return x / y;
}

struct BIT {
  private:
   vector<ll> bit;
   ll N;
 
  public:
   BIT(ll size) {
     N = size;
     bit.resize(N + 1);
   }
 
   // 一点更新です
   void add(ll a, ll w) {
     for (ll x = a; x <= N; x += x & -x) bit[x] += w;
   }
 
   // 1~Nまでの和を求める。
   int sum(ll a) {
     ll ret = 0;
     for (ll x = a; x > 0; x -= x & -x) ret += bit[x];
     return ret;
   }
 };
 

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

  ll n = s.length();
  vector<ll> v(n);
  rep(i, n){
    if(s[i]=='B') v[i]=2;
    else v[i]=1;
  }

  BIT b(2);
  ll ans = 0;
  rep(i, n){
    ans += i - b.sum(v[i]);
    b.add(v[i], 1);
  }
  cout<<ans<<endl;
}


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

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define inf 100000000000010
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pi;

bool isprime(ll n)
{
    if(n<=1)return false;
    if(n<=3)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
}

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}

struct CustomCompare
{
    bool operator()(const int& lhs, const int& rhs)
    {
        return lhs < rhs;
    }
};

bool comp(pair<pi, ll>a,pair<pi,ll>b)
{
    if(a.fi.fi==b.fi.fi)return a.fi.se<b.fi.se;
    return a.fi.fi<b.fi.fi;
}

ll builtin_popcount(ll x)
{
    ll cnt = 0;
    for(ll i=60;i>=0;i--)
    {
        if((1LL<<i)&x)cnt++;
    }
    return cnt;
}

ll addmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a+b)%mod;
}
ll mulmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a*b)%mod;
}
/*
const int mxn = 5*(1e6) +10;
vi spf(mxn);
void sieve()
{
    for(ll i =0;i<mxn;i++)spf[i]  = i;
    for(ll i=2;i<mxn;i+=2)spf[i] = 2;
    for(ll i = 3;i*i<mxn;i++)
    {
        if(spf[i]==i)
        {
            for(ll j = i*i;j<mxn;j+=i)
            {
                if(spf[j]==j)spf[j] = i;
            }
        }
    }
}
*/

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n; cin>>n;
vi temp(n);
rep(i,0,n)cin>>temp[i];
sort(all(temp));
vpi arr;
rep(i,0,n)
{
    if(arr.size()==0)arr.pb({temp[i],1});
    else if(arr.back().fi==temp[i])arr.back().se++;
    else arr.pb({temp[i],1});
}
ll ans = 0;
n = arr.size();
for(ll i=0;i<n;i++)
{
    for(ll j=i+1;j<n;j++)
    {
        for(ll k=j+1;k<n;k++)
        {
            if(arr[k].fi<arr[j].fi+arr[i].fi)ans+=(arr[i].se*arr[j].se*arr[k].se);
        }
    }
}
cout<<ans<<endl;
return 0;
}
/*
23 5
10 3 3
2 1 4 11 8 10 5 6 7 9 12 3 14 13 16 18 21 15 17 19 20 23 22
4 6 3 18 23
*/


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main() {
  string S; cin >> S;
  ll cnt = 0;
  ll sum = 0;
  for(int i = 0; i < S.length(); ++i) {
    if(S[i] == 'B') cnt++;
    if(S[i] == 'W') sum += cnt;
  }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	vector<ll> vec;
	for(int i=0;i<n;i++)
	{
		ll x; cin>>x; vec.pb(x);
	}
	sort(vec.begin(),vec.end());
	ld ans = vec[0];
	for(int i=1;i<n;i++)
	{
		ans=(ans+vec[i])*ld(0.5);
	}
	cout<<fixed<<setprecision(20)<<ans<<'\n';
}


Measured memory_bytes: 256
<?php
$n = intval(fgets(STDIN));
$a = array_map("intval", explode(" ", trim(fgets(STDIN))));
$nums = [0,0,0];
$p = 1;
for($i = 0; $i < $n; $i++){
  $count = 0;
  for($j = 0; $j < 3; $j++){
    if($nums[$j] == $a[$i]){
      $count++;
      $J = $j;
    }
  }
  $nums[$J]++;
  $p*=$count;
  $p%=10**9+7;
}
echo $p;



Measured memory_bytes: 16884
while True:
    a, op, b = input().split()
    if op == '+':
        print(int(a) + int(b))
    elif op == '-':
        print(int(a) - int(b))
    elif op == '*':
        print(int(a) * int(b))
    elif op == '/':
        print(int(a) // int(b))
    elif op == '?':
        exit()


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

#define r(c) ((c) * M_PI / 180)

int main() {
  double a, b, C, S, L, h;

  cin >> a >> b >> C;

  h = b * sin(r(C));
  L = a + b + sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(r(C)));
  S = a * h / 2;

  cout << fixed << S << endl << L << endl << h << endl;

  return 0;
}

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

int main()
{
    int n, k;
    double n2;

    cin >> n;
    cin >> k;

    n2 = n;
    int bit[n], b[k];
    int selection[n];

    for( int i = 0; i < k; i++ )
        cin >> b[i];

   
    for( int i = 0; i < n; i++ )
    {
        bit[i] = i;
        selection[i] = 0;
    }
    
    for( int i = 0; i < pow( 2, n2 ); i++ )
    {
        int x = i;
        int j = 0;
        while( x > 1 )
        {
            selection[j] = x % 2;
            j++;
            x = x / 2;
        }
        selection[j] = x;

        bool judge = true;
        for( int t = 0; t < k; t++ )
            if( selection[b[t]] == 0 )
                judge = false;     

        if( judge == true )
        {
            cout << i << ":";
            for( int t = 0; t < n; t++ )
                if( selection[t] == 1 )
                    cout << " " << bit[t];
            cout<< endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3280
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <string>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;

#define rep(i, n) for(int i = 0; i < n ; i++ )
#define For(i, a, b) for(int i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MAX_N = 20;

int main(void){
    int N;
    int H[MAX_N];
    int max_H[MAX_N];
    int answer = 0;

    cin >> N;
    
    rep(i, N){
        cin >> H[i];
        if (i == 0){
            max_H[i] = H[i];
        }else{
            max_H[i] = max(max_H[i - 1], H[i]);
        }
        
    }

    rep(i, N){
        if (max_H[i] == H[i]){
            answer ++;
        }
    }


    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())

using namespace std;
int main() {
  ll N;
  cin>>N; 
  vec A(N),B(N);
  rep(i,0,N) cin>>A[i];
  rep(i,0,N) B[i]=A[i];
  sort(A);
  rep(i,0,N) {
     if(B[i]-A[N/2-1]<=0) {
      cout<<A[N/2]<<endl;
    }
    if(B[i]-A[N/2-1]>0) {
      cout<<A[N/2-1]<<endl;
    }
  }
}
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  


Measured memory_bytes: 5376
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
#define ip(arr, n) for(int i=0; i<n; i++) cin>>arr[i];
#define op(arr, n) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 100005

int n;
ll arr[MAX], dp[MAX]={0};;

void bottomUp(){
    dp[1] = abs(arr[1]-arr[0]);
    
    for(int i=2; i<n; i++){
        dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]));
    }
    cout<<dp[n-1]<<endl;
}

// ll topDown(int pos){
//     if(pos >= n-1) return 0;

//     if(dp[pos] != -1) return dp[pos];

// }
int main(){
    cin>>n;
    ip(arr, n);
    bottomUp();
    return 0;
}

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

#define rep(i,n) for(int i = 0;i<n;i++)
#define cint(a) int a; cin >> a;
#define cstr(str) string str; cin >> str;
#define vv(Type, n,m,d)vector<vector<Type>> vv(n, vector<Type>(m, d));

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

bool is_prime(ll a) {
	if (a == 1) return false;

	for (ll i = 2; i * i <= a; i++) {
		if (a % i == 0) return false;

	}
	return true;
}


int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(0);

	vector<int> a;
	ll n; cin >> n;
	int cnt = 0;
	ll b = n;

	for (ll i = 2; i*i  <= n; i++) {
		int c = 0;
		while (true) {
			if (n % i) break;
			c++;
			n /= i;
		}
		a.emplace_back(c);
	}

	

	for (auto d : a) {
		int i = 1;
		while (true) {
			if (d - i < 0) break;
			d -= i++;
			cnt += 1;
		}
	}
	if (n != 1) cnt++;
	cout << cnt << endl;



	return 0;
}


Measured memory_bytes: 7428
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); int a = stdIn.nextInt(); int b = stdIn.nextInt(); int c = stdIn.nextInt(); int counter = 0; int[] divisors = new int[10000]; for(int i = a; i <= b && i <= c; i++ ) { if(c % i == 0) { divisors[counter] = i; counter++; } } System.out.println(counter); } } 


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

using namespace std;

typedef long long int ll;

const ll MAXN = 1e5 + 5;

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

  string s;
  cin >> s;
  bool rev = false;
  deque < char > q;
  for(int i = 0; i < s.length(); i++) q.push_back(s[i]);
  ll qq;
  cin >> qq;
  while(qq--){
    ll t;
    cin >> t;
    if(t == 1){
      rev = !rev;
    }else{
      ll f;
      cin >> f;
      char ch;
      cin >> ch;
      if(f == 1){
        if(!rev) q.push_front(ch);
        else q.push_back(ch);
      }else{
        if(!rev) q.push_back(ch);
        else q.push_front(ch);
      }
    }
  }

  if(rev){
    while(!q.empty()){
      cout << q.back();
      q.pop_back();
    }
  }else{
    while(!q.empty()){
      cout << q.front();
      q.pop_front();
    }
  }
  cout << endl;
}


Measured memory_bytes: 976
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <time.h>
using namespace std;

typedef long double LD;
typedef long long LL;
typedef pair<int, int> PII;
#define MP make_pair
#define PB push_back
//#define X first
#define Y second
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i, 0, t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))

const LD PI = acos(-1.0);
const LD EPS = 1e-6;
const LL INF = 1000000007;
const LL LINF = 1LL * INF * INF;
const LL mod = 1000000007;
const LL MAX = 13;

int h, w, od, B[MAX];
string S[MAX];
bool P[MAX][MAX];
vector <int> A;

int cnt(int mask)
{
	int res = 0;
	REP(i, MAX)
		if (mask & (1 << i))
			++res;
	return res;
}

void rec1(int unused, int r)
{
	if (r == (h >> 1))
	{
		od = -1;
		REP(i, h)
			if (unused & (1 << i))
				od = i;
		if (od > -1)
		{
			A.push_back(od);
			B[r++] = od;
		}
		REP(mask, 1 << w)
		{
			if (cnt(mask) != (w >> 1))
				continue;
			vector <int> C, D;
			REP(j, w)
				if (mask & (1 << j))
					C.push_back(j);
				else
					D.push_back(j);
			do
			{
				bool ok = true;
				if (w & 1)
				{
					REP(i, r)
						if (S[A[i]][D.back()] != S[B[i]][D.back()])
						{
							ok = false;
							break;
						}
				}
				if (!ok)
					continue;
				REP(i, w >> 1)
				{
					REP(j, r)
						if (S[A[j]][C[i]] != S[B[j]][D[i]] || S[A[j]][D[i]] != S[B[j]][C[i]])
						{
							ok = false;
							break;
						}
						if (!ok)
							break;
				}
				if (!ok)
					continue;
				cout << "YES";
				exit(0);
			} while(next_permutation(ALL(D)));
		}
		if (od > -1)
			A.pop_back();
		return;
	}
	REP(i, h)
		if ((unused & (1 << i)) && P[i][A[r]])
		{
			B[r] = i;
			rec1(unused ^ (1 << i), r + 1);
		}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	cin >> h >> w;
	REP(i, h)
		cin >> S[i];
	REP(i, h)
		REP(j, h)
	{
		string T1 = S[i], T2 = S[j];
		sort(ALL(T1));
		sort(ALL(T2));
		int C1[26][26], C2[26][26];
		REP(k, 26)
			REP(l, 26)
			C1[k][l] = C2[k][l] = 0;
		REP(k, w)
		{
			C1[S[i][k] - 'a'][S[j][k] - 'a']++;
			C2[S[j][k] - 'a'][S[i][k] - 'a']++;
		}
		P[i][j] = T1 == T2;
		REP(k, 26)
			REP(l, 26)
			if (C1[k][l] != C2[k][l])
				P[i][j] = false;
	}
	REP(mask, 1 << h)
	{
		if (cnt(mask) != (h >> 1))
			continue;
		A.clear();
		REP(i, h)
			if (mask & (1 << i))
				A.push_back(i);
		rec1(((1 << h) - 1) ^ mask, 0);
	}
	cout << "NO";
	return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;


void ABC096C()
{
	int H, W;
	cin >> H >> W;
	vector<vector<int> > grid(H+2, vector<int>(W+2));
	for (int i = 1; i <= H; ++i)
	{
		string str;
		cin >> str;
		for (int j = 1; j <= W; ++j)
		{
			if (str[j-1] == '.')
				grid[i][j] = 0;
			else
				grid[i][j] = 1;
		}
	}
	vector<pair<int, int> > dx = { {0,1},{0,-1}, {1,0}, {-1,0} };
	for (int i = 1; i <= H; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			if (grid[i][j] == 1 && grid[i][j - 1] == 0 && grid[i][j + 1] == 0 && grid[i - 1][j] == 0 && grid[i + 1][j] == 0)
			{
				cout << "No" << endl;
				return;
			}
			continue;

			if (grid[i][j] > 0)
			{
				bool found = false;
				for (int k = 0; k < 4; ++k)
				{
					int x = i + dx[k].first;
					int y = j + dx[k].second;
					if (grid[x][y] > 0)
					{
						found = true;
						break;
					}
				}
				if (!found)
				{
					cout << "No" << endl;
					return;
				}
			}
		}
	}
	cout << "Yes" << endl;
	return;

}

int main()
{
	ABC096C();
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

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

		String s = sc.next();

		System.out.println("" + s.charAt(0) + (s.length() - 2) + s.charAt(s.length() - 1));

		sc.close();
	}
}


Measured memory_bytes: 22740
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
  int a,b;
  cin >> a >> b;
  if(a==b)cout << a+b << endl;
  else if(a < b)cout << 2*b-1 << endl;
  else cout << 2*a-1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<iomanip>

using namespace std;

vector<int> bignum(1,1);
const int e9=1000000000;

void fact(int n);
void multi(int num);
void output();

int main()
{
	int n;
	cin>>n;
	fact(n);
	return 0;
}

void fact(int n)
{
	for(int i=1;i<=n;i++)
	{
		 multi(i);
	}
	output();
}

void multi(int num)
{
	long long temp;
	for(int i=bignum.size()-1;i>=0;i--)
	{
		temp=(long long)(bignum[i])*num;
		bignum[i]=temp%e9;
		if(i==bignum.size()-1&&temp/e9>0)
		{
			bignum.push_back(temp/e9);
			continue;
		}
		bignum[i+1]+=temp/e9;
	}
}

void output()
{
	for(int i=bignum.size()-1;i>=0;i--)
	if(i==bignum.size()-1)
	{
		cout<<bignum[i];
	}
	else//上位を0で詰める
	{
		cout<<setfill('0')<<setw(9)<<right<<bignum[i];
	}
	cout<<endl;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define t1 first
#define t2 second
#define ll long long
using namespace std;
int a[105];
int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	for(int i=0;i<m;i++)
	{
		int c;
		cin>>c;
		a[c-1]=1;
	}
	int l1=0,l2=0;
	for(int i=0;i<x;i++)
	if(a[i]==1)
	l1++;
	for(int i=x;i<=n;i++)
	if(a[i]==1)
	l2++;
	cout<<min(l1,l2);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ctime>
#include <unordered_map>
#include <stdlib.h>
using namespace std;
#define ll  long long int
#define mod 1000000007
#define modd 998244353
#define com(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define pri(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<endl;
#define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*__builtin_clz();
__builtin_ctz();
__builtin_popcount();*/
int main()
{

    speed;
    ll a,b;
    cin>>a>>b;
    ll lcm= (a*b)/(__gcd(a,b));
    cout<<lcm<<"\n";
    cerr << "\nTime elapsed: " << 1000 * clock()/CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n;
	cin >> n;
	VI h(n);
	REP(i, n) { cin >> h[i]; }

	VI dp(n, INF);
	dp[0] = 0;
	REP(i, n - 1) {
		chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
		if(i + 2 < n) {
			chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}


Measured memory_bytes: 3988
#include <iostream>
#include <fstream>
#define F freopen("in.txt","r",stdin);
#define rep(a) for(int i=1;i<=a;i++)
using namespace std;

int main()
{
	//F
	int n;
	cin>>n;
	long long arr[105];
	rep(n)
	 cin>>arr[i];

	 int ans=0;
	 for (int i = 1; i <=n-2; ++i)
	 {
	 	for (int j = i+1; j <= n-1; ++j)
	 	{
	 		for(int k=j+1;k<=n;k++)
	 		{
	 			if(arr[i]<arr[j]+arr[k] and arr[j]<arr[i]+arr[k] and arr[k]<arr[i]+arr[j])
	 				{
	 					if(arr[i]==arr[j] || arr[j]==arr[k] ||arr[i]==arr[k])
	 						continue;
	 					else
	 					{
	 						//cout<<i<<" "<<j<<" "<<k<<endl;
	 						ans++;
	 					}
	 				}

	 		}
	 	}
	 }


	  cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3616
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] nums=new int[n+1];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        Arrays.sort(nums);
        int count=1;
        int ans=0;
        for(int i=n;i>0;i--){
            if(nums[i]!=nums[i-1]){
                ans+=count>=nums[i]?count-nums[i]:count;
                count=1;
            }else{
                count++;
            }
        }
        System.out.println(ans);
    }

    
}

Measured memory_bytes: 52384
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    vector<tuple<string,int,int>> spi(100);
    cin >>N;
    for(int i=0;i<N;i++){
        cin >>get <0>(spi.at(i))>>get <1>(spi.at(i));
        get<1>(spi.at(i))=-get<1> (spi.at(i));
        get<2> (spi.at(i))=i+1;
    }
    sort(spi.begin(),spi.end()+N-100);
    for(int i=0;i<N;i++){
        cout << get<2> (spi.at(i))<<endl;
    }
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
if 1 in a:
    a.remove(1)
ans = 1

if 0 in a:
    print(0)
else:
    for i in range(len(a)):
        if ans <= 10 ** 18:
            ans *= a[i]
    if ans <= 10 ** 18:
        print(ans)
    else:
        print(-1)

Measured memory_bytes: 21644
from math import log2
N, K = map(int, input().split())
ans = 0
for i in range(N):
    if i+1 > K:
        ans += (1/N)
    else:
        num = log2(K/(i+1))
        if (i+1)*2**(int(num)) >= K:
            ans += ((1/N)*(1/2)**int(num))
        else:
            ans += ((1/N)*(1/2)**(int(num)+1))
print(ans)


Measured memory_bytes: 3060
N, M = map(int, input().split())
g = [[float('INF')] * (N + 1) for _ in range(N + 1)]
abc = []
for _ in range(M):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))
    g[a][b] = c
    g[b][a] = c
for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 0
for a, b, c in abc:
    if g[a][b] != c:
        ans += 1
print(ans)


Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

typedef long long ll;

/*
  let's try computer shogi!!!
 */



int main(){
  ll n;
  cin >> n;
  ll out = 0;
  for(ll i=1;i<sqrt(n);++i){
    if ((n-i) % i == 0){

      if((n-i)/i > i){
	out += (n-i)/i;
	cerr<<(n-i)/i<<" for "<<i<<endl;
      }
    }
  }
  cout<<out<<endl;
  return 0;
}

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

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

    int w;
    while(cin >> w && w != -1){

        const int lastmonth = 4280;
        int ans = 1150;
        if(w <= 10);
        else if(w <= 20){
            ans += (w - 10) * 125;
        }
        else if(w <= 30){
            ans += 10 * 125;
            ans += (w - 20) * 140;
        }
        else {
            ans += 10 * 125 + 10 * 140;
            ans += (w - 30) * 160;
        }

        cout << lastmonth - ans << endl;
    }

   return 0;
}

Measured memory_bytes: 1188
H,W,K = gets.chomp.split.map(&:to_i)
C = H.times.map{gets.chomp.split("").map(&:to_s)}

gyo = [0, 1].repeated_permutation(H).to_a
retsu = [0, 1].repeated_permutation(W).to_a
ans = 0

gyo.each do |i|
  sample = Marshal.load(Marshal.dump(C)) 
  (0...H).each do |j|
    if i[j] == 1
      (0...W).each do |k|
        if sample[j][k] == "#"
          sample[j][k] = "."
        end
      end
    end
  end
  retsu.each do |l|
    sample2 = Marshal.load(Marshal.dump(sample)) 
    (0...W).each do |m|
      if l[m] == 1
        (0...H).each do |n|
          if sample2[n][m] == "#"
            sample2[n][m] = "."
          end
        end
      end
    end
    sum = 0
    (0...H).each do |o|
      (0...W).each do |p|
        if sample2[o][p] == "#"
          sum += 1
        end
      end
    end
    if sum == K
      ans += 1
    end
  end
end

puts ans

Measured memory_bytes: 14428
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=50000; ++i){
        if(i*108/100==n){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<":("<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

vector<ll> d(100001, 0);
struct edge{ll to, cost;};
vector<vector<edge>> G(100001, vector<edge>());
void dfs(ll now, ll from, ll D){
  d[now] = D;
  re(i, G[now].size()){
    if(G[now][i].to==from) continue;
    dfs(G[now][i].to, now, D+G[now][i].cost);
  }
}
int main(int argc, char const *argv[]) {
  ll a, b, c, n;std::cin >> n;
  re(i, n-1){
    std::cin >> a >> b >> c;
    G[a].push_back(edge{b, c});
    G[b].push_back(edge{a, c});
  }
  ll q, k;std::cin >> q >> k;
  dfs(k, -1, 0);
  re(i, q){
    std::cin >> a >> b;
    std::cout << d[a] + d[b] << '\n';
  }
  return 0;
}


Measured memory_bytes: 15872
#include <iostream>
using namespace std;
int main(){
  string s;cin>>s;
  int ret  = 1000;
  for(char i = 'a';'z' >= i; i++){
    int mx=0;
    int nw = 0;
    for(int j = 0; s.size() > j; j++){
      if(s[j]!=i){
        nw++;
      }else{
        mx = max(mx,nw);
        nw = 0;
      }
    }
    mx = max(mx,nw);
    ret = min(ret,mx);
  }
  cout << ret << endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B = 1e9+7;

ull StoH(string a){
  ull res=0;
  for(int i=0;i<a.size();i++)res=res*B+a[i];
  return res;
}

vector<bool> search(string &a,string &key){
  vector<bool> res(a.size(),0);
  ull klen=key.size(),h=StoH(a.substr(0,klen)),target=StoH(key),t=1;
  for(int i=0;i<klen;i++) t*=B;
  for(int i=klen;i<a.size();i++){
    if(h==target) res[i-klen]=1;
    h = h*B+a[i]-a[i-klen]*t;
  }
  if(h==target) res[a.size()-klen] = 1;
  return res;
}

int n,m,len;
string e[12];
vector<bool> es[12];
bool used[12],mem[1<<12];

bool check(int idx,int sta){
  if(sta==(1<<n)-1) return 1;
  if(mem[sta])return 0;
  mem[sta]=1;

  for(int i=0;i<n;i++){
    if(used[i]||!es[i][idx])continue;
    used[i]=1;
    if(check(idx+e[i].size(),sta+(1<<i))) return 1;
    used[i]=0;
  }
  return 0;
}

int main(){
  while(1){
    cin>>n>>m;
    if(!n&&!m)break;

    len=0;
    for(int i=0;i<n;i++)cin>>e[i],len+=e[i].size();
  
    string mp;
    for(int i=0;i<m;i++){
      string tmp;
      cin>>tmp;
      mp+=tmp;
    }

    for(int i=0;i<n;i++)es[i]=search(mp,e[i]);
    int ans=0;
    for(int i=0;i<mp.size()-len+1;i++){
      memset(used,0,sizeof(used));
      memset(mem,0,sizeof(mem));
      if(check(i,0)) ans++;
    }
    cout<<ans<<endl;
  }  
  return 0;
}

Measured memory_bytes: 3028
use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        _n: usize,
        m: usize,
        ab: [(usize, usize); m],
    }

    let mut map = HashMap::new();

    for (a, b) in ab {
        *map.entry(a).or_insert(0) += 1;
        *map.entry(b).or_insert(0) += 1;
    }

    for (_key, val) in map {
        if val % 2 != 0 {
            println!("NO");
            return;
        }
    }

    println!("YES");
}


Measured memory_bytes: 8144
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<cstring>

using namespace std;

#ifdef LDEBUG
#define debug(x) cout << #x << ":" << x << endl
#else
#define debug(...)
#endif

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

typedef unsigned long long u64;
typedef long long i64;

string s;

bool acgt(char c){
        return (c == 'A' || c == 'C' || c == 'G' || c == 'T');
}

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

        cin >> s;

        int m = 0;
        REP(i, s.size()) {
                if (!acgt(s[i]))
                        continue;

                int k = 0;
                while (i < s.size() && acgt(s[i])) {
                        k++;
                        i++;
                }
                m = max(m, k);
        }

        cout << m << endl;


        return 0;
}


Measured memory_bytes: 256
from sys import stdin, stderr, setrecursionlimit, exit
setrecursionlimit(2147483647)
def getint():
    return int(stdin.readline().rstrip('\r\n'))
def getints():
    return [int(i) for i in stdin.readline().rstrip('\r\n').split()]
def getintlines():
    return [int(i) for i in stdin.readlines()]
def getintslines():
    return [[int(i) for i in s.split()] for s in stdin.readlines()]
def debug(*args, **kwargs):
    print(*args, file=stderr, **kwargs)

n, m = getints()
shops = getintslines()

shops.sort(key=lambda x:x[0])
current_drink = 0
current_money = 0
for price, num in shops:
    current_money += price * num if current_drink + num <= m else price * (m - current_drink)
    current_drink += num
    if current_drink >= m:
        break
    
print(current_money)



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

int main(){
  int N;
  cin >> N;
  bool fourtype = false;  
  char color;
  for(int i = 0; i < N ;i++){
    cin >> color;
    if(color == 'Y'){
    fourtype = true;
    }
  }
  
  if(fourtype == true){
    cout << "Four" << endl;
  }
  else {
    cout << "Three" << endl;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int main() {
  int n,k;
  string s;
  cin >> n >> k >> s;
  s[k-1] += 0x20;
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	int n, a, b, c, d;
	char input[200001];
	string str;
	int i;
	int lmax;
	int lvac = 0, lrk = 0, cur;

	scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);

	a--;
	b--;
	c--;
	d--;

	scanf("%s", input);

	str = input;

	cur = 0;

	lmax = c > d ? c : d;

	for (i = a + 1; i <= c; i++)
	{
		if (str[i] == '#')
		{
			cur++;
		}

		else
		{
			cur = 0;
		}

		if (cur > lrk)
		{
			lrk = cur;
		}
	}

	if (lrk >= 2)
	{
		printf("No\n");

		return 0;
	}

	cur = 0;
	lrk = 0;

	lmax = c > d ? c : d;

	for (i = b + 1; i <= d; i++)
	{
		if (str[i] == '#')
		{
			cur++;
		}

		else
		{
			cur = 0;
		}

		if (cur > lrk)
		{
			lrk = cur;
		}
	}

	if (lrk >= 2)
	{
		printf("No\n");

		return 0;
	}

	if (c < d)
	{
		printf("Yes\n");

		return 0;
	}

	cur = 0;

	for (i = b - 1; i <= d + 1 && i < n; i++)
	{
		if (str[i] == '.')
		{
			cur++;
		}

		else
		{
			cur = 0;
		}

		if (cur > lvac)
		{
			lvac = cur;
		}
	}

	if (lvac >= 3)
	{
		printf("Yes\n");
	}

	else
	{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    long long n,a,b,c,d; cin>>n>>a>>b>>c>>d;
    string ans="NO";
    for(long long m=0;m<n;m++){
        if(c*(n-1-m)-d*m<= b-a && b-a <= -c*m+d*(n-1-m)){
            ans="YES";
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    if small == 0:
        return big
    
    r = small
    while r != 0:
        r = big % small
        big = small
        small = r
        
    return big
   
N, X, *x = map(int, open(0).read().split())

d = abs(x[0] - X)
for i in range(N):
    x[i] = abs(x[i] - X)
    d = gcd(d, x[i])
    
print(d)

Measured memory_bytes: 14052
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <cmath>
#include <stack>

using namespace std;
typedef long long ll;
using Pll = pair<ll,ll>;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    ll N,K,L;
    cin >> N >> K >> L;
    vector<Pll>p(K);
    vector<Pll>r(L);
    UnionFind ufk(N+1),ufl(N+1),uf(N);
    for(int i=0;i<K;i++){
        cin >> p[i].first >> p[i].second;
    }
    for(int i=0;i<L;i++){
        cin >> r[i].first >> r[i].second;
    }
    for(int i=0;i<K;i++){
        ufk.merge(p[i].first,p[i].second);
    }
    for(int i=0;i<L;i++){
        ufl.merge(r[i].first,r[i].second);
    }
    map<Pll,int>mp;
    for(int i=1;i<=N;i++){
        mp[Pll(ufk.root(i),ufl.root(i))]++;
    }
    for(int i=1;i<=N;i++){
        cout << mp[Pll(ufk.root(i),ufl.root(i))];
        if(i!=N)cout << " " ; 
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 17280
#include<bits/stdc++.h>
using namespace std;
int main()
{
   string s,s1,s3;
   cin>>s>>s1;
   int cnt=0;
   for(int i=0;i<s1.size()-1;i++)
   {
       if(s[i]!=s1[i])
       {
           cnt=1;
           break;
       }
   }

   if(cnt==0)
    cout<<"Yes\n";
   else
    cout<<"No\n";

}


Measured memory_bytes: 3596
#import numpy as np
#import math
#from decimal import *
#from numba import njit
from collections import Counter

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    r = []
    l = []
    for i in range(N):
        r += i - A[i],
        l += i + A[i],

    c = Counter(l)
    for i in r:
        count += c[i]

    print(count)
main()


Measured memory_bytes: 50580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int a[2][200010];
int fnd(int k, int x) {
  return a[k][x] = (a[k][x] == x ? x : fnd(k, a[k][x]));
}
void uni(int k, int x, int y) {
  a[k][fnd(k, x)] = fnd(k, y);
}
map<int,int> mp[200010];
int main(){
  int n, k, l;
  cin >> n >> k >> l;
  iota(a[0], a[0] + n + 1, 0);
  iota(a[1], a[1] + n + 1, 0);
  for (int i = 0, p, q; i < k; i++) {
    cin >> p >> q;
    uni(0, p, q);
  }
  for (int i = 0, r, s; i < l; i++) {
    cin >> r >> s;
    uni(1, r, s);
  }
  for (int i = 1; i <= n; i++) {
    mp[fnd(0, i)][fnd(1, i)]++;
  }
  for (int i = 1; i <= n; i++) {
    cout << mp[fnd(0, i)][fnd(1, i)];
    if (i != n) cout << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 20096
#include <stdio.h>

void insertionSort(int as[], int n)
{
  int i, j, k;
  int key;

  for (i = 0; i < n; i++) {
    key = as[i];
    j = i - 1;
    while (j >= 0 && as[j] > key) {
      as[j + 1] = as[j];
      j--;
    }
    as[j + 1] = key;
    for (k = 0; k < (n - 1); k++) {
      printf("%d ", as[k]);
    }
    printf("%d\n", as[n - 1]);
  }
}

int main(int argc, char *argv[])
{
  char row[4];
  int n = atoi(fgets(row, sizeof(row), stdin));
  int as[n];
  int i;

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

  insertionSort(as, n);

  return 0;
}

Measured memory_bytes: 608
import java.io.*;
import java.util.StringTokenizer;

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

		try {
			int c[] = {0,0};
			while ((buf = br.readLine())!=null) {
				StringTokenizer st = new StringTokenizer(buf,",");
				int l[] = new int[3];
				for (int i=0;i<3;i++) l[i] = Integer.parseInt(st.nextToken());
	
				if (Math.pow(l[0],2)+Math.pow(l[1],2)==Math.pow(l[2],2)) c[0]++;
				if (l[0]==l[1]) c[1]++;
			}
			System.out.println(c[0]);
			System.out.println(c[1]);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 16880
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>

using namespace std;

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

int main(){
    ll N,K,ans, tmp;
    vector<ll> H;
    cin >> N >> K;
    for (int i = 0; i< N; i++){
        cin >> tmp;
        H.push_back(tmp);
    }
    sort(H.begin(),H.end());

    for (int i= 0;i<K;i++){
        if(H.empty()){
            break;
        }
        H.pop_back();
    }

    for (size_t i = 0; i < H.size(); i++)
    {
        ans += H[i];
    }
    
    cout << ans ;
    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
int main() {
  string left = {"qwertasdfgzxcvb"};
  string right = {"yuiophjklnm"};
  while (1) {
    string s;
    cin >> s;
    if (s == "#") {
      break;
    }
    int ans = 0, last;
    string temp;
    temp.push_back(s[0]);
    if (left.find(temp) == string::npos) {
      last = 1;
    } else {
      last = 0;
    }
    temp.erase(0);
    for (int i = 1; s[i] != '\0'; i++) {
      temp.push_back(s[i]);
      if (left.find(temp) != string::npos && last == 1) {
        ans++;
        last = 0;
      } else if (right.find(temp) != string::npos && last == 0) {
        ans++;
        last = 1;
      }
      temp.erase(0);
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3192
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static String s;
	static int len;
	static int index;
	static long x;
	
	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		index = 0;
		s = br.readLine();
		
		len = s.length();
		int n = (int) Math.pow(2, len-1);
		x = 0;
		
		for(int i=0; i<= s.length(); i++){
			f(i, 0, s);
		}
		
		System.out.println(x);
	}
	
	static void f(int plus, long sum, String str){
		if(plus != 0){
			for(int i=1; i<str.length()-plus+1; i++){
				f(plus-1, Long.parseLong(str.substring(0, i))+sum, str.substring(i, str.length()));
			}
		}else{
			x += sum + Long.parseLong(str);
		}
	}
}


Measured memory_bytes: 8784
import sys
sys.setrecursionlimit(1000000)
def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)

N, M = map(int, input().split())
P = [-1 for i in range(N)]
A = [int(a)-1 for a in input().split()]
for _ in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)

X = [[] for _ in range(N)]
Y = [[] for _ in range(N)]
for i in range(N):
    X[par(i)].append(i)
    Y[par(i)].append(A[i])

ans = 0
for i in range(N):
    ans += len(set(X[i]) & set(Y[i]))

print(ans)



Measured memory_bytes: 129384
N = int(input())

result = 0
if N >= 10:
    result += 9
else:
    result += N

if N >= 1000:
    result += 900
elif N >= 100:
    result += N - 99


if N >= 100000:
    result += 90000
elif N >= 10000:
    result += N - 9999

print(result)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll h, w;
    cin >> h >> w;
    vector<string> image(h);
    REP(i, h) cin >> image.at(i);
    image.insert(image.begin(), string(w+2, '#'));
    image.push_back(string(w+2, '#'));
    FOR(i, 1, image.size() - 1) {
        image.at(i).insert(image.at(i).begin(), '#');
        image.at(i).push_back('#');
    }
    REP(i, image.size()) {
        cout << image.at(i) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d", $n);
for ($i = 0; $i < $n - 1; $i++) {
	fscanf(STDIN, "%d %d", $a, $b);
	$g[$a][$b] = $g[$b][$a] = 1;
}
$f[1] = 0;
$f[$n] = 1;
$x[0] = $x[1] = 1;
$q = new SplQueue();
$q->push([1, 0]);
$q->push([$n, 1]);
while (!$q->isEmpty()) {
	list($s, $c) = $q->shift();
	foreach ($g[$s] as $t => $r) {
		if (!isset($f[$t])) {
			$f[$t] = $c;
			$x[$c]++;
			$q->push([$t, $c]);
		}
	}
}
echo $x[0] > $x[1] ? 'Fennec' : 'Snuke';

Measured memory_bytes: 60152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
    ll n, x;
    cin >> n >> x;
    vector<ll> v(n + 1);
    v[0] = 0;
    for (ll i = 0; i < n; i++)
    {
        ll tmp;
        cin >> tmp;
        v[i + 1] = v[i] + tmp;
    }
    ll ans = 0;
    for (ll i = 0; i < n + 1; i++)
    {
        if (v[i] <= x)
            ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3600
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long k = Long.parseLong(sc.next());
        int[] a = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        if(k <= n) {
            int x = 1;
            for(int i=0; i<k; i++) {
                x = a[x];
            }
            System.out.println(x);
        }else {
            int x = 1;
            Map<Integer, Integer> map = new HashMap<>();
            int start = 0;
            int finish = 0;
            map.put(1, 0);
            int j = 1;
            while(true) {
                x = a[x];
                if(map.containsKey(x)) {
                    start = map.get(x);
                    finish = j-1;
                    break;
                }else {
                    map.put(x, j);
                }
                j++;
            }
            
            long amari = (k - start + 1) % (finish - start + 1);
            int ans = x;
            if(amari == 0) {
                amari = finish - start + 1;
            }
            for(int i=1; i<amari; i++) {
                ans = a[ans];
            }
        
            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 62780
#include <bits/stdc++.h>
         
typedef long long ll;
using namespace std;
        
#define F first
#define S second
#define sqr(x) x*x
#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define repit(i, n) for(auto it = n.begin(); it != n.end(); ++it)
       
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b){if(b==0)return a;else return gcd(b,a%b);}
int lcm(int a,int b){return abs(a*b)/gcd(a,b);}
     
int main(){ios_base::sync_with_stdio(0);cin.tie(0);
    unordered_map <string,int> um, um2;
    int n,m;
    cin >> n;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        um[s]++;
    }
    cin >> m;
    for(int i = 0; i < m; ++i){
        string s;
        cin >> s;
        um2[s]++;
    }
    bool flag = false;
    vector<int> v;
    for(auto x : um){
        for(auto y : um2){
            if(x.F == y.F ){
                flag = true;
                v.pb(x.S - y.S);
            }
        }
        if(flag == false){
            v.pb(x.S);
        }
        flag = false;
    }
    sort(all(v));
    reverse(all(v));
    if(v[0] < 0){
        cout << 0;
        exit(0);
    }
    cout << v[0];
    }

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int W,H,x,y,r;
	
	cin>>W>>H>>x>>y>>r;
	
	if(x+r<=W && y+r<=H && x-r>=0 && y-r>=0)
		cout<<"Yes\n";
	else if(x+r>W || y+r>H || x-r<0 || y-r<0)
		cout<<"No\n";
}

Measured memory_bytes: 1128