akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
using ll = long long;
using p = pair <int, int>;

p		pi[10];
int		d, g;

int		count(int *arr){
	int		score = 0;
	int		i = 0;
	int		rt = 0;
	int		nfull = -1;

	while (i < d){
		score += arr[i] * (pi[i].first * (i + 1) * 100 + pi[i].second);
		rt += arr[i] * pi[i].first;
		if (arr[i] == 0)
			nfull = i;
		i++;
	}
	if (nfull < 0)
		return (rt);
	i = 0;
	while (score < g){
		score += (nfull + 1) * 100;
		rt++;
		i++;
		if (i == pi[nfull].first)
			return (INF);
	}
	return (rt);
}

int		rec(int dep, int *arr){
	int		rt0, rt1;

	if (dep == d){
		arr[dep - 1] = 0;
		rt0 = count(arr);
		arr[dep - 1] = 1;
		rt1 = count(arr);
		if (rt0 < rt1)
			return (rt0);
		else
			return (rt1);
	}
	arr[dep - 1] = 0;
	rt0 = rec(dep + 1, arr);
	arr[dep - 1] = 1;
	rt1 = rec(dep + 1, arr);
	if (rt0 < rt1)
		return (rt0);
	else
		return (rt1);
}

int		main(void)
{
	cin >> d >> g;
	int		i = 0;
	while (i < d){
		cin >> pi[i].first >> pi[i].second;
		i++;
	}
	int		arr[d];
	i = 0;
	while (i < d)
		arr[i++] = 0;
	cout << rec(1, arr);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define ms(s,x) memset(s,x,sizeof(s))
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;

const double PI = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 2e5+5;
const ll MOD = 1e9+7;

int a[MAXN];
ll sum;
map <int, int> mp;
map <int, int>::iterator it;

int main()
{
    int n;
    scanf("%d", &n);
    rep(i, 1, n){
        scanf("%d", &a[i]);
        mp[a[i]]++;
    }
    for (it = mp.begin(); it != mp.end(); it++){
        if (it->second > 1) sum += 1ll * (it->second) * (it->second-1) / 2;
    }
    rep(i, 1, n){
        ll ans = sum;
        if (mp[a[i]] > 1){
            ans -= 1ll * mp[a[i]] * (mp[a[i]]-1) / 2;
            if (mp[a[i]]-1 > 1) ans += 1ll * (mp[a[i]]-1) * (mp[a[i]]-2) / 2;
        }
        printf("%lld\n", ans);
    }

    return 0;
}


Measured memory_bytes: 9344
#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,k;
  int counts = 0;
  cin >> n >> k;
  while(n >= k){
   counts++;
    n /= k;
  }
  cout << counts + 1 << endl;
}


Measured memory_bytes: 3540
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<math.h>

using namespace std;
int main(){
    
    long long a,b;
    char s,t,x;
    cin >> a ;
    vector<char> v1(a);
    vector<char> v2(a);
    vector<char> v3(2*a);

    for(int i=0;i<a;i++){
        cin >> v1[i];
    }
    for(int i=0;i<a;i++){
        cin >> v2[i];
    }
    for(int i=0;i<a;i++){
        cout << v1[i];
        cout <<v2[i];
    }
   
}

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

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>

using namespace std;
typedef long long ll;
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;}
const ll INF = 1e18+1;

int A[1000][1000];
int c[10][10];

int main() {
    int H, W; 
    cin >> H >> W;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) cin >> c[i][j];
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) cin >> A[i][j];
    }
    
    for (int k = 0; k < 10; k++) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                chmin(c[i][j], c[i][k]+c[k][j]);
            }
        }
    }
    int res = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (A[i][j] != -1) res += c[A[i][j]][1];
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<ctime>
using namespace std;
string s;
string t;
int main() {
    int n;
    cin >> n;
    cin >> s >> t;
    for (int i= 0; i <n; i++) {
        cout << s[i] << t[i];
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef double ld;
typedef vector<ld> vec;
typedef vector<vec> mat;
const double EPS=1E-6;

/*
  N???????????°??§N??????????¨???????????????´??????init?????????
  mat A(N,vec(N,0));
  vec B(N,0);
*/

vec gauss_jordan(const mat& A,const vec& b){
  int n=A.size();
  mat B(n,vec(n+1));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)B[i][j]=A[i][j];
  for(int i=0;i<n;i++)B[i][n]=b[i];
  for(int i=0;i<n;i++){
    int pivot=i;
    for(int j=i;j<n;j++)
      if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;
    swap(B[i],B[pivot]);

    if(abs(B[i][i])<EPS)return vec();

    for(int j=i+1;j<=n;j++)B[i][j]/=B[i][i];
    for(int j=0;j<n;j++){
      if(i!=j)
	for(int k=i+1;k<=n;k++)B[j][k]-=B[j][i]*B[i][k];
    }
  }
  vec x(n);
  for(int i=0;i<n;i++)x[i]=B[i][n];
  return x;
}

int d,c[6],used[8];
ld Ans[8];
int cnt[8];

ld power(ld x,ld y){
  ld res=1;
  for(int i=0;i<y;i++)res*=x;
  return res;
}

void check(){
  mat A(d+1,vec(d+1,0));
  vec B(d+1,0);
  
  for(int i=0;i<d+1;i++)
    for(int j=0;j<d+1;j++)
      A[i][j]=power(c[i],d-j);
  
  for(int i=0;i<d+1;i++)B[i]=Ans[c[i]];
  
  vec r=gauss_jordan(A,B);
  
  if(!r.size())return;

  int Z=0,C=0;
  for(int i=0;i<d+3;i++){
    ld sum=0;
    
    for(int j=0;j<r.size();j++)
      sum+=power(i,d-j)*r[j];
    
    if(abs(sum-Ans[i])>1e-5)Z=i,C++;
    
  }
  if(C==1)cnt[Z]++;
  
}

void dfs(int x,int idx){
  if(x==d+1){
    check();
    return;
  }
  for(int i=idx;i<d+3;i++){
    if(used[i])continue;
    used[i]=1;
    c[x]=i;
    dfs(x+1,i+1);
    used[i]=0;
  }
}

int main(){

  while(1){
    cin>>d;
    if(!d)break;
    
    for(int i=0;i<d+3;i++)cin>>Ans[i];
    
    memset(cnt,0,sizeof(cnt));
    
    dfs(0,0);

    int maxcnt=0,ans;
    
    for(int i=0;i<d+3;i++)
      if(maxcnt<cnt[i])ans=i,maxcnt=cnt[i];
    cout<<ans<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 3156
package main

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

var writer = bufio.NewWriter(os.Stdout)

func main() {
	c := make([]int, 5)
	for i := 0; i < 3; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		c[a]++
		c[b]++
	}

	for i := 1; i < 5; i++ {
		if c[i] == 3 {
			fmt.Fprintf(writer, "NO\n")
			writer.Flush()
			return
		}
	}

	fmt.Fprintf(writer, "YES\n")
	writer.Flush()
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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; }

int main(){
  ll k, s;
  cin >> k >> s;
  ll count = 0;
  rep(x,k+1){
    rep(y,k+1){
      if(s-x-y<=k&&s-x-y>=0){
          count++;
        }
    }
  }
  print(count);
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int N,T;
  int c[101];
  int t[101];

  scanf("%d%d",&N,&T);
  for(int i=1;i<=N;i++) scanf("%d%d",&c[i],&t[i]);

  int c_min=10000;
  for(int i=1;i<=N;i++){
    if(t[i]<=T && c_min>c[i]) c_min=c[i];
  }

  if(c_min==10000) printf("TLE\n");
  else printf("%d\n",c_min);
  return 0;
}


Measured memory_bytes: 128
#pragma warning(disable:4996)

#include<iostream>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include <assert.h>
#define pb push_back
#define INF 0x3F3F3F3F //int 下较大值
#define inf 0x3F3F3F3F3F3F3F3F  // ll 下较大值 
#define moD 1000000003
#define pii pair<ll,ll>
#define eps 1e-10
#define equals(a,b) (fabs(a-b)<eps)
#define bug puts("bug")
#define re  register
#define fi first
#define se second
typedef  long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll Mod = 998244352;
const int maxn = 2e6 + 10;
const double Inf = 10000.0;
const double PI = acos(-1.0);
using namespace std;


int bitcount(int x) {
    return x == 0 ? 0 : bitcount(x / 2) + (x & 1);
}


ll mul(ll a, ll b, ll m) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res % m;
}

ll quickPower(ll a, ll b, ll m) {
    ll base = a;
    ll ans = 1ll;
    while (b) {
        if (b & 1) ans = mul(ans, base, m);
        base = mul(base, base, m);
        b >>= 1;
    }
    return ans;
}

ll ksm(ll a, ll b, ll m) {
    ll base = a % m;
    ll ans = 1ll;
    while (b) {
        if (b & 1) ans *= base, ans %= m;
        base *= base, base %= m;
        b >>= 1;
    }
    return ans;
}



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

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

int readint() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

ll readll() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

ull readull() {
    ull x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void Put(ll x) {
    if (x < 0) putchar('-'), x *= -1;
    if (x > 9) Put(x / 10);
    putchar(x % 10 + '0');
}

ll a[2005];

int main() {
    int s = readint();
    a[0] = 1ll;
    for (int i = 0; i <= s; i++)
        for (int j = 3; j + i <= s; j++)
            a[i + j] = (a[i + j] + a[i]) % MOD;
    Put(a[s]);
}

Measured memory_bytes: 3612
#include<stdio.h>

int main(void)
{
  int A,B;
  scanf("%d %d",&A,&B);
  
  if(A+B==3){
    printf("%d",3);
  }
  else if(A+B==4){
    printf("%d",2);
  }else{
    printf("%d",1);
  }
  
  return 0;
}
 

Measured memory_bytes: 128
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
//#include <cstdio>
//#include <iomanip>//"cout<<fixed<<setprecision(n)<<sth<<endl;"
//#include <string>//"reverse(s's it,s's it)"
//#include <functional>//"greater<T>" "sort(a,a+n,greater<int>());""
//#include <cmath>//"abs" "sqrt"
//#include <numeric>//"accumulate(inputit,inputit,init,(optional) object)"
//#include <algorithm>//"lower_bound(it,it,v)" "next_permutation(a,a+n)"
//"reverse(v's it,v's it)"(v: vector)
using namespace std;
#define is insert

void solve(string s){
	set<string> st;
	for(int i=1;i<s.size();++i){
		string t[2][2];
		t[0][0]=s.substr(0,i);
		t[1][0]=s.substr(i,s.size()-i);
		for(int j=0;j<2;++j){
			t[j][1]=t[j][0];
			reverse(t[j][1].begin(),t[j][1].end());
		}
		for(int j=0;j<2;++j) for(int k=0;k<2;++k) for(int l=0;l<2;++l){
			string u=t[j][k];
			u+=t[1-j][l];
			st.is(u);
		}
	}
	cout<<st.size()<<endl;
}

int main(){
	int m;
	cin>>m;
	while((m--)>0){
		string s;
		cin>>s;
		solve(s);
	}
}

Measured memory_bytes: 3188
//============================================================================
// Name        : HelloCPP.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {

	int a,b;

	cin >> a >> b;

	printf("%d %d %lf\n",a/b,a%b,(double)a / b );

	return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cctype>

using namespace std;
// for loop
#define F(i, L, R) for(int i = L; i < R; i++)
#define FE(i, L, R) for(int i = L; i <= R; i++)
// for (reversed)
#define FR(i, L, R) for(int i = L; i > R; i--)
#define FRE(i, L, R) for(int i = L; i >= R; i--)

// data types
#define ul unsigned long
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned shoft

// vectors
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define ALL(c) (c).begin(),(c).end()
#define last(vec) vec.size()-1
#define lastEle(vec) vec[last(vec)]
#define pb push_back

// debug
#define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl;
#define printA(a, L, R) FE(i, L, R) cout << a[i] << (i==R?'\n':' ')
#define printAF(a, L) printA(a, 0, L-1)
#define printV(a) printA(a, 0, a.size()-1)

// utils
#define char2int(c) (c-'0')
#define bit(x, i) (x&(1<<i))
#define space ' '
#define PI 3.14159265358979323

int main() {
    char input[1001];
    vi ans;
    while(1){
        cin.getline(input, sizeof(input));
        if(input[0] == '0' && input[1] == '\0')break;
        int sum = 0;
        F(j, 0, sizeof(input)){
            if(input[j] == '\0')break;
                sum += char2int(input[j]);
        }
        ans.pb(sum);
    }
    F(j, 0, ans.size()){
        cout << ans[j] << endl;
    }
}



Measured memory_bytes: 3164
N,M,C=map(int, input().split())
B=list(map(int, input().split()))
count = 0
for i in range(N):
  A=list(map(int, input().split()))
  hyoka = 0
  for k in range(M):
    hyoka = hyoka + A[k]*B[k]
  if hyoka+C > 0:
    count = count + 1
print(count)

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

inline void Disp(int a, int b)
{
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			if (i == 0 || i == a - 1) cout << "#";
			else if (j == 0 || j == b - 1) cout << "#";
			else cout << ".";
		}
		cout << endl;
	}
	cout << endl;
}

int main(void)
{
	int a, b;

	while (true)
	{
		cin >> a >> b;
		if (a == 0 && b == 0) break;
		Disp(a, b);
	}
	return 0;
}


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

int main(){
    int n, k;
    cin >> n >> k;
    ll h[n];
    for(int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);
    ll ans = 1e9 + 1;
    for(int i = 0; i < n; i++){
        if(i + k - 1 > n - 1) continue;
        ll tmp = h[i + k - 1] - h[i];
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
def input(): return sys.stdin.readline().strip()

def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    ans = 10**18
    for i in range(ls - lt + 1):
        cnt = 0
        for j in range(lt):
            if t[j] != s[i + j]:
                cnt += 1
        ans = min(ans, cnt)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 67788
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define MP make_pair
#define pb push_back

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

static const int INF = INT_MAX;
static const LL L_INF = LLONG_MAX;
static const int MOD = (1000000000 + 7);

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

    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort( a, a + n );
    int s = 0;
    for(int i = 0; i < n - 1; ++i) s += a[i];
    if( a[n - 1] < s ) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

typedef long long ll;
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 200005

ll n;
ll a[MAXX];
ll b[MAXX];

int main()
{
    _FastIO;
    cin >> n;
    bool flag = true;
    multiset<pair<ll , ll> > ms;
    multiset<pair<ll , ll> >::iterator it;
    for(ll i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) flag = false;
        ms.insert({b[i] , i});
    }
    if(!flag){
        cout << "No" << endl;
        return 0;
    }
    ll t = 0;
    string ans = "Yes";
    for(it = ms.begin(); it != ms.end(); it++){
        ll x = (it)->second;
        t += a[x];
        if(t > b[x]){
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int h,w;
	char s[51][51];
	int dx[8]={-1, 0, 1,-1, 1,-1, 0, 1};
	int dy[8]={-1,-1,-1, 0, 0, 1, 1, 1};
	int box[51][51];
	int x,y;
	int i,j,k;
	cin>>h>>w;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>s[i][j];
			box[i][j]=0;
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(s[i][j]=='#'){
				for(k=0;k<8;k++){
					y=i+dy[k];
					x=j+dx[k];
					// cout<<x<<" "<<y<<endl;
					if(0<=x&&x<w&&0<=y&&y<h)	box[y][x]++;
				}
			}
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(s[i][j]=='#')	cout<<s[i][j];
			else				cout<<box[i][j];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N;
ll a[100000 + 100];
int main () {
  ios::sync_with_stdio(false);
  cin >> N;
  int ct1 = 0;
  int ct2 = 0;
  int ct4 = 0;
  for(int i = 0; i < N; ++i) {
    ll c;
    cin >> c;
    if ((c % 4) == 0) ct4++;
    else if ((c % 2) == 0) ct2++;
    else ct1++;
  }
  if ((ct2 == 0 && ct4 >= ct1 - 1 && ct4 > 0) ||
  ct4 >= ct1) cout << "Yes";
  else cout << "No";
  cout << endl;
}

Measured memory_bytes: 256
x = int(input())
A = 0
B = 0
for i in range(-1000,1000):
  if i**5 + x >= 0 and float.is_integer(round((i**5 + x)**0.2,5)) == True:
    A = (i**5 + x)**0.2
    B = i
    break

print(int(A),B)

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

int gcd(int x,int y){
  int a=max(x,y);
  int b=min(x,y);
  if(a%b == 0){
    return b;
  }else{
    return gcd(a%b,b);
  }
}

int main(){
  int N;
  cin >> N;
  vector<int> X(N+1);
  cin >> X.at(0);
  for(int i=1;i<=N;i++){
    cin >> X.at(i);
  }
  sort(X.begin(),X.end());
  //for(int i=0;i<=N;i++){
  //  cout << X.at(i) << endl;
  //}
  int ans = X.at(1) - X.at(0);
  for(int i=2;i<=N;i++){
    //cout << ans << endl;
    ans = gcd(ans,X.at(i) - X.at(i-1));
  }
  cout << ans << endl;
}

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

using namespace std;
#define ll long long
#define f first
#define s second
ll n,x,y,tmp,ans;

int par[100005] , sz[100005];

int findPar(int node)
{
    if (par[node]==node) return node;
    return par[node] = findPar(par[node]);
}

void mergeCom(int node , int node2)
{
    int led = findPar(node) , led2 = findPar(node2);

    if (sz[led] > sz[led2])
    {
        par[led2]=led , sz[led] += sz[led2];
    }
    else
    {
        par[led]=led2 , sz[led2] += sz[led];
    }
}

int main()
{
    cin >> n;
    pair < pair<ll,ll> , ll> arr[n+1] , arr2[n+1];
    vector <pair<ll , pair<ll,ll> > > vec;

    for (int i=1; i<=n; i++)
    {
        cin >> x >> y;
        arr[i].f.f=x , arr[i].f.s=y , arr[i].s=i;
        arr2[i].f.f=y , arr2[i].f.s=x , arr2[i].s=i;
        par[i]=i , sz[i]=1;
    }
    sort(arr+1,arr+n+1) , sort(arr2+1,arr2+n+1);
    for (int i=1; i<n; i++)
    {
        tmp = min(abs(arr[i+1].f.f-arr[i].f.f) , abs(arr[i+1].f.s-arr[i].f.s));
        vec.push_back({tmp , {arr[i+1].s , arr[i].s}});

        tmp = min(abs(arr2[i+1].f.f-arr2[i].f.f) , abs(arr2[i+1].f.s-arr2[i].f.s));
        vec.push_back({tmp , {arr2[i+1].s , arr2[i].s}});
    }

    sort(vec.begin() , vec.end());
    tmp = n-1;
    for (int i=0; i<vec.size(); i++)
    {
        if (!tmp) break;
        x = vec[i].s.f , y = vec[i].s.s;
        if (findPar(x)==findPar(y)) continue;
        ans += vec[i].f , tmp--;
        mergeCom(vec[i].s.f , vec[i].s.s);
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 13936
N, M = map(int, input().split())
lights = []
for i in range(1,M+1):
  light = list(map(int, input().split()))
  lights.append(light)

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

ans = 0
for i in range(2**N):
  all = True
  for j in range(M):
    ons = 0
    for s in lights[j][1:]:
      if (i>>(s-1) & 1):
        ons += 1
    if ons % 2 != ps[j]:
      all = False
      break            
  if all:
    ans += 1

print(ans)

Measured memory_bytes: 3064
x = [input() for i in range(2)]

n = x[0]
word = x[1]


letter_num = len(word)


word_num = list(word)

if letter_num <= int(n):
    print(word)

else:
    words = list(word)
    l = list()
    m = 0
    for i in range (int(n)):
        l.append(words[int(m)])
        m += 1
        
    l.append("...")
    
    answer = " "
    
    for j in l:
        answer += j
    print(answer)

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

#define rep(i,N); for (int i = 0; i<N; i++)

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> alist(N);
  rep(i, N) {
    cin >> alist.at(i);
  }
  int asum = 0;
  rep(i, N) {
    asum += alist.at(i);
  }
  sort(alist.begin(), alist.end());
  reverse(alist.begin(), alist.end());
  if (alist.at(M-1)*4*M>=asum) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	char a;
	int x=0;
	for(int i=1;i<=3;i++){cin>>a;if(a=='o')x++;}
	cout<<x*100+700;
}



Measured memory_bytes: 256
x = gets.chomp
s = []

x.split('').each do |c|
  if c == 'S' then
    s.push(c)
  else
    if ((s.size == 0) || (s[s.size - 1] == 'T')) then
      s.push(c)
    else
      s.pop
    end
  end
end
    
puts s.size.to_s

Measured memory_bytes: 18428
#include <bits/stdc++.h>
using namespace std;
int n, k, jump;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	cin >> n >> k;
	vector<int> dp(n, INT_MAX);
	vector<int> arr(n);
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(int i=2;i<n;i++){
		for(int j=i-1, jump=0;j>=0 && jump<k;j--, jump++){
			dp[i]=min(dp[i], dp[j]+abs(arr[i] - arr[j]));
		}
	}
	cout << dp[n-1] << endl;
}

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

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion


int main()
{
    int num_rect = 0;
    int num_lozen = 0;
    int side1, side2, diagonal;
    char c;
    while(cin>>side1>>c>>side2>>c>>diagonal) {
        if(side1*side1+side2*side2==diagonal*diagonal) {
            num_rect++;
        } else if (side1==side2) num_lozen++;
    }
    cout << num_rect << "\n" << num_lozen << endl;
    return 0;
}

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

#include <string>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define pb push_back



int main(){
	

	int n;
	cin>>n;

	int num[n+1]={0};
	int ans[n+1]={0};
	for(int i=0;i<n;i++){
		cin>>num[i];
	}

	if(n%2==0){
		for(int i=0;i<=n/2;i++){
			ans[i]=num[n-1-(2*i)];
		}
		for(int i=0;i<=n/2;i++){
			ans[i+n/2]=num[2*i];
		}

	}

	if(n%2==1){


		for(int i=0;i<=n/2;i++){
			ans[i]=num[n-1-(2*i)];
		}

		for(int i=0;i<n/2;i++){
			ans[i+n/2+1]=num[2*i+1];
		}







	}
	for(int i=0;i<n-1;i++){
			cout<<ans[i]<<" ";
		}
		cout<<ans[n-1]<<endl;



}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define endl ("\n")
using namespace std;

#define deb(x) cout << (#x) << " -> " << (x) << endl;
#define mod (1000000007)

bool dist(vector<int> a, vector<int> b)
{
    long long dist = 0ll;
    for(int i = 0;i < a.size();i++)
    {
        dist += (a[i] - b[i])*(a[i] - b[i]);
    }
    int s = sqrt(dist);
    return s * s == dist;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cout << fixed;
    cout.precision(10);
    // Those who cannot acknowledge themselves, will invariably fail

    int n;
    cin >> n;
    int d;
    cin >> d;
    vector<vector<int> > arr(n);
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < d;j++)
        {
            int a;
            cin >> a;
            arr[i].push_back(a);
        }
    }
    int count = 0;
    for(int i= 0;i < n;i++)
    {
        for(int j = i + 1;j < n;j++)
        {
            count += dist(arr[i], arr[j]);
        }
    }
    cout << count;
    return 0;
}

Measured memory_bytes: 256
s = input()
m = 10**9 + 7

a = [1,0,0,0]
for ch in s:
    if ch == 'A':
        a[1] = (a[0]+a[1]) % m
    elif ch == 'B':
        a[2] = (a[1]+a[2]) % m
    elif ch == 'C':
        a[3] = (a[2]+a[3]) % m
    else:
        a[3] = (a[2]+3*a[3]) % m
        a[2] = (a[1]+3*a[2]) % m
        a[1] = (a[0]+3*a[1]) % m
        a[0] = (3*a[0]) % m

print(a[3])


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod2 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 2e9

int main()
{
    int n;
    cin >> n;
    int q=n/1000;
    if(n%1000!=0)
        q+=1;
    cout << q*1000-n << endl;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<set>

using namespace std;

bool isLeap(int year)
{
    if (year % 400 == 0)
    {
        return true;
    }
    
    if (year % 100 == 0)
    {
        return false;
    }
    
    return (year % 4 == 0);
}

long long dateSerial(int year, int month, int day)
{
    static int days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    
    long long res = day;
    
    for (int i = 0; i < month - 1; i++)
    {
        res += days[i];
        
        if(isLeap(year) && i == 1)
        {
            res++;
        }
    }
    
    for (int i = 1; i < year; i++)
    {
        res += 365;
       
        if (isLeap(i))
        {
            res++;
        }
    }
    
    return res;
}

void Solution()
{
    int y1, m1, d1, y2, m2, d2;
    
    while (cin>>y1>>m1>>d1>>y2>>m2>>d2)
    {
        if (y1 < 0 || m1 < 0 || d1 < 0 || y2 < 0 || m2 < 0 || d2 < 0)
        {
            break;
        }
        
        long long date1 = dateSerial(y1, m1, d1);
        long long date2 = dateSerial(y2, m2, d2);
        
        cout<<date2 - date1<<endl;
    }
}

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

Measured memory_bytes: 1156
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>


#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;


int main()   {
    cout.precision(17);
    ll modd = 1000 * 1000 * 1000 + 7;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
    ll infinit = 10000000000000000;

//    readint(test_cases);
     int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(n);
        vector<ll> d;
        forr(i,0,n) {
            readll(kk); d.push_back(kk);
        }
        sort(d.begin(), d.end());
        if (d[0] == 0) {
            cout << 0 << endl;
        } else {
            ll ret = 1;
            bool print_ = true;
            for (auto x : d) {
                if (ret <= 1+2000000000000000000LL/x) {
                    ret *= x;                    
                    if (ret > 1000000000000000000LL) {
                        cout << -1 << endl;
                        print_ = false;
                        break;
                    }
                } else {
                    cout << -1 << endl;
                    print_ = false;
                    break;
                }
            }
            if (print_) {
                    if (ret <= 1000000000000000000LL) {
                     cout << ret << endl;
                    } else {
                        cout << -1 << endl;
                    }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 4288
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

  vector<string> v;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }

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

  for (auto s : v) {
    cout << s;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
int main(){
    int N , Y ;
    cin >> N >> Y ;
    for( int i = 0 ; i <= N ; i++ )
     for( int j = 0 ; j <= N - i ; j++ ){
         int k = N - i - j ;
         if ( i * 10000 + j * 5000 + k * 1000 == Y ){
             cout << i << " " << j << " " << k << endl ;
             return 0 ;
         }
     }
    cout << "-1 -1 -1" << endl ;
    return 0 ;
}

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

#define ll long long int
#define hell 1000000007
#define vi vector <ll>
#define pb push_back
#define pii pair<ll,ll>
#define vii vector <pii>
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define sep(i,a,b)  for(ll i=a-1;i>=b;i--)
#define inf (ll)(1e16)

using namespace std;

void solve()
{
    ll m,n;
    cin>>m>>n;
    vector < vi> dp(m+1,vi(n+1,0));
    rep(i,1,m+1)
    {
        rep(j,1,n+1)
        {
            char c;
            cin>>c;
            if(c=='.')
            {
                if(i==1&&j==1)
                    dp[i][j]=1;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
            else
                dp[i][j]=0;
            dp[i][j]%=hell;
        }
    }
    cout<<dp[m][n];
}

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


Measured memory_bytes: 8192
#include <iostream>
#include<algorithm>
#include <vector>
#include<string>
#include<queue>

using namespace std;

long long h[1005] = {0};

int main() {
	int n;
	cin >>n;
	long long ans = 0;
	long long a, b, c,d,e,f;
	for (int i = 1; i <=n; i++) {
		cin >> d >> e >> f;
		


		a = max(d, max(e, f)); c = min(d, min(e, f)); b = d + e + f - a - c;
		
		h[i] = a * 1002001 + b * 1001 + c;
		for (int j = 1; j <= i-1; j++) {
			if (h[j] == h[i]) { 
				ans++;
				//cout << " " << i<<" "<<j << endl;
				h[j] = 0;
			}
		}
	}

	cout << ans << endl;
}



Measured memory_bytes: 3140
# coding: utf-8
# Your code here!
M=[]

for i in range(3):
    row=list(map(int,input().split()))
    M.append(row)

flg=True

for i in range(3):
    if M[0][i]-M[0][i-1] == M[1][i]-M[1][i-1] == M[2][i]-M[2][i-1]:
        continue
    else:
        flg=False
    
    if M[i][0]-M[i-1][0] == M[i][1]-M[i-1][1] == M[i][2]-M[i-1][2]:
        continue
    else:
        flg=False

if flg:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
(|>) :: a -> (a -> b) -> b
infixl 1 |>
x |> f = f x

($>) :: (Functor m) => m a -> (a -> b) -> m b
infixl 1 $>
x $> f = fmap f x

getNums = getLine $> words $> map read

solve :: Int -> Int -> Int
solve a b
    | a > b = 0
    | otherwise = 1 + solve (a * 2) b

main = do
    x:y:_ <- getNums :: IO [Int]
    solve x y |> print

Measured memory_bytes: 508
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

class Main {
	//最大公約数を求める
	static int Gcd(int x, int y) {
		
		int n = Math.min(x, y);
		
		for (int i = n; i >= 1; i--) 
			if (x % i == 0 && y % i == 0) return i;
		
		return 1;
	}
		
	static class InputReader {
		BufferedReader br;
		StringTokenizer st;
		
		public String nextString() {
			
			 while (!st.hasMoreTokens()) {
	                try {
	                    st = new StringTokenizer(br.readLine(), " ");
	                } catch (IOException e) {
	                    throw new InputMismatchException();
	                }
	            }
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(nextString());
		}
					
		public InputReader (InputStream inputStream) {
			br = new BufferedReader (new InputStreamReader (inputStream));
			st = new StringTokenizer ("");
		}
		
	}
	
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		InputReader in = new InputReader (inputStream);
		
		//２つの自然数入力
		int x = in.nextInt();
		int y = in.nextInt();
		
		int gcd;
		
		if ( x == y) gcd = x;
		else if (x > y) {
			int n = x % y;
			gcd = Gcd(y,n);
		} else {
			int n = y % x;
			gcd = Gcd(x,n);
		}
		
		System.out.println(gcd);
	}
	
}



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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  int d = 100*a + 10*b + c;
  
  if(d%4 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
 
  return 0;
}

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

int main(){
    int N,K;
    cin >> N >> K;
    vector<ll> A(N),hi(N);
    rep(i,N){
        cin >> A[i];
        if(i!=0){
            hi[i]=max(hi[i-1],A[i]);
        }else{
            hi[0]=A[0];
        }
    }
    ll ans = INF;
    for(int bit=0;bit<(1<<N);bit++){
        vector<int> tmp(N);
        rep(i,N) tmp[i]=hi[i];
        vector<int> b;
        ll money=0;
        for(int d=0;d<N;d++){
            if(bit&(1<<d)){
                b.push_back(d);
            }
        }
        if(b.size()<K)continue;
        for(int i=0;i<b.size();i++){
            int maxhi = 0;
            rep(x,b[i]){
                maxhi = max(maxhi,tmp[x]);
            }
            if(A[b[i]]<=maxhi){
                money+=maxhi-A[b[i]]+1;
                tmp[b[i]]=maxhi+1;
            }
        }
        ans = min(ans,money);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(){
    int tmp;
    double rest;
    double out=0;
    int min_rest=10;
    bool flag=false;
    
    vector<int> min_index;
    vector<int> order_time;

    cin>>tmp;
    order_time.push_back(tmp);
    cin>>tmp;
    order_time.push_back(tmp);
    cin>>tmp;
    order_time.push_back(tmp);
    cin>>tmp;
    order_time.push_back(tmp);
    cin>>tmp;
    order_time.push_back(tmp);

    for(int i=0;i<order_time.size();i++){
        rest=order_time[i]%10;

        if(rest==0)
            rest = 9.9;

        if(min_rest==rest){
            min_index.push_back(i);
        } 
        if(min_rest>rest){
            min_rest=rest;
            min_index.clear();
            min_index.push_back(i);
        }
    }

    

    
    for(int i=0;i<order_time.size();i++){
        flag=false;
        for(int j=0;j<min_index.size();j++){
            if(i==min_index[j]){
                flag = true;
                break;
            }
        }
        if(flag)
            continue;
        else{
            if((order_time[i]%10))
                out +=order_time[i]+(10-(order_time[i]%10));
            else
                out+=order_time[i];
        }
        
        
    }



    if(min_index.size()==1){
        out +=order_time[min_index[0]];
    }else{
        for(int i=0;i<min_index.size()-1;i++){
            out += (order_time[min_index[i]]+(10-(order_time[min_index[i]]%10)));
        }
        
        out +=order_time[min_index[min_index.size()-1]];
    }

    cout<<out<<endl;
    return 0;

}

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


const int N = 1e5 + 10, M = 998244353;
int n, a[N];
int ans = 1e9;

int dp[N];

int main() {


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

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

	for (int i = n - 1; i >= 0; i--)
	{
		if (i == n - 1)
		{
			dp[i] = 0;
		}
		else if (i == n - 2)
		{
			dp[i] = abs(a[i] - a[i + 1]);
		}
		else
		{
			dp[i] = min(abs(a[i] - a[i + 1]) + dp[i + 1], abs(a[i] - a[i + 2]) + dp[i + 2]);
		}
	}

	cout << dp[0] << "\n";
	
	return 0;
}

/*
recursion :
int calcMin(int i)
{
	if (i == n - 1)
	{
		return 0;
	}
	if (i < n - 2)
	{
		return min(abs(a[i] - a[i + 1]) + calcMin(i + 1), abs(a[i] - a[i + 2]) + calcMin(i + 2));
	}
	return abs(a[i] - a[i + 1]) + calcMin(i + 1);
}
*/

/*
recursion + dp :
int dp[N];
bool solved[N];

int calcMin(int i)
{
	if (i == n - 1)
	{
		return 0;
	}

	if (solved[i])
	{
		return dp[i];
	}

	if (i < n - 2)
	{
		dp[i] = min(abs(a[i] - a[i + 1]) + calcMin(i + 1), abs(a[i] - a[i + 2]) + calcMin(i + 2));
	}
	else
	{
		dp[i] = abs(a[i] - a[i + 1]) + calcMin(i + 1);
	}

	solved[i] = 1;
	return dp[i];
}
*/

Measured memory_bytes: 1024
#include<bits/stdc++.h> 
using namespace std; 
typedef long long ll;
vector<int> g[200005];
int a[200005],b[200005],f[200005],root[200006],tot,n;
int ls[4000005],rs[4000005],mx[4000005],ans[200005];
int Query(int p,int l,int r,int x){
	if(!p||!x)return 0;
	if(r<=x)return mx[p];
	int mid=(l+r)/2,m=0;
	m=max(m,Query(ls[p],l,mid,x));
	if(x>mid)m=max(m,Query(rs[p],mid+1,r,x));
	return m;
}
void Update(int &p,int q,int l,int r,int x,int y){
	p=++tot;
	ls[p]=ls[q],rs[p]=rs[q],mx[p]=max(mx[q],y);
	if(l==r)return ;
	int mid=(l+r)/2;
	if(x<=mid)Update(ls[p],ls[q],l,mid,x,y);
	else Update(rs[p],rs[q],mid+1,r,x,y);
}
void dfs(int x,int fa){
	f[x]=Query(root[fa],1,n,a[x]-1)+1;
	ans[x]=max(f[x],ans[fa]);
	Update(root[x],root[fa],1,n,a[x],f[x]);
	for(int y:g[x]){
		if(y^fa)dfs(y,x);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y),g[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 70800
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

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

int main(){

	int p,n,x,y,u,v,common;
	int left,right,m,tmp_bunshi;
	double sqrt_p,near_small,near_big;
	double tmp,tmp_small,tmp_big;

	while(true){
		scanf("%d %d",&p,&n);
		if(p == 0 && n == 0)break;

		near_small = 0,near_big = DBL_MAX;

		sqrt_p = (double)sqrt(p);

		for(int bunbo = 1; bunbo <= n; bunbo++){

			left = 1,right = n, m = (left+right)/2;
			tmp_small = 0;

			while(left <= right){
				tmp = (double)m/(double)bunbo;

				if(tmp < sqrt_p){
					tmp_small = tmp;
					tmp_bunshi = m;
					left = m+1;
				}else{
					right = m-1;
				}
				m = (left+right)/2;
			}
			if(near_small < tmp_small){
				near_small = tmp_small;
				u = tmp_bunshi;
				v = bunbo;
			}

			left = 1,right = n, m = (left+right)/2;
			tmp_big = DBL_MAX;

			while(left <= right){
				tmp = (double)m/(double)bunbo;

				if(tmp > sqrt_p){
					tmp_big = tmp;
					tmp_bunshi = m;
					right = m-1;
				}else{
					left = m+1;
				}
				m = (left+right)/2;
			}

			if(near_big > tmp_big){
				near_big = tmp_big;
				x = tmp_bunshi;
				y = bunbo;
			}
		}

		if(u >= v){
			common = calc(u,v);
		}else{
			common = calc(v,u);
		}

		u /= common;
		v /= common;

		if(x >= y){
			common = calc(x,y);
		}else{
			common = calc(y,x);
		}

		x /= common;
		y /= common;

		printf("%d/%d %d/%d\n",x,y,u,v);
	}

	return 0;
}

Measured memory_bytes: 3124
import sys

def solve(game: dict):
    card = game['a'].pop(0)
    while game[card]:
        card = game[card].pop(0)
    print(str.upper(card))

def main():
    game = {turn: list(sys.stdin.readline().rstrip()) for turn in 'abc'}
    solve(game)

if __name__ == '__main__':
    main()


Measured memory_bytes: 61808
# -*- coding:utf-8 -*-
# /usr/bin/python3

from math import ceil

def main():
  number_of_tree, monitering_range = map(int, input().split())
  monitering_range = monitering_range*2 + 1
  number_for_monitor = ceil(number_of_tree / monitering_range)
  print(number_for_monitor)
  pass

if __name__=='__main__':
  main()


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

typedef signed long long ll;
const int MX = 30;
int A[MX];

int main() {
    string S;
    cin >> S;
    int sz = S.size();
    bool ok = true;

    for(int i = 0; i < sz; i++) {
        if(A[S[i] - 'a']) {
            ok = false;
            break;
        }
        A[S[i] - 'a']++;
    }

    ok ? cout << "yes\n" : cout << "no\n"; 

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;


void solve(long long S){

    long long ichi;

    ichi = S % 10;

    if( (ichi==3) ){
        cout << "bon" << endl;
    }else if( (ichi==0) || (ichi==1) || (ichi==6) || (ichi==8) ){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }

    return;

}

int main(){
    long long S;
    scanf("%lld",&S);
    solve(S);
    return 0;
}


Measured memory_bytes: 3764
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
print("ABC" + s)

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

const long long M = 1e9 + 7;
long long dp[101][4][4][4];

int main() {
    int N;
    cin >> N;
    dp[0][3][3][3] = 1;
    for (int len = 0; len < N; len++) {
        for (int c1 = 0; c1 < 4; c1++) {
            for (int c2 = 0; c2 < 4; c2++) {
                for (int c3 = 0; c3 < 4; c3++) {
                    if (dp[len][c1][c2][c3] == 0) continue;

                    for (int a = 0; a < 4; a++) {
                        if (a == 2 && c1 == 1 && c2 == 0) continue;
                        if (a == 2 && c1 == 0 && c2 == 1) continue;
                        if (a == 1 && c1 == 2 && c2 == 0) continue;
                        if (a == 2 && c1 == 1 && c3 == 0) continue;
                        if (a == 2 && c2 == 1 && c3 == 0) continue;

                        dp[len + 1][a][c1][c2] =
                            (dp[len + 1][a][c1][c2] + dp[len][c1][c2][c3]) % M;
                    }
                }
            }
        }
    }

    long long ans = 0;
    for (int c1 = 0; c1 < 4; c1++) {
        for (int c2 = 0; c2 < 4; c2++) {
            for (int c3 = 0; c3 < 4; c3++) {
                ans = (ans + dp[N][c1][c2][c3]) % M;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<vector>
#include<string>
#include<iterator>
#include<iomanip>
#include<cmath>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;

void fast(){
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(0);
}

int main()
{
	fast();

	int a[1000],sumeven=0,sumodd=0;
	int n;
	vector<int> v;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		v.push_back(a[i]);
	}
	sort( v.begin(),v.end());
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0)
			sumeven += v[i];
		else
			sumodd += v[i];
	}
	cout << abs(sumeven - sumodd) << endl;

}



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

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long

const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<string, int> ma;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ma[s]++;
    }
    cout << "AC x " << ma["AC"] << "\n";
    cout << "WA x " << ma["WA"] << "\n";
    cout << "TLE x " << ma["TLE"] << "\n";
    cout << "RE x " << ma["RE"] << "\n";
    return 0;
}


Measured memory_bytes: 3640
def main():
    S = input()
    N = len(S)

    if check(S) and check(S[:(N-1)//2]) and check(S[(N+3)//2-1:]):
        print("Yes")
    else:
        print("No")


def check(s):
    #print(s)
    for i in range(len(s) // 2):
        c1 = s[i]
        c2 = s[-(i+1)]
        if c1 != c2:
            return False
    return True

main()

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

    if(a > b)
    printf("a > b\n");

    if(a == b)
    printf("a == b\n");

    return 0;
}

Measured memory_bytes: 580
#include <iostream>
using namespace std;
int N;
int main() {
  cin >> N;
  int ma = -1, mb = 1 << 30;
  for(int i = 0; i < N; ++i) {
    int a, b;
    cin >> a >> b;
    if(a > ma) {
      ma = a;
      mb = b;
    }
  }
  cout << ma + mb << endl;
}

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

int main(){
	int n, m;

	while(cin >> n >> m){
		if(n < m) swap(n, m);

		while(n % m != 0){
			int d = n % m;
			n = m;
			m = d;
		}
		cout << m << endl;
	}
}

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


int main(){
  int N,D;
  cin >> N >> D;
  vector<vector<int>>X(N,vector<int>(D));
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++){
      cin >> X.at(i).at(j);
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int norm =0;
      for(int k=0;k<D;k++){
        int diff =abs(X[i][k]-X[j][k]);
        norm += diff*diff;
      }
      bool check = false;
      for(int k=0;k<=norm; k++){
        if(k*k==norm){
          check = true;
        }
      }
      if(check) ++ans;
    }
  }
  cout << ans << endl;
                      
      
    
}
      


Measured memory_bytes: 256