akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long ll;

int main()
{
	int n;
	string str;
	vector<int> s;
	cin>>n;
	cin>>str;
	rep(i,n){
		int num = str[i] - '0';
		s.push_back(num);
	}
	int ans = 0;
	for(int i = 0; i <= 9; i++){
		for(int j = 0; j <= 9; j++){
			for(int k = 0; k <= 9; k++){
				auto iter = s.begin();
				while( iter != s.end()){
					if( *iter == i){
						iter++;
						break;
					}
					iter++;
				}
				while( iter != s.end()){
					if( *iter == j){
						iter++;
						break;
					}
					iter++;
				}
				while( iter != s.end()){
					if( *iter == k){
						break;
					}
					iter++;
				}
				if( iter != s.end()){
					ans++;
					//cout<<i<<j<<k<<endl;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    vector<int> cs(26), ct(26);
    int j = 0;
    for(char c = 'a'; c <= 'z'; c++) {
        rep(i, s.size()) {
            if(s[i] == c) {
                cs[j]++;
            }
            if(t[i] == c) {
                ct[j]++;
            }
        }
        j++;
    }

    sort(cs.begin(), cs.end());
    sort(ct.begin(), ct.end());

    rep(i, 26) {
        if(cs[i] != ct[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 776
#!/usr/bin/env python3
import math

A, B, H, M = map(int, input().split())

theta_A = H * 30 + M/2
theta_B = 6*M

theta_test = abs(theta_A - theta_B)
theta = min(theta_test, 360 - theta_test)

cos = math.cos(math.radians(theta))

test = A**2 + B**2 - 2*A*B*cos

print(math.sqrt(test))

Measured memory_bytes: 9512
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int a[N],b[N], n, sum1,sum2;
signed main(void){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    for(int i=1;i<=n;i++) scanf("%lld",b+i);
    for(int i=1;i<=n;i++) {
        if(a[i] > b[i]) sum1 += (a[i] - b[i]);
        if(a[i] < b[i]) sum2 += (b[i] - a[i])/2;
    }
    if(sum1 <= sum2) puts("Yes\r");
    else puts("No");
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a[0];
  int min = a[0], max = a[0], minpos = 1, maxpos = 1;
  for (int i = 1; i < n; i++) {
    cin >> a[i];
    if (min > a[i]) {
      min = a[i];
      minpos = i + 1;
    }
    if (max < a[i]) {
      max = a[i];
      maxpos = i + 1;
    }
  }
  if (min < 0 && max > 0) {
    cout << 2 * n - 1 << endl;
    if (-min > max) {
      for (int i = 0; i < n; i++) {
        cout << minpos << " " << i + 1 << endl;
      }
      for (int i = n; i > 1; i--) {
        cout << i << " " << i - 1 << endl;
      }
    } else {
      for (int i = 0; i < n; i++) {
        cout << maxpos << " " << i + 1 << endl;
      }
      for (int i = 1; i < n; i++) {
        cout << i << " " << i + 1 << endl;
      }
    }
  } else {
    cout << n - 1 << endl;
    if (min < 0) {
      for (int i = n; i > 1; i--) {
        cout << i << " " << i - 1 << endl;
      }
    } else {
      for (int i = 1; i < n; i++) {
        cout << i << " " << i + 1 << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define zeros(x) ((x) & (-x))
#define inf 1e18

using namespace std;

int V[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);

    int x;
    cin>>x;
    cout<<V[x-1];

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int  long long int
#define ld 	 long double
#define F 	 first
#define S 	 second
#define P 	 pair<int,int>
#define pb 	 push_back
#define mod  1000000007
#define inf  1e18
#define endl '\n'
const int N = 55;//change it when needed
struct mat {
	int m[N][N];
	void identity() {
		memset(m, 0, sizeof(m));
		for (int i = 0; i < N; i++) {
			m[i][i] = 1;
		}
	}
	mat operator*(const mat &b)const {
		mat r;
		memset(r.m, 0, sizeof(r.m));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					r.m[i][j] = (r.m[i][j] + m[i][k] * b.m[k][j]) % mod;
				}
			}
		}
		return r;
	}
};
mat adj;
mat powerMatrix(int k) {
	mat r;
	r.identity();
	while (k) {
		if (k & 1) {
			r = r * adj;
		}
		k /= 2;
		adj = adj * adj;
	}
	return r;
}
void solve() {
	int n, k;
	cin >> n >> k;
	memset(adj.m, 0, sizeof(adj.m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> adj.m[i][j];
		}
	}

	mat res = powerMatrix(k);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans += res.m[i][j];
			ans %= mod;
		}
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  string str,str1;
  int n,c,i;
  cin>>str>>str1;
  n=str.length();
  c=0;
  for(i=0;i<n;i++)
  {
    if(str[i]!=str1[i])
      c++;
  }
  cout<<c<<endl;
  return 0;
}

Measured memory_bytes: 3912
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>

#define ll long long

using namespace std;

int A;
int cnt5 = 0;
int cnt7 = 0;

int main()
{
    for (int i = 0; i < 3; i++) {
        cin >> A;
        switch (A) {
        case 5:
            cnt5++;
            break;
        case 7:
            cnt7++;
            break;
        }
    }
    cout << (cnt5 == 2 && cnt7 == 1 ? "YES" : "NO") << endl;
    return 0;
}

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

int main() {
  int N, a;
  //set<int> A;
  bool isDistinct = true;
  
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  
  for (int i = 0; i < N-1; i++) {
    if (A.at(i + 1) == A.at(i)) {
      isDistinct = false;
      break;
    }
  }
  
  isDistinct ? cout << "YES" << endl : cout << "NO" << endl; 
}

Measured memory_bytes: 1024
#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()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, r,k;
    cin>>n>>r;

    if(n < 10)
    {
        k = 100 * (10 - n);
        cout<<(r + k)<<endl;
    }
    else
    {
        cout<<r<<endl;
    }
    

    return 0;
}


Measured memory_bytes: 256
// https://ynucpc.github.io/blog/2018/04/15/cp_vscode/
// http://www.atmarkit.co.jp/ait/articles/1509/08/news019.html

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,n,m) for(ll i=(n);i<(ll)(m);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b)) 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int _stoi(string s, int tmp=10){
	istringstream stm(s);
	int res;
	stm >> res;
	return res;
}
double _stod(string s, int tmp=10){
	istringstream stm(s);
	double res;
	stm >> res;
	return res;
}
template<typename T>string to_string(const T& n){
	std::ostringstream stm;
	stm << n;
	return stm.str();
}

// 降順ソート: sort(A, A+N, greater<>());
// min: *min_element(A, A+N)
// argmin: min_element(A, A+N)-A

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


int main(){	
	// ll A; cin >> A;
	// cout << "hello" << _stoi("14") << max({1,3}) << endl;
	string S;
	cin >> S;
	ll n = S.size();
	ll a=0, b=0;
	rep(i, n){
		if ((S[i]=='0')^(i%2==0)) a++;
		else b++;
	}
	cout << min(a, b) << endl;

}








Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
using namespace std;
int n;
long long sum[200500],a[200500];
int main()
{
    ios::sync_with_stdio(false);
    int k,n,i;
    sum[0]=0;
    cin >> n >> k;
    for (i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    long long ans=1e18+7;
    for (i=1;i+k-1<=n;i++)
    {
        long long tmp=a[i+k-1]-a[i];
        if ((a[i]<0) && (a[i+k-1]<0)) tmp+=abs(a[i+k-1]);
        else if ((a[i]>0) && (a[i+k-1]>0)) tmp+=a[i];
        else tmp+=min(-a[i],a[i+k-1]);
        ans=min(ans,tmp);
    }
    cout << ans;
    return 0;
}

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

int main(){
    int n;
    /*入力*/
    cin >> n;
    int a[n],b[n],c[n];
    int sum = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    for(int i = 0;i < n;i++){
        cin >> b[i];
        sum += b[i];
    }
    for(int i = 0;i < n - 1;i++){
        cin >> c[i];
    }
    for(int i = 1;i < n;i++){
        if(a[i - 1] + 1 == a[i]){
            sum += c[a[i - 1] - 1];
        }
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long ans;
int n, mn = 1e9, cnt[N];
vector<pair<int, int> > gr[N];
vector<int> Centroid;
void dfs(int v, int par = 0, int w = 0) {
	bool z = true;
	for (auto u : gr[v])
		if (u.first != par) {
			dfs(u.first, v, u.second);
			cnt[v] += cnt[u.first];
			if (cnt[u.first] > n / 2)
				z = false;
		}
	cnt[v]++;
	ans += 1ll * min(cnt[v], n - cnt[v]) * 2 * w;
	if (n - cnt[v] > n / 2)
		z = false;
	if (z)
		Centroid.push_back(v);
}
int main() {
	ios_base::sync_with_stdio (false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		x--, y--;
		gr[x].push_back({y, w});
		gr[y].push_back({x, w});
	}
	dfs(0);
	if (Centroid.size() == 2) {
		int v = Centroid[0], u = Centroid[1];
		for (auto p : gr[v]) {
			if (p.first == u)
				ans -= p.second;
		}
	}
	else {
		int v = Centroid[0];
		for (auto p : gr[v]) 
			mn = min(mn, p.second);
		ans -= mn;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 12800
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#if defined(DAIJOBU)
#include "/home/ichigo/includes.hpp"
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int main(){
	FIO
	
	int x, a, b;
	cin >> x >> a >> b;
	if(abs(x - a) > abs(x - b))puts("B");
	else puts("A");
	//cout << min(abs(x - a), abs(x - b)) << '\n';
 	return 0; 
}


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

int main() {
  int N;
  int ans=100000000;
  cin >> N;
  
  rep(i, N) {
  	int A;
    cin >> A;
    int curr=0;
    while (A % 2 == 0) {
      curr+=1;
      A /= 2;
    }
    if (ans > curr) ans = curr;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 3496
#include<stdio.h>

int abss(int a,int b){
  if(a>b)
    return a-b;
  else
    return b-a;
}

int main(){
  int N;
  scanf("%d",&N);
  int A[N];
  int i,j,k=10000000,ika,ijyou;
  for(i=0;i<N;i++){
    scanf("%d ",&A[i]);
  }
  
  for(i=0;i<N;i++){
    ika=ijyou=0;
    
    for(j=0;j<=i;j++){
      ika+=A[j];
    }
    for(j=i+1;j<N;j++)
      ijyou+=A[j];
    if(k>abss(ika,ijyou))
      k=abss(ika,ijyou);
  }
  
  printf("%d\n",k);
  return 0;
}

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


void solve(long long N, std::vector<long long> A, std::vector<long long> accs){
  long long mymin = LLONG_MAX;
  long long acc = 0;
  for(long long i = (N-2); i >= 0; i--){
    acc += A[i+1];

    mymin = min(mymin, abs(accs[i] - acc));
  }

  cout << mymin << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    long long acc = 0;
  scanf("%lld",&N);
  std::vector<long long> A(N);
  std::vector<long long> accs(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&A[i]);
    acc += A[i];
    accs[i] = acc;
  }
    solve(N, std::move(A), move(accs));
    return 0;
}


Measured memory_bytes: 6356
#include <bits/stdc++.h>
using namespace std;
int main (void) {
    string S;
    cin >> S;
    if (S.at(2) == S.at(3) && S.at(4) == S.at(5)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#define ll long long
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define set2d(array, val, m, n) memset(array, val, sizeof(array[0][0]) * m * n);
#include <bits/stdc++.h>
using namespace std;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x %= p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
ll po(ll base, ll powerRaised)
{
    if (powerRaised != 0)
        return (base * po(base, powerRaised - 1));
    else
        return 1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    set<ll> st;
    if (n == 2)
    {
        cout << "1";
        return 0;
    }
    for (ll i = 2; i * i <= n; i++)
    {
        ll num = n;
        while (num % i == 0)
            num /= i;
        if (num % i == 1)
            st.insert(i);
    }
    n--;
    for (ll i = 2; i * i <= n; i++)
    {
        ll num = n;
        if (num % i == 0)
        {
            st.insert(num / i);
            st.insert(i);
            num /= i;
        }
    }

    cout << st.size() + 2;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
long long cut;
int a[100100],b[100100],c[100100];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for (int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	sort(a+1,a+n+1);
	sort(c+1,c+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		int ans=0,l=1,r=n;
		long long now;
		while (l<=r)
		{
			int mid=l+r>>1;
			if (a[mid]<b[i]) ans=mid,l=mid+1;
			else r=mid-1;
		}
		now=ans;
		ans=0,l=1,r=n;
		while (l<=r)
		{
			int mid=l+r>>1;
			if (c[mid]>b[i]) ans=mid,l=mid+1;
			else r=mid-1;
		}
		//cout<<now<<" ";
		now=1ll*now*ans;
		//cout<<now<<endl;
		cut+=now;
	}
	printf("%lld",cut);
}

Measured memory_bytes: 1408
from math import floor
from decimal import Decimal

S = list(input())
T = list(input())

isSuccess = False

for i in reversed(range(len(S) - len(T) + 1)):
    T_str = S[i: i + len(T)]
    for j in range(len(T)):
        if T_str[j] != T[j] and T_str[j] != "?":
        	break
    else:
        isSuccess = True
        S[i:i + len(T)] = T
        break
if isSuccess == False:
    print("UNRESTORABLE")
else:
    string = ",".join(S)
    string = string.replace('?', 'a')
    S = string.split(',')
    print("".join(map(str,S)))

Measured memory_bytes: 5076
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define fi first
#define se second
#define For(i,a,b) for(ll i=a;i<b;i++)
#define RFor(i,b,a) for(ll i = b;i>=a;i--)
#define sz size()
#define PQ priority_queue
#define len length()
#define mll map<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vpll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define mp(x,y)  make_pair(x,y)
#define pb push_back
#define ins insert
#define er erase
#define pf push_front
#define ALL(v) v.begin(),v.end()
#define LAPAK ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 2e18;
const ll MAX = 1e7 + 2;
vll a(MAX);

int main() {
    LAPAK
    ll n;
    cin>>n;
    for(int i = 1;i<MAX;i++){
        for(int j = i;j<MAX;j+=i){
            a[j]++;
        }
    }
    ll ans = 0;
    for(int i = 1;i<=n;i++)ans += i*a[i];
    
    cout<<ans;
    return 0;
}

Measured memory_bytes: 81204
#include <stdio.h>
int bubbleSort(int A[],int N){
  int i,j,t;
  int sw=0;
  int flag=1;
  for(i=0 ; flag ; i++){
    flag = 0;
  for(j=N-1 ; j>=i+1 ; j--){
    if(A[j] < A[j-1]){
      t = A[j];
      A[j] = A[j-1];
      A[j-1] = t;
      flag=1;
      sw++;
    }
  }
  }
  return sw;
}
int main(){
  int A[100],N,sw,i;
  scanf("%d",&N);
  for(i=0 ; i<N ; i++)
    scanf("%d",&A[i]);
    sw = bubbleSort(A,N);

  for(i=0 ; i<N ; i++){
    if(i>0)
      printf(" ");
      printf("%d" ,A[i]);
  }
  printf("\n");
  printf("%d\n" ,sw);

    return 0;
}




Measured memory_bytes: 2104
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main(void)
{
	for(int num; cin >> num, num > 0; ) {
		int  p[1000], a_sum = 0;
		double ave, dev, d_sum = 0.0;
	
		for(int i = 0; i < num; i++) {
			cin >> p[i];
			a_sum += p[i];
		}
	
		ave = (double)a_sum / num;
	
		for(int i = 0; i < num; i++)
			d_sum += (p[i] - ave) * (p[i] - ave);
	
		dev = sqrt(d_sum / num);
	
		printf("%.8f\n", dev);
	}
	
	return 0;
}

Measured memory_bytes: 1196
using System;

namespace noteCsharp
{
    class Program
    {
        static void Main(string[] args)
        {
            string iranai = Console.ReadLine();
            iranai = null;
            string[] inputAn = Console.ReadLine().Split(char.Parse(" "));
            int[] inputAn_int = new int[inputAn.Length];
            for(int cycle = 0; cycle < inputAn.Length; cycle++)
            {
                inputAn_int[cycle] = int.Parse(inputAn[cycle]);
            }
            for(int cycle = 0; cycle < inputAn.Length - 1; cycle++)
            {
                Console.Write(inputAn_int[inputAn.Length - cycle - 1]+" ");
            }
            Console.Write(inputAn_int[0]);
            Console.WriteLine();
        }
    }
}



Measured memory_bytes: 15880
R,G,B,N=map(int,input().split())
cnt=0
for r in range(N//R+1):
    for g in range(N//G+1):
        if (N-r*R-g*G)<0:
            break
        elif (N-r*R-g*G)%B==0:
            cnt+=1

        
print(cnt)

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;
int block[110][110]={};
//status unsolved
int main(){
    
    int h,w;
    cin>>h>>w;
    rep2(i,h)rep2(k,w){
        char c;
        cin>>c;
        if(c=='#')block[i][k]=1;
        else block[i][k]=0;
    }
    int point[110][110];
    rep(i,110)rep(k,110)point[i][k]=1e9;

    /*
    queue<int>q;
    q.push(0);
    q.push(1);
    q.push(1);
    int dx[2]={0,1};
    int dy[2]={1,0};
    
    
    rep2(i,h)rep2(k,w)point[i][k]=1e9;
    while(!q.empty()){
        int nowp=q.front();q.pop();
        int nowx=q.front();q.pop();
        int nowy=q.front();q.pop();
        if(block[nowy][nowx]=='#'){
                nowp++;
        }
        point[nowy][nowx]=min(point[nowy][nowx],nowp);

        rep(i,2){
            int nx=nowx+dx[i];
            int ny=nowy+dy[i];
            if(nx<1 || nx>w || ny<1 ||ny>h)continue;
            q.push(nowp);
            q.push(nx);
            q.push(ny);
        }
    }
    */
    point[1][1]=block[1][1];
    rep2(i,h)rep2(k,w){
        if(i==1 && k==1)continue;
        if(point[i-1][k]<point[i][k-1]){
            point[i][k]=point[i-1][k];
            if(block[i-1][k]==0 && block[i][k]==1){
                point[i][k]++;
            }
        }
        else if(point[i-1][k]>point[i][k-1]){
            point[i][k]=point[i][k-1];
            if(block[i][k-1]==0 && block[i][k]==1){
                point[i][k]++;
            }
        }
        else{
            point[i][k]=point[i][k-1];
            if((block[i][k-1]==0 && block[i][k]==1)
            && (block[i-1][k]==0 && block[i][k]==1)){
                point[i][k]++;
            }
        }
    }
    cout<<point[h][w]<<endl;
    return 0;

}
/*

4 4
.###
#.#.
##.#
.#..
*/


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define prique priority_queue
#define inf 1145141919364364
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
typedef pair<ll, ll>P;
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
signed main(){
	ll n;
	cin>>n;
	cout<<n*n*n<<endl;
}



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

using namespace std;

int main(int argc, char* argv[]) {
  long long N;
  cin >> N;

  if (N % 2 == 1)
    cout << 0 << endl;
  else {
    long long ret = 0;
    long long tmp = 10;
    while (N / tmp > 0) {
      ret += N / tmp;
      tmp *= 5;
    }
    cout << ret << endl;
  }

  return 0;
}

Measured memory_bytes: 256
def swap(b,e)
    return Float::INFINITY if b.count("0") != e.count("0")
    i = 0
    ret = 0
    while i < b.length
        if b[i] == e[i]
            i += 1
            next
        end
        j = i + 1
        while b[j] == b[i]
            j += 1
        end
        ret += j - i
        b[i], b[j] = b[j], b[i]
        i += 1
    end
    return ret
end

n, m = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
p = gets.split.map(&:to_i)
s0 = ""
s1 = ""
p.each_slice(2) do |d|
    if d.size == 2
        s0 << "0" * d[0]
        s0 << "1" * d[1]
    else
        s0 << "0" * d[0]
    end
end
p.each_slice(2) do |d|
    if d.size == 2
        s1 << "1" * d[0]
        s1 << "0" * d[1]
    else
        s1 << "1" * d[0]
    end
end
puts [swap(b.join,s0), swap(b.join,s1)].min

Measured memory_bytes: 6128
#include <cmath>
#include <cstdio>
#include <algorithm>

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

using namespace std;

const double EPS=1e-8;
const double PI=acos(-1);

struct point{
	double x,y;
	point():x(0),y(0){}
	point(double x,double y):x(x),y(y){}
	point operator+(const point &a)const{ return point(x+a.x,y+a.y); }
	point operator-(const point &a)const{ return point(x-a.x,y-a.y); }
};

point operator*(double c,const point &a){ return point(c*a.x,c*a.y); }

double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

struct circle{
	point c;
	double r;
	circle():c(point(0,0)),r(0){}
	circle(const point &c,double r):c(c),r(r){}
};

double area(double a,double b,double c){
	return sqrt((a+b+c)*(b+c-a)*(c+a-b)*(a+b-c))/4;
}

double common_area(const circle &C1,const circle &C2){
	double d=abs(C1.c-C2.c);
	double r1=C1.r,r2=C2.r;
	if     (r1+r2<d+EPS) return 0;
	else if(d+r1<r2+EPS) return PI*r1*r1;
	else if(d+r2<r1+EPS) return PI*r2*r2;
	else{
		double theta1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
		double theta2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));
		return r1*r1*theta1+r2*r2*theta2-2*area(r1,r2,d);
	}
}

int main(){
	for(int h,w,a,b,acapb;~scanf("%d%d%d%d%d",&w,&h,&a,&b,&acapb);){
		if(w==0) break;

		bool flag=false;
		if(a<b) swap(a,b), flag=true;

		circle Ca,Cb;
		Ca.r=sqrt(a/PI);
		Ca.c=point(Ca.r,Ca.r);
		Cb.r=sqrt(b/PI);
		Cb.c=point(w-Cb.r,h-Cb.r);

		// 円がそもそも長方形に入らないとき ( 入力の制約で排除すべき? )
		if(2*Ca.r>min(h,w)+EPS
		|| 2*Cb.r>min(h,w)+EPS){ puts("impossible"); continue; }

		if(common_area(Ca,Cb)>acapb+EPS){ puts("impossible"); continue; }

		// binary search
		double lo=0,hi=1;
		rep(_,50){
			double mi=(lo+hi)/2;
			double t=mi;
			circle C((1-t)*Ca.c+t*Cb.c,Cb.r);
			if(common_area(Ca,C)<acapb) hi=mi; else lo=mi;
		}
		Cb=circle((1-lo)*Ca.c+lo*Cb.c,Cb.r);

		if(flag) swap(Ca,Cb);

		printf("%.9f %.9f %.9f %.9f %.9f %.9f\n",Ca.c.x,Ca.c.y,Ca.r,Cb.c.x,Cb.c.y,Cb.r);
	}

	return 0;
}

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

int main() {

  int N, K; cin >> N >> K;
  vector<long long> p(N);
  for (int i = 0; i < N; ++i) cin >> p[i], ++p[i]; // 1 足しておく

  
  vector<long long> s(N+1, 0);
  for (int i = 0; i < N; ++i) s[i+1] = s[i] + p[i];

  
  long long res = 0;
  for (int i = 0; i+K <= N; ++i) res = max(res, s[i+K] - s[i]);
  cout << fixed << setprecision(10) << (double)(res)/2 << endl;
  
}

Measured memory_bytes: 3328
import sys
N = int(input())
H = list(map(int,input().split()))
for i in reversed (range(N-1)):
  if H[i] > H[i+1]:
    H[i] = H[i] - 1
    if H[i] > H[i+1]:
      print("No")
      sys.exit()
print("Yes")

Measured memory_bytes: 14396
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
    def __init__(self, n):
        self.n = n #要素数
        self.parents = [-1] * n #親格納配列(親のときは下流の要素数のマイナスを返す)

    def find(self,x):
        if self.parents[x] < 0: #親のとき
            return x
        else:
            self.parents[x] = self.find(self.parents[x]) #再帰で親に繋ぎ変える
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: #親が同じときスキップ
            return

        if self.parents[x] > self.parents[y]: #要素数が多いほうをxにする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #xの属するグループの要素一覧
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self): #根の一覧
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self): #グループ個数
        return len(self.roots())

    def all_group_members(self): #根とその要素の辞書配列
        return {r: self.members(r) for r in self.roots()}

    def __str__(self): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

        
n,m,k=map(int,input().split())

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if U.same(a,b):
        K[a].append(b)
        K[b].append(a)

ans=[]
for i in range(n):
    m=M[i]
    k=K[i]
    ans.append(U.size(i)-len(m)-len(k)-1)
print(*ans)

Measured memory_bytes: 46820
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

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


#define PB push_back
#define MP make_pair
#define F first
#define S second

/*long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ret;
}*/

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}


int main(){
	double a,b;
	double h,m;
	cin >> a >> b >> h >> m;
	double hkakudo=2*M_PI*(h+m/60)/12;
	double mkakudo=2*M_PI*(m/60);

	cout << fixed << setprecision(12);
	cout << sqrt(pow(a*cos(hkakudo) - b*cos(mkakudo),2)+pow(a*sin(hkakudo)-b*sin(mkakudo),2)) << endl;	
}

Measured memory_bytes: 4088
s = input().split() #s_1 s_2を分割して取得し、sに値を入れる
n = int(s[0])
r = int(s[1])

if n > 0 and n <= 10:
	i = r + 100 * (10 - n)
else:
	i = r
  
print(i)

Measured memory_bytes: 2940
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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=1e9+7;

int main()
{
    string s;
    cin >> s;
    ll n=s.length();
    vector<char> t;
    rep(i,n){
        if(s[i]=='B'){
            if(t.size()!=0){
                t.pop_back();
            }
        }
        else{
            t.push_back(s[i]);
        }
    }
    for(auto x:t){
        cout << x;
    }
    cout << endl;
    return 0;
} 

Measured memory_bytes: 256
from sys import exit

N, Y = map(int, input().split())

FAIL = '-1 -1 -1'

for z in range(N + 1):
    x = 4 * z / 5 + Y / 5000 - N
    y = -9 * z / 5 - Y / 5000 + 2 * N
    if x == int(x) and x >= 0\
       and y == int(y) and y >= 0:
        print('{} {} {}'.format(int(x), int(y), z))
        exit()

print(FAIL)


Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 100 == 0) {
		x /= 100;
		ret++;
	}

	return ret;
}


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

	cin >> a >>b;

	int cnt = 0;
	int val = 0;
	rep(i, 1, 1100000) {
		if (calc(i) == a)
		{
			cnt++;
		}

		if (cnt == b) {
			cout << i << endl;
			return 0;
		}

	}


}
	

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repr(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<(int)(n);i++)
#define INF 99999999999999

    /*Solve*/

int main(){
    ll n,c,k;
    cin >> n >> c >> k;
    vector<ll> t;
    ll x;
    rep(i,n){
        cin >> x;
        t.push_back(x);
    }
    sort(t.begin(),t.end());
    ll dep=t[n-1];
    ll cnt=1;
    ll cntc=0;
    repr(i,n-1){
        if(t[i]<=dep && dep<=t[i]+k){
            if((cntc-1)%c==c-1 && cntc%c==0){
                cntc=1;
                cnt++;
                dep=t[i];
            }else cntc++;
        }else{
            cntc=1;
            cnt++;
            dep=t[i];
        }
    }
    if(c==1)cnt=n;
    cout << cnt;
}

Measured memory_bytes: 1400
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    int x = abs(sx - tx);
    int y = abs(sy - ty);
    char ans[4 * x + 4 * y + 8];

    int index = 0;
    for (; index < x; index++)
    {
        ans[index] = 'R';
    }

    for (; index < x + y; index++)
    {
        ans[index] = 'U';
    }

    for (; index < x + y + x; index++)
    {
        ans[index] = 'L';
    }

    for (; index < x + y + x + y + 1; index++)
    {
        ans[index] = 'D';
    }

    for (; index < x + y + x + y + x + 2; index++)
    {
        ans[index] = 'R';
    }

    for (; index < x + y + x + y + x + y + 3; index++)
    {
        ans[index] = 'U';
    }
    ans[index] = 'L';
    index++;
    ans[index] = 'U';
    index++;
    for (; index < x + y + x + y + x + y + x + 6; index++)
    {
        ans[index] = 'L';
    }
    for (; index < x + y + x + y + x + y + x + y + 7; index++)
    {
        ans[index] = 'D';
    }
    ans[index] = 'R';
    repi(i, index + 1, 0)
    {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
def show_missing_card(suit, rank_exists):
    for i in range(13):
        if not rank_exists[i]:
            print('{suit} {rank}'.format(suit=suit, rank=(i + 1)))


spades = 'S'
hearts = 'H'
clubs = 'C'
diamonds = 'D'

trump_exists_map = {
    spades: [False] * 13,
    hearts: [False] * 13,
    clubs: [False] * 13,
    diamonds: [False] * 13
}

num_cards = int(input())

inputs = []

for i in range(num_cards):
    inputs.append(input())

for input_value in inputs:
    suit, rank = input_value.split()

    rank = int(rank)

    trump_exists_map[suit][rank - 1] = True

show_missing_card(spades, trump_exists_map[spades])
show_missing_card(hearts, trump_exists_map[hearts])
show_missing_card(clubs, trump_exists_map[clubs])
show_missing_card(diamonds, trump_exists_map[diamonds])



Measured memory_bytes: 5604
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    ll ans = 0;
    int N_dig = to_string(N).size();
    string strN = to_string(N);
    int topN = strN[0] - 0x30;
    int tailN = strN[strN.size() - 1] - 0x30;
    vll T(N_dig + 1);
    T[0] = 1;
    REP(i, 1,  N_dig + 1) {
        T[i] = T[i - 1] * 10;
    }
    REP(A, 1, N + 1) {

        string strA = to_string(A);
        int topA = strA[0] - 0x30;
        int tailA = strA[strA.size() - 1] - 0x30;
        if (tailA == 0) continue;
        REP(d, 1, N_dig + 1) {
            if (d == 1) {
                if (topA == tailA) ans++;
                continue;
            }
            if (d < N_dig) {
                ans += max(1LL, T[d - 2]);
            }
            else {
                if (tailA > topN) continue;
                
                if (tailA < topN) {
                    ans += max(1LL, T[d - 2]);
                }
                else {
                    if (topA <= tailN) {
                        if (strN.size() > 2)
                            ans += ll(stol(strN.substr(1, strN.size() - 2))) + 1;
                        else ans++;
                    }
                    else {
                        if (strN.size() > 2) {
                            ll add = ll(stol(strN.substr(1, strN.size() - 2))) - 1;
                            if (add >= 0) add++;
                            else add = 0;
                            ans += add;
                        }
                    }

                }
            }
        }
        //cout << "A:" << A << "ans" << ans << endl;
    }

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

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

signed main(){
  int N,M;
  cin>>N>>M;
  string ans="No";
  if(N==M)ans="Yes";
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
  int n,m,h,f;
  vector<int> vec;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d %d",&h,&f);
    vec.push_back(h*60+f);
  }
  scanf("%d",&m);
  for(int i=0;i<m;i++){
    scanf("%d %d",&h,&f);
    vec.push_back(h*60+f);
  }
  sort(vec.begin(),vec.end());
  vec.erase(unique(vec.begin(),vec.end()),vec.end());
  for(int i=0;i<vec.size();i++){
    printf("%d:%02d",vec[i]/60,vec[i]%60);
    if(i != vec.size()-1) putchar(' ');
  }
  putchar('\n');
  return(0);
}



Measured memory_bytes: 2760
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int MAXN = 200005;
const int MOD = 1000000007;

ll aa[MAXN],bb[MAXN];

ll fun(ll arr[],ll n){
	ll ans = 0;
	for(int i=1;i<n;i++){
		ans = (ans + arr[i] * (i) % MOD * (n-i) % MOD) % MOD;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n; cin >> n;
	int m; cin >> m;
	for(int i=0;i<n;i++) cin >> aa[i];
	for(int i=0;i<m;i++) cin >> bb[i];
	for(int i=n-1;i;i--) aa[i] -= aa[i-1];
	for(int i=m-1;i;i--) bb[i] -= bb[i-1];
	ll ka = fun(aa,n);
	ll kb = fun(bb,m);
	ka = ka * kb % MOD;
	cout << ka << '\n';
	return 0;
}


Measured memory_bytes: 1792
N,K = map(int,input().split())
A = list(map(int,input().split()))
total = 0
saidai = -9999
ans = 0
B = [0]*(len(A)+1)
for i in range(len(A)):
    total += A[i]
    B[i+1] = total
for j in range(N-K+1):
     if B[j+K]-B[j]>saidai:
            saidai = B[j+K]-B[j]
            P = A[j:j+K]
for i in range(len(P)):
    ans += (0.5*P[i]*(P[i]+1))/P[i]
print(ans)

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

// ??????: http://tubo28.me/algorithm/union-find/
struct UnionFind {
    vector<int> parent;
    int set_num;

    UnionFind(int n) {
        parent.resize(n, -1);
        set_num = n;
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            if (size(x) < size(y)) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            set_num--;
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    int find(int x) {
        if (parent[x] < 0) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    int size(int x) {
        return -parent[find(x)];
    }

    int size() {
        return set_num;
    }
};

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

    int n, q;
    cin >> n >> q;
    UnionFind uf(n);

    for (int i = 0; i < q; i++) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            uf.unite(x, y);
        } else {
            cout << (uf.is_same(x, y) ? 1 : 0) << endl;
        }
    }
    return 0;
}

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

int main(){
  int n,i,r,b;
  string s;
  cin >> n >> s;
  r=0;
  b=0;
  for(i=0;i<n;i++){
    if(s.at(i)=='R'){
      r++;
    }else{
      b++;
    }
  }
  
  if(r>b){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
#!/usr/bin/env perl

use strict;
use warnings;
use Data::Dumper;

my $line = <>; chomp $line;
my @sd = split //, $line;
$line = <>; chomp $line;
my @t = split //, $line;

my ($n, $m) = (scalar @sd, scalar @t);

unless ($m <= $n) {
  print "UNRESTORABLE\n";
  exit;
}

my @results;
NEXT: for (my $i = 0; $i < $n - $m + 1; $i++) {
  for (my $j = 0; $j < $m; $j++) {
    unless ($sd[$i + $j] eq $t[$j] || $sd[$i + $j] eq '?') {
      next NEXT;
    }
  }
  my @cand;
  for (my $k = 0; $k < $i; $k++) {
    push @cand, 'a' if $sd[$k] eq '?';
    push @cand, $sd[$k] unless $sd[$k] eq '?';
  }
  for (my $k = 0; $k < $m; $k++) {
    push @cand, $t[$k];
  }
  for (my $k = $i + $m; $k < $n; $k++) {
    push @cand, 'a' if $sd[$k] eq '?';
    push @cand, $sd[$k] unless $sd[$k] eq '?';
  }
  push @results, join('', @cand);
}

unless (scalar @results) {
  print "UNRESTORABLE\n";
  exit;
}

@results = sort @results;
print $results[0], "\n";


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

int main() {
	int N, y;
	cin >> N;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec.at(i);
	}
    int size,count;
	count = 0;
	sort(vec.begin(), vec.end());
	size = 0;
	for (int i = 0; i < N; i++) {
        y = vec.at(i);
		if (size == y) {
    		continue;
    	}
		else {
    		size = y;
        	count++;
    	}
	}
		cout << count << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repa(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define COUT(x) cout << (x) << endl
#define _GLIBCXX_DEBUG

int main(){
  
  string a, b, c;
  cin >> a >> b >> c;
  cout << (char)(a[0] - 32) << (char)(b[0] - 32) << (char)(c[0] - 32) << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<int, int>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

#include <deque>

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin, s;
    int q;
    cin, q;
    deque<char> deq;
    REP(i, 0, s.size()) {
        deq.push_back(s[i]);
    }
    int add = 0;
    REP(i, 0, q) {
        int t;
        cin, t;
        if (t == 1) {
            add = 1 - add;
        } else {
            int f;
            char c;
            cin, f, c;
            int pos = (add + f - 1) % 2;
            if (pos == 0) {
                deq.push_front(c);
            } else {
                deq.push_back(c);
            }
        }
    }
    if (add) {
        reverse(deq.begin(), deq.end());
    }
    for (auto &c : deq) {
        cout << c;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 976
package main

import "fmt"

func main() {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)

	max := 0
	for i := 0; i < n-1; i++ {
		count := 0
		alphabet := make([]int, 26)
		x := s[:i+1]
		y := s[i+1:]

		for j := range x {
			alphabet[x[j]-97] = 1
		}
		for j := range y {
			if alphabet[y[j]-97] == 1 {
				alphabet[y[j]-97] = 2
			}
		}
		for _, c := range alphabet {
			if c == 2 {
				count++
			}
		}
		if max < count {
			max = count
		}
	}
	fmt.Println(max)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll h;cin>>h;
    ll a;cin>>a;
    ans=(h+a-1)/a;
    cout<<ans<<endl;
}
int main(){
    Main();
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    map<ll, ll> mp;
    rep(i, 0, n) mp[a[i]]++;
    int q;
    cin >> q;
    ll ans = 0;
    rep(i, 0, n) ans += a[i];
    vector<ll> res;
    rep(i, 0, q){
        int b, c;
        cin >> b >> c;
        ans -= b*mp[b];
        mp[c] += mp[b];
        ans += c*mp[b];
        mp[b] = 0;
        res.push_back(ans);
    }
    for(ll i : res){
        cout << i << endl;
    }
    return 0;
}


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

bool b[100][100];
int memo[100][100];

int rev(vector<vector<char>> vv, int m, int n) {
  int H = vv.size();
  int W = vv.at(0).size();
  b[H-1][W-1] = true;
  memo[H-1][W-1] = 0;
  if (b[m][n]) return memo[m][n];
  else if (m == H-1) {
    int w = rev(vv, m, n+1);
    if (vv.at(m).at(n) != vv.at(m).at(n+1)) w++;
    b[m][n] = true;
    memo[m][n] = w;
    return w;
  }
  else if (n == W-1) {
    int h = rev(vv, m+1, n);
    if (vv.at(m).at(n) != vv.at(m+1).at(n)) h++;
    b[m][n] = true;
    memo[m][n] = h;
    return h;
  }
  else if (m < H-1 && n < W-1) {
    int w = rev(vv, m, n+1);
    int h = rev(vv, m+1, n);
    if (vv.at(m).at(n) != vv.at(m).at(n+1)) w++;
    if (vv.at(m).at(n) != vv.at(m+1).at(n)) h++;
    b[m][n] = true;
    memo[m][n] = min(h, w);
    return min(h,w);
  }
}

int main() {
  int H , W;
  cin >> H >> W;
  vector<vector<char>> vv (H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      char c ;
      cin >> c;
      vv.at(i).at(j) = c;
    }
  }
  int p = rev(vv, 0, 0);
  int ans;
  if (p % 2 == 1) ans = (p+1)/2;
  if (p % 2 == 0) {
    if (vv.at(0).at(0) == '.') {
      ans = p/2;
    }
    else {
      ans = p/2 + 1;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 2944
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ


		Scanner scan = new Scanner(System.in);
		int m=0;
		while(scan.hasNext()){
			String[] s = scan.next().split("[^0-9]+");
			for(String t: s){
				try{
				m+=Integer.parseInt(t);
				}
				catch(Exception e){
				}
			}
		}
		System.out.println(m);
	}

}

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

#define ALL(v) (v).begin(),(v).end()

using namespace std ;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;




int main()
{
  int n ;
  cin >> n ;
  
  if(n<=999) cout<<"ABC"<<endl ;
  else cout<<"ABD"<<endl ;
    return 0 ;
}

/*　吾輩はやれば出来る子である。 
　　　　∩∩ 
　　　（´･ω･） 
　　 ＿|　⊃／(＿＿_ 
　／　└-(＿＿＿_／ 
　￣￣￣￣￣￣￣ 
　やる気はまだない 

　　 ⊂⌒／ヽ-、＿_ 
　／⊂_/＿＿＿＿ ／ 
　￣￣￣￣￣￣￣　　*/

Measured memory_bytes: 256