akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rng(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(rng(a));
  ll sum = 0;
  int ans = 0;
  rep(i,n-1) {
    sum += a[i];
    if(sum*2 >= a[i+1]) ans++;
    else ans = 0;
  }
  ans ++;//a[n-1]は確定
  cout << ans << endl;
  return 0;
}

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

void input(string& rsColor)
{
  int nColorSiz;
  cin >> nColorSiz >> rsColor;
}

int calcColor(string sColor)
{
  int nColorCnt = 0;
  int nFwd = 0;

  while (nFwd < sColor.size() )
  {
    while ( nFwd < sColor.size() - 1   &&
            sColor[nFwd] == sColor[nFwd + 1] )
      ++nFwd;

    ++nColorCnt;
    ++nFwd;
  }
  return nColorCnt;
}

int main()
{
  string sColor;

  input(sColor);
  cout << calcColor(sColor) << endl;

  return 0;
}

Measured memory_bytes: 3844
import sys
import math

def main():
    a, b = [int(s) for s in sys.stdin.readline().strip().split()]

    def factorize(x):
        ret = set()
        for n in range(2, int(math.sqrt(x))+2):
            if x % n == 0:
                while x % n == 0:
                    x //= n
                ret.add(n)
        if x != 1:
            ret.add(x)
        return ret

    a_primes = factorize(a)
    b_primes = factorize(b)
    shared = a_primes.intersection(b_primes)
    print(len(shared) + 1)


main()


Measured memory_bytes: 38612
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> a(2, vector<int>(N, 0));
    REP(i, 2) {
        REP(j, N) { cin >> a[i][j]; }
    }
    //累積和
    //(first,end]
    vector<int> up(N + 1, 0);
    REP(i, N) { up[i + 1] = up[i] + a[0][i]; }
    vector<int> down(N + 1, 0);
    REP(i, N) { down[i + 1] = down[i] + a[1][i]; }
    vector<int> res(N, 0);
    REP(i, N) { res[i] = up[i + 1] - up[0] + down[N] - down[i]; }
    cout << *max_element(res.begin(), res.end()) << endl;
}

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

int main(){
	std::vector<int> a(4);
	std::vector<int> b(4);
	int hit_num;
	int blow_num;
	
	while(std::cin >> a[0] >> a[1] >> a[2] >> a[3]){
		std::cin >> b[0] >> b[1] >> b[2] >> b[3];
		hit_num = 0;
		blow_num = 0;
		for(int i = 0; i < 4; ++i){
			if(a[i] == b[i]) ++hit_num;
			for(int j = 0; j < 4; ++j){
				if(i != j && a[i] == b[j]) ++blow_num;
			}
		}
		std::cout << hit_num << " " << blow_num << std::endl;
	}
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
const int N = 5001,M = 1e9 + 7;
int n;
long long dp[N][N][2],temp[N][2],fact[N],sz[N],ans;
vector<int>g[N];
void add(long long &a,long long b){
	a+=b;
	if(a >= M)a-=M;
	if(a < 0)a+=M;
}
void calc(int u,int p){
	dp[u][1][0] = 1;
	sz[u] = 1;
	for(auto i : g[u])
		if(i != p){
			calc(i,u);
			for(int j = 0;j <= sz[u];j++)
				for(int k = 0;k < 2;k++)
					temp[j][k] = dp[u][j][k],
					dp[u][j][k] = 0;
			for(int j = 1;j <= sz[u];j++)
				for(int k = 1;k <= sz[i];k++)
					for(int a = 0;a < 2;a++)
						for(int b = 0;b < 2;b++){
							add(dp[u][j + k][a^b],temp[j][a]*1LL*dp[i][k][b]%M);
							if(!(k&1))add(dp[u][j][a^b^1],(temp[j][a]*1LL*dp[i][k][b]%M)*fact[k]%M);
						}
			sz[u]+=sz[i];
		}
}
int main(){
	//freopen("readin.txt","r",stdin);
	fact[0] = 1;
	scanf("%d",&n);
	for(int i = 2;i < N;i+=2)fact[i] = (i - 1LL)*fact[i - 2]%M;
	for(int i = 1,a,b;i < n;i++){
		scanf("%d%d",&a,&b);
		g[--a].push_back(--b);
		g[b].push_back(a);
	}		
	calc(0,-1);
	for(int i = 2;i <= n;i+=2)add(ans,fact[i]*1LL*(dp[0][i][0] - dp[0][i][1])%M);
	printf("%lld\n",ans);
}

Measured memory_bytes: 390016
import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

void main()
{
	auto hw = readln.split.map!( to!byte );
	auto s = new string[ hw[ 0 ] ];
	foreach( ref sl; s )
	{
		sl = readln.strip;
	}
	
	writeln( solve( hw[ 0 ], hw[ 1 ], s ) );
}

string solve( in byte h, in byte w, in string[] s )
{
	foreach( y; 0 .. h )
	{
		foreach( x; 0 .. w )
		{
			if( s[ y ][ x ] == '#' )
			{
				if( 0 <= y - 1 && s[ y - 1 ][ x ] == '#' ) continue;
				if( y + 1 < h && s[ y + 1 ][ x ] == '#' ) continue;
				if( 0 <= x - 1 && s[ y ][ x - 1 ] == '#' ) continue;
				if( x + 1 < w && s[ y ][ x + 1 ] == '#' ) continue;
				return "No";
			}
		}
	}
	
	return "Yes";
}

unittest
{
	assert( solve( 3, 3, [ ".#.", "###", ".#." ] ) == "Yes" );
	assert( solve( 5, 5, [ "#.#.#", ".#.#.", "#.#.#", ".#.#.", "#.#.#" ] ) == "No" );
	assert( solve( 11, 11, [ "...#####...", ".##.....##.", "#..##.##..#", "#..##.##..#", "#.........#", "#...###...#", ".#########.", ".#.#.#.#.#.", "##.#.#.#.##", "..##.#.##..", ".##..#..##." ] ) == "Yes" );
	assert( solve( 4, 3, [ "##.", ".##", "##.", ".##" ] ) == "Yes" );
}


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

int main(void){
  double r;
  double s, l;

  scanf("%lf", &r);
  s = r * r * M_PI;
  l = 2 * r * M_PI;
  printf("%.6lf %.6lf\n", s, l);
  return 0;
}



Measured memory_bytes: 2064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define BUF_SIZE 55

// size: specify sizeof(str)
int get_str(char *str, int size) {
    if(!fgets(str, size, stdin)) return -1;
    return 0;
}

#define UNKNOWN '?'

int compare(char *s, char *t, int len) {
    int i;
    int flag = 1;
    for(i = 0; i < len; i++) {
        if(s[i] == UNKNOWN) continue;
        if(s[i] != t[i]) {
            flag = 0;
            break;
        }
    }
    return flag;
}

int main(void) {
    char str[BUF_SIZE];
    char sub[BUF_SIZE];
    get_str(str, BUF_SIZE);
    get_str(sub, BUF_SIZE);
    int slen = strlen(str)-1;
    int tlen = strlen(sub)-1;
    int i, j;

    int flag = 0;
    for(i = slen-tlen; i >= 0; i--) {
        if(compare(&str[i], sub, tlen)) {
            flag = 1;
            memcpy(&str[i], sub, tlen);
            for(j = 0; j < slen; j++) {
                if(str[j] == UNKNOWN) str[j] = 'a';
            }
            break;
        }
    }
    printf("%s", flag ? str : "UNRESTORABLE\n");
    return 0;
}

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

int main() {
  
  int N; cin >> N; int64_t ans = 0;
  
  vector<int> vecA(N + 1); vector<int> vecB(N);
  
  for (int i = 0; i < N + 1; i++) cin >> vecA[i];
  
  for (int i = 0; i < N; i++) cin >> vecB[i];
  
  for (int i = 0; i < N; i++) {
    
    if (vecA[i] < vecB[i]) {
      
      ans += min(vecB[i], vecA[i] + vecA[i + 1]);
      
      vecA[i + 1] = max(0, vecA[i + 1] + vecA[i] - vecB[i]);
      
    }
    
    else ans += vecB[i];
    
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 1024
N = int(raw_input())
u = {}
for _ in xrange(N):
  u[raw_input()] = True
M = int(raw_input())
is_opened = False
for _ in xrange(M):
  key = raw_input()
  if key in u:
    if is_opened == True:
      print "Closed by %s" % (key)
      is_opened = False
    else:
      print "Opened by %s" % (key)
      is_opened = True
  else:
    print "Unknown %s" % (key)

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

int main() {
  int n, k;
  cin >> n >> k;

  vector<bool> v(n, false);
  for (int i = 0; i < k; i++) {
    int d;
    cin >> d;
    for (int j = 0; j < d; j++) {
      int a;
      cin >> a;
      v.at(a-1) = true;
    }
  }
  
  int ans = 0;
  for (auto x:v) {
    if (x == false) ans++;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 3608
def main():
    import collections
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    N=int(input())
    A=list(map(int,input().split()))
    Q=int(input())
    BC=[list(map(int,input().split())) for _ in range(Q)]
    answer=sum(A)
    c=collections.Counter(A)
    for x in BC:
        B=x[0]
        C=x[1]
        if B in c.keys():
            n=c[B]
            answer=answer-(B-C)*n
            c[B]=0
            c[C]=c[C]+n
        print(answer)



if __name__ == '__main__':
    main()

Measured memory_bytes: 36320
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <climits>
#include <memory>
#include <sstream>
#include <iomanip>
#include <cstdio>

using namespace std;

int main() {

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

	int n, m, c;
	cin >> n >> m >> c;
	vector<int> b(m);
	int ans = 0;
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n;i++) {
		int tmp = 0;
		for (int j = 0; j < m;j++) {
			int a;
			cin >> a;
			tmp += a * b[j];
		}
		if (tmp + c > 0)ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
S = input()

flag = True
odd_conds = ["R", "U", "D"]
even_conds = ["L", "U", "D"]
for i, c in enumerate(S):
    j = i+1
    if j %  2 == 0 and c in even_conds:
        pass
    elif j % 2 == 1 and c in odd_conds:
        pass
    else:
        flag = False
        break

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

Measured memory_bytes: 3064
# ABC115 C - Christmas Eve
import numpy as np
N,K = map(int,input().split())
H = [int(input()) for _ in range(N)]

ans = 10**10
H.sort()

for i in range(N-K+1):
    t = H[i+K-1] - H[i]
    ans = min(ans,t)
print(ans)

Measured memory_bytes: 16724
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
int main() {
	int d;
	cin >> d;
	if (d == 25) {
		cout << "Christmas" << endl;
	}
	else if (d == 24) {
		cout << "Christmas Eve" << endl;
	}
	else if (d == 23) {
		cout << "Christmas Eve Eve" << endl;
	}
	else {
		cout << "Christmas Eve Eve Eve" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;

long func(vector<long>* a,long m){
  long sum = 0;
  long ii;
  for(auto val:*a){
	sum += m % val;
  }
  return sum;
}

int main(){
  long ii,jj,n;
  vector<long> a;
  long max = 0;
  long sum;
  cin >> n;
  a.resize(n);
  sum = 0;
  for(ii=0;ii<n;ii++){
	cin >> a[ii];
	sum += a[ii];
  }
  sum -= n;
  cout << sum << endl;
//  for(ii=00000;ii<400000000;ii++){
//	sum =func(&a,ii);
//
//	if(sum > max){
//	  cout << "ii:" << ii << "sum:" << sum << endl;
//	  max = sum;
//	}
//  }
//  cout << max << endl;
  return 0;
}


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

int main(void){
    int a,b;

    scanf("%d %d",&a,&b);
    if(a+b==15) printf("+\n");
    else if(a*b==15) printf("*\n");
    else printf("x\n");
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
const int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const string dir8[8] = {"U", "RU", "R", "RD", "D", "LD", "L", "LU"};

// Self settings
// clang-format off
#define MAX_N 100000
#define MAX 100000
#define INFTY (1<<30)
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1000100011;
class Point { public: double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} Point operator+(Point p) { return Point(x + p.x, y + p.y); } Point operator-(Point p) { return Point(x - p.x, y - p.y); } Point operator*(double a) { return Point(a * x, a * y); } Point operator/(double a) { return Point(x / a, y / a); } double abs() { return sqrt(norm()); } double norm() { return x * x + y * y; } bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; } bool operator==(const Point& p) const { return fabs(x - p.y) < EPS && fabs(y - p.y) < EPS; } };
typedef Point Vector;
double norm(Vector a) { return a.x * a.x + a.y * a.y; }
double abs(Vector a) { return sqrt(norm(a));}
double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
struct Segment { Point p1, p2; };
typedef Segment Line;
// clang-format on

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

  ll ans = 0;
  ans += (X / 500) * 1000;
  X %= 500;
  ans += (X / 5) * 5;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long  LL;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define F first
#define S second
inline int read(){
	int x = 0; char ch = getchar(); bool positive = 1;
	for (; !isdigit(ch); ch = getchar())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
#include<string>
string s;
int dp[1<<26],sum,oo=10000005;
int main(){
	cin>>s;
	for(int i=1;i<(1<<26);i++)dp[i]=oo;
	for(int i=0;i<s.length();i++){
		sum^=1<<(s[i]-'a');
		for(int j=0;j<26;j++)dp[sum]=min(dp[sum],dp[sum^(1<<j)]+1);
	}
	if(sum==0)writeln(1); else writeln(dp[sum]);
}

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

void fnInput(int& rnLimit, vector<llong>& rvnCostA, vector<llong>& rvnCostB)
{
  int nCostASiz, nCostBSiz;
  cin >> nCostASiz >> nCostBSiz >> rnLimit;
  rvnCostA.resize(nCostASiz + 1);
  rvnCostB.resize(nCostBSiz + 1);

  for (int i = 1; i < rvnCostA.size(); i++)
  {
    int nOneCost;
    cin >> nOneCost;
    rvnCostA[i] = rvnCostA[i - 1] + nOneCost;
  }

  for (int i = 1; i < rvnCostB.size(); i++)
  {
    int nOneCost;
    cin >> nOneCost;
    rvnCostB[i] = rvnCostB[i - 1] + nOneCost;
  }
}

int fnMaxSelCnt(int nLimit, const vector<llong>& cnrvnCostA, 
                            const vector<llong>& cnrvnCostB)
{
  int nMaxSelCnt = 0;
  int nBgnB = cnrvnCostB.size() - 1;
  int nixA = 0;

  while (nixA < cnrvnCostA.size()  &&
         cnrvnCostA[nixA] <= nLimit   )
  {
    int nixB = nBgnB;

    while (cnrvnCostB[nixB] > nLimit - cnrvnCostA[nixA])
      nixB--;

    nMaxSelCnt = max(nMaxSelCnt, nixA + nixB);
    nBgnB = nixB;

    nixA++;
  }
  return nMaxSelCnt;
}
 
int main()
{
  int nLimit;
  vector<llong> vnCostA, vnCostB;

  fnInput(nLimit, vnCostA, vnCostB);
  cout << fnMaxSelCnt(nLimit, vnCostA, vnCostB) << endl;

  return 0;
}

Measured memory_bytes: 6404
#include <iostream>

using namespace std;

int main(){
	int n,a,b;
	while(cin >> n,n){
		int ta=0,tb=0;
		while(n--){
			cin >> a >> b;
			if(a>b)ta+=(a+b);
			else if(b>a)tb+=(a+b);
			else{
				ta+=a;tb+=b;
			}
		}
		cout << ta <<" "<< tb << endl;
	}
	return 0;
}

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
#include<fstream>
#include <set>
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
const int  MAXN =5e5+10;
const int mod = 1e9 + 7;
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf= 0x3f3f3f3f;
#define eps 1e-8
#define PI 3.1415926535898
#define lowbit(x) (x&(-x))
using namespace std ;
//getline(cin,s);
//set<ll>::iterator it;
//map<int,int>::iterator it;
typedef long long ll;
//费马小的逆元 容斥定理组合数  
ll fac[MAXN],inv[MAXN];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll C(int n,int m)
{
	return fac[m]*inv[m-n]%mod*inv[n]%mod;
}
ll A(int n,int m)
{
	return fac[m]*inv[m-n]%mod;
}
int main()
{
	int n,m;
	ll ans=0;
	scanf("%d %d",&n,&m);
	fac[0]=1; 
	for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;
	inv[m]=qpow(fac[m],mod-2);//逆元
	for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=0;i<=n;i++)
	{
		ll sum=C(i,n)*A(n-i,m-i)%mod;
		if(i&1) ans=((ans-sum)%mod+mod)%mod;
		else  ans=((ans+sum)%mod+mod)%mod;
	}
//	ans=(ans%mod+mod)%mod;
	printf("%lld\n",(ans*A(n,m))%mod); 
	return 0;
}

Measured memory_bytes: 11552
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
	int R;
	cin >> R;
	if (R < 1200)
	{
		cout << "ABC";
	}
	else if (R < 2800)
	{
		cout << "ARC";
	}
	else
	{
		cout << "AGC";
	}
	cout << endl;
	return 0;
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node *Node;

void insert(int);
void Inorder(Node);
void Preorder(Node);
Node find(int);
void delete(int);
Node successor(Node);
Node minimum(Node);

Node root;

int main(){
  char s[10];
  int k, n, i;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%s", s);

    if(s[0] == 'i'){
      scanf("%d", &k);
      insert(k);
    }
    else if(s[0] == 'f'){
      scanf("%d", &k);
      printf(find(k) == NULL ? "no\n" : "yes\n");
    }
    else if(s[0] == 'd'){
      scanf("%d", &k);
      delete(k);
    }
    else{
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }
  }
  
  return 0;
}

void insert(int k){
  Node z, x = root, y = NULL;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NULL;
  z->right = NULL;

  while(x != NULL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;

  if(y == NULL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}

void Inorder(Node u){
  if(u == NULL) return;
  Inorder(u->left);
  printf(" %d", u->key);
  Inorder(u->right);
}

void Preorder(Node u){
  if(u == NULL) return;
  printf(" %d", u->key);
  Preorder(u->left);
  Preorder(u->right);
}

Node find(int k){
  Node x = root;

  while(x != NULL){
    if(k == x->key)
      return x;
    else if(k < x->key)
      x = x->left;
    else
      x = x->right;
  }
  return NULL;
}

void delete(int k){
  Node z, x, y;

  z = find(k);

  if(z->left == NULL || z->right == NULL) y = z;
  else y = successor(z);

  if(y->left != NULL) x = y->left;
  else x = y->right;

  if(x != NULL) x->parent = y->parent;

  if(y->parent == NULL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;

  if(y != z) z->key = y->key;
}

Node successor(Node x){
  Node y;
  
  if(x->right != NULL) return minimum(x->right);

  y = x->parent;
  while(y != NULL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

Node minimum(Node x){
  while(x->left != NULL) x = x->left;
  return x;
}

Measured memory_bytes: 19352
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<pair<long,long>> data(N);
  for(int i = 0; i < N; i++){
    cin >> data.at(i).second >> data.at(i).first;
  }
  sort(data.begin(), data.end());
  long amari = data.at(0).first - data.at(0).second;
  if(amari < 0){
    cout << "No" << endl;
    return 0;
  }
  int flag = 1;
  for(int i = 0; i < N - 1; i++){
    amari = (data.at(i + 1).first - data.at(i).first + amari) - data.at(i + 1).second;
    if(amari < 0){
      flag = 0;
      break;
    }
  }
  if(flag == 0)cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3328
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC098A
{
    class Program
    {
        static void Main(string[] args)
        {
            int A, B,x,y,z,a;
            var word = Console.ReadLine().Split(' ');
            A = int.Parse(word[0]);
            B = int.Parse(word[1]);
            x = A + B;
            y = A - B;
            z = A * B;
            if (x >= y && x >= z)
                a = x;
            else if (x <= y && y >= z)
                a = y;
            else
                a = z;
            Console.WriteLine(a);
            Console.ReadKey();


        }
    }
}


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

using namespace std;
typedef long long LL;

int main(){
  int N;
  cin >> N;
  string s[100010];
  for(int i=0; i<N; i++) cin >> s[i];
  for(int i=0; i<N; i++) sort(s[i].begin(),s[i].end());
  sort(s,s+N);
  s[N]="";
  LL ans=0, same=0;
  for(int i=0; i<N; i++){
    same++;
    if(s[i]!=s[i+1]){
      ans+=same*(same-1)/2;
      same=0;
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 7296
#include <iostream>
using namespace std;
int main(void){
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  
  if (m1 != m2){
  cout << "1" << endl;
  }
  else{
  cout << "0" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class E
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		int T = GetInt();
		int[] A = new int[N];
		int[] B = new int[N];
		for(int i = 0; i < N; i++)
		{
			A[i] = GetInt();
			B[i] = GetInt();
		}

		int[,] dp1 = new int[N + 2, T];
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < T; j++)
			{
				chmax(ref dp1[i + 1, j], dp1[i, j]);
				if(j + A[i] < T)
					chmax(ref dp1[i + 1, j + A[i]], dp1[i, j] + B[i]);
			}
		}

		int[,] dp2 = new int[N + 2, T];
		for(int i = N - 1; i >= 0; i--)
		{
			for(int j = 0; j < T; j++)
			{
				chmax(ref dp2[i + 1, j], dp2[i + 2, j]);
				if(j + A[i] < T)
					chmax(ref dp2[i + 1, j + A[i]], dp2[i + 2, j] + B[i]);
			}
		}

		int ans = 0;
		for(int i = 1; i <= N; i++)
		{
			for(int j = 0; j < T; j++)
				chmax(ref ans, dp1[i - 1, j] + dp2[i + 1, T - 1 - j] + B[i - 1]);
		}
		WriteLine(ans);
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 81240
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <map>
using namespace std;
#define REP(i, n) for(int i = 0; i <= n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define INF 1e10
typedef long long ll;
typedef long double ld;
int main(){
    int cnt=0;
    int k,s; cin>>k>>s;
    REP(x,k)REP(y,k){
        int z=s-x-y;
        if(0<=z && z<=k)cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


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

int main() {
  int k, x;
  cin >> k >> x;
  if (k * 500 >= x) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3532
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    cin >> a >> b;
    if(0<=a&&a<=5){
        cout << 0 << endl;
    }
    else if(6<=a&&a<=12){
        cout << b/2 << endl;
    }
    else{
        cout << b << endl;
    }
}

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

const int N = 2e5 + 5;

int dp[N][2];
string s, one[N], two[N];

signed main() {
	cin >> s;
	int n = s.size();
	string pre;
	dp[0][0] = 1;
	one[0] = s[0];
	for (int i = 1; i < n; i++) {
		if (one[i - 1][0] != s[i]) {
			if (dp[i][0] < dp[i - 1][0] + 1) {
				dp[i][0] = dp[i - 1][0] + 1;
				one[i] += s[i];
			}
		}
		if (dp[i][0] < dp[i - 1][1] + 1) {
			dp[i][0] = dp[i - 1][1] + 1;
			one[i] += s[i];
		}
		if (i == 1) continue;
		if (dp[i][1] < dp[i - 2][0] + 1) {
			dp[i][1] = dp[i - 2][0] + 1;
			two[i] += s[i - 1];
			two[i] += s[i];
		}
		if (two[i - 2][0] != s[i - 1] && two[i - 2][1] != s[i]) {
			if (dp[i][1] < dp[i - 2][1] + 1) {
				dp[i][1] = dp[i - 2][1] + 1;
				two[i] += s[i - 1];
				two[i] += s[i];
			}
		}
	}
	cout << max(dp[n - 1][0], dp[n - 1][1]);
}

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    bool f = true;
    while (a > 0 && c > 0) {
        c -= b;
        if (c <= 0) break;

        a -= d;
        if (a <= 0) {
            f = false;
            break;
        }
    }
    cout << (f ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 3640
import numpy as np
 
H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)
DP = np.zeros(H+1)

for i in range(1,H+1):
    DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)
    
print(int(DP[-1]))

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

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)


void solve(long long a, long long b, long long c, long long d, long long e, long long k){
    if(e-a<=k){
        cout << "Yay!" << endl;
    }
    else{
        cout << ":(" << endl;
    }
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    long long d;
    scanf("%lld",&d);
    long long e;
    scanf("%lld",&e);
    long long k;
    scanf("%lld",&k);
    solve(a, b, c, d, e, k);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
 
int main(){
  int a,b,c,d,e,f;
  float x,y;
  while(scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)!=-1){
    x = (float)(c*e-b*f)/(a*e-d*b);
    y = (float)(c*d-a*f)/(b*d-a*e);
    if(-0.0005<x && x<=0)
      x=0;
    if(-0.0005<y && y<=0)
      y=0;
    printf("%.3f %.3f\n",x,y);
  }
  return 0;
}

Measured memory_bytes: 1748
#include <stdio.h>

void Tenka(int N) {
  char S[N];
  int K, i;
  scanf("%s%d",S,&K);
  for (i = 0; i < N; i++) {
    if (S[i] != S[K-1]) {
      S[i] = '*';
    }
  }
  printf("%s",S);
}

int main(void) {
  int N;
  scanf("%d",&N);
  Tenka(N);
  return 0;
}

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

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<char>> table(H, vector<char>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> table.at(i).at(j);
        }
    }

    for (int i = 0; i < H; i++) {
        bool shift = true;

        for (int j = 0; j < W; j++) {
            if (table.at(i).at(j) != '.') {
                shift = false;
                break;
            }
        }

        if (shift) {
            for (int j = i; j < H - 1; j++) {
                for (int k = 0; k < W; k++) {
                    table.at(j).at(k) = table.at(j + 1).at(k);
                }
            }
            i--;
            H--;
        }
    }

    for (int i = 0; i < W; i++) {
        bool shift = true;

        for (int j = 0; j < H; j++) {
            if (table.at(j).at(i) != '.') {
                shift = false;
                break;
            }
        }

        if (shift) {
            for (int j = i; j < W - 1; j++) {
                for (int k = 0; k < H; k++) {
                    table.at(k).at(j) = table.at(k).at(j + 1);
                }
            }
            i--;
            W--;
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << table.at(i).at(j);
        }
        cout << endl;
    }
}

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

int dfs(int x,int y);
int w,h;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int sum=1;
char maps[21][21];

int main(){
  int sx,sy;
  while(1){
    cin >> w >> h;
    if(w==0 && h==0) break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> maps[i][j];
	if(maps[i][j]=='@'){
	  sy=i;
	  sx=j;
	}
      }
    }
    
    dfs(sx,sy);
    cout << sum << endl;
    sum=1;
  }
  return(0);
}

int dfs(int x,int y){
  int nx,ny;
  for(int i=0;i<4;i++){
    nx=x+dx[i];
    ny=y+dy[i];
    maps[y][x]='#';
    if(0<=nx && nx<w && 0<=ny && ny<h && maps[ny][nx]!='#'){
      dfs(nx,ny);
      sum++;
    } 
  }
  return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

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...));
}

int main() {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        int s = 0;
        REP(i, n) {
                cin >> a[i];
                s += a[i];
        }

        int c = 0;
        REP(i, n) {
                if (a[i] * 4 * m >= s) c++;
        }

        if (c >= m) {
                cout << "Yes" << endl;
        } else {
                cout << "No" << endl;
        }

        return 0;
}


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

int main()
{

	int n;
	double inp,tot = 0;

	cin>>n;

	for(int i=0;i<n;++i)
	{
		cin>>inp;
		tot += 1/inp;
	}

	cout<<setprecision(9)<<1/tot<<"\n";

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;

int main(){
    int N,M;
    cin >> N >> M;
    vector<bool> a(N,true);
    for(int i = 0;i < M;++i){
        int b;
        cin >> b;
        a[b-1] = false;
    }
    vector<long long int> dp(N+2);
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2;i < N+2;++i){
        if(a[i-2]){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= mod;
        }
    }
    cout << dp[N+1] % mod << endl;
}

Measured memory_bytes: 1024
n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
count = r*g*b
for i in range(n):
    for d in range(n):
        j = i+d
        k = j+d
        if k >= n: 
            break
        if s[i]!=s[j] and s[j]!=s[k] and s[k] != s[i]: 
            count -= 1
            
print(count)

Measured memory_bytes: 9208
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll ai,a[225816],z[225816],e[225816],o[225816],pql[225816];
priority_queue<P, vector<P>, greater<P> > pqr;

int main(void){
	int n,i;
	ll t=0ll,l,r,ans=INFLL;
	P p;
	cin >> n;
	for(i=0; i<n; ++i){
		z[i+1] = z[i];
		e[i+1] = e[i];
		o[i+1] = o[i];
		cin >> a[i+1];
		if(!a[i+1]){
			++z[i+1];
		}else if(a[i+1]%2){
			++o[i+1];
		}else{
			++e[i+1];
		}
		a[i+1] += a[i];
	}
	for(i=1; i<=n; ++i){
		pqr.push(P(o[i]+z[i]*2+a[n]-a[i],i));
		ai = a[i]-a[i-1];
		if(!ai){
			pql[i] = pql[i-1] + 2;
		}else if(ai%2){
			pql[i] = pql[i-1] + 1;
		}else{
			pql[i] = pql[i-1];
		}
		pql[i] -= ((z[i]+e[i])-(z[i-1]+e[i-1]));
		pql[i] = min(pql[i],a[i]-(z[i]+e[i]));
	}
	for(i=0; i<=n; ++i){
		if(i){
			pql[i] = min(pql[i],pql[i-1]);
		}
		l = pql[i]+(z[i]+e[i]);
		while(true){
			if(i==n){
				r = 0ll;
				break;
			}
			p = pqr.top();
			if(p.second<i){
				pqr.pop();
			}else{
				r = p.first-(o[i]+z[i]*2);
				break;
			}
		}
		ans = min(ans,l+r);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 14448
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int r, d, x;

    cin >> r >> d >> x;

    for (int i = 0; i < 10; i++)
    {
        x = r * x - d;

        cout << x << endl;
    }
}

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

int mod = 1000000007;
int64_t large = 9223372036854775807;

int main()
{
    int A, B;
    cin >> A >> B;
    if(A>=13)
        cout << B;
    else if (A >= 6)
        cout << B / 2;
    else
        cout << 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    string s;
    cin >> s;
    sort(all(s));
    fp((s[0] == s[1])&&(s[2] == s[3])&&(s[1] != s[2]));
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define P pair<int,int>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
template<class T> inline bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }

class UnionFind{
public:
  vector<ll> parent;  //parent[i]はiの親
  vector<ll> siz;  //素集合のサイズを表す配列(1で初期化)
  UnionFind(ll n) : parent(n), siz(n,1){ rep(i,n) parent[i] = i; } //コンストラクタ  //全ての要素の根が自身であるとして初期化
  ll root(ll x){ //データxの属する木の根を取得(経路圧縮も行う)
    if(parent[x] == x) return x;
    return parent[x] = root(parent[x]);  //代入式の値は代入した変数の値なので、経路圧縮できる
  }
  void unite(ll x,ll y){ //xとyの木を併合
    ll rx = root(x);  //xの根
    ll ry = root(y);  //yの根
    if(rx == ry) return;  //同じ木にある時
    if(siz[rx] < siz[ry]) swap(rx,ry);
    siz[rx] += siz[ry];  //小さい集合を大きい集合へと併合(ry→rxへ併合)
    parent[ry] = rx;  //xとyが同じ木にない時はyの根ryをxの根rxにつける
  }
  bool same(ll x,ll y){ return root(x) == root(y); } //xとyが属する木が同じかを判定
  ll size(ll x){ return siz[root(x)]; } //xの素集合のサイズを取得
};

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n,m; cin >> n >> m;
  UnionFind uf(n);
  rep(i,m){
    int a,b; cin >> a >> b;
    --a; --b;
    uf.unite(a,b);
  }
  set<int> r;
  rep(i,n) r.insert(uf.root(i));
  cout << r.size()-1;
  cout << endl;
  return 0;
}


Measured memory_bytes: 8412
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <fstream>
#include <cassert>
#include <unordered_map>
#include <cstring>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;

int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	set<int> s;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		s.insert(x);
	}
	cout << (s.size() == n ? "YES" : "NO");
}



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

int n;
int a[50];

int slove(int i,int m){
  if(m==0)return 1;
  if(i>=n)return 0;
  int res=slove(i+1,m)||slove(i+1,m-a[i]);
  return res;
}


int main(){
  cin>>n;
  rep(i,n)cin>>a[i];
  int q;
  cin>>q;
  int b;

  rep(j,q){
    cin>>b;
    int ans=slove(0,b);
    if(ans)cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
  
  return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define pb push_back
#define ld long double
typedef pair<ll,ll> P;
#define boost ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
int main()
{
    ll n,i;
    cin>>n;
    ll A[n];
    ll DP[n];
    DP[0]=0;
    for(i=0;i<n;i++)
    cin>>A[i];
    DP[1]=abs(A[1]-A[0]);
    for(i=2;i<=n;i++)
    {
        DP[i]=min(DP[i-1]+abs(A[i]-A[i-1]),DP[i-2]+abs(A[i]-A[i-2]));
    }
    cout<<DP[n-1]<<endl;
}


Measured memory_bytes: 1792
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


# つながってないところに辺を張る
# 二部グラフになるか
N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

edges = set()
for a, b in AB:
    a -= 1
    b -= 1
    edges.add((a, b))
    edges.add((b, a))

graph = [[] for _ in range(N)]
for a, b in itertools.combinations(range(N), r=2):
    if (a, b) not in edges:
        graph[a].append(b)
        graph[b].append(a)

ok = True
pairs = []
seen = [False] * N
for v in range(N):
    if seen[v]:
        continue
    evens = {v}
    odds = set()
    stack = [(v, True)]
    while stack:
        v, v_is_even = stack.pop()
        next_set = odds if v_is_even else evens
        for u in graph[v]:
            if u in next_set:
                continue
            next_set.add(u)
            stack.append((u, not v_is_even))
    if len(evens) + len(odds) != len(evens | odds):
        ok = False
        break
    pairs.append((len(evens), len(odds)))
    for v in evens:
        seen[v] = True
    for v in odds:
        seen[v] = True

# 二部グラフじゃないのが混じってた。ダメ
if not ok:
    print(-1)
    exit()
# pairs をどう分割するか
# どっちかを選んで作れる数を列挙する
can_make = [[False] * (N + 1) for _ in range(len(pairs) + 1)]
can_make[0][0] = True
for pi, (a, b) in enumerate(pairs):
    for i in range(N + 1):
        if can_make[pi][i]:
            can_make[pi + 1][i + a] |= True
            can_make[pi + 1][i + b] |= True

ans = INF
for n in range(len(can_make[-1])):
    if can_make[-1][n]:
        m = N - n
        a = m * (m - 1) // 2
        b = n * (n - 1) // 2
        ans = min(ans, a + b)
print(ans)


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

#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define EPS (1e-7)
#define INF 1e18

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
int vx[]={0,1,0,-1};
int vy[]={1,0,-1,0};

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

const ll mod=1e9+7;
const int MAX_N=300;

int main(){
	int n;
	ll z,w;
	cin>>n>>z>>w;
	ll a[n];
	REP(i,n)cin>>a[i];
	if(n>2 && abs(a[n-1]-w)<abs(a[n-1]-a[n-2])){
		cout<<abs(a[n-1]-a[n-2])<<endl;
	}else{
		cout<<abs(a[n-1]-w)<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

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

  rep(i, 12) {
    cout << s[i];
    if (i==3) cout << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
// D - Wizard in Maze
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(int)(s);i<(int)(e);++i)

// ダイクストラ　O(ElogV)
using PR = pair<int, int>;
#define INF 1'000'000'000
vector<vector<PR>> G; // [from]<to, cost> 隣接リスト
int V; // 頂点数(max:10^3*10^3=10^6)

vi dijkstra(int s){
	vi dist(V, INF);
	dist[s] = 0;
	priority_queue<PR, vector<PR>, greater<PR>> pq; // <dist, u>
	pq.push({0, s});
	while(pq.size()){
		int d, u; tie(d, u) = pq.top(); pq.pop();
		if(dist[u] < d) continue;
		for(auto e:G[u]){
			int v = e.first, next_d = e.second + dist[u];
			if(dist[v] <= next_d) continue;
			dist[v] = next_d;
			pq.push({dist[v], v});
		}
	}
	return dist;
}

int main(){
	int H, W, sh, sw, eh, ew; cin>>H>>W>>sh>>sw>>eh>>ew;
	string S[H]; rp(i, 0, H) cin>>S[i];

	int dh[] = { 1,-1, 0, 0};
	int dw[] = { 0, 0,-1, 1};
	V = H * W;
	G.resize(V); // 隣接リスト初期化
	rp(u, 0, V){
		int h = u / W, w = u % W;
		rp(i, 0, 4){
			int nx_h = h + dh[i], nx_w = w + dw[i];
			if(nx_h < 0 || H <= nx_h || nx_w < 0 || W <= nx_w) continue;
			if(S[nx_h][nx_w] == '#') continue;
			G[u].emplace_back(nx_h*W + nx_w, 0);
		}
		rp(i, -2, 2+1) rp(j, -2, 2+1){ //[i, j]: [-2,-2]~[2,2]
			if(i*i + j*j <= 1) continue; // 上下左右を除く
			int nx_h = h + i, nx_w = w + j;
			if(nx_h < 0 || H <= nx_h || nx_w < 0 || W <= nx_w) continue;
			if(S[nx_h][nx_w] == '#') continue;
			G[u].emplace_back(nx_h*W + nx_w, 1);
		}
	}

	int ans = dijkstra((sh-1)*W + (sw-1))[(eh-1)*W + (ew-1)];
	cout<< (ans==INF? -1:ans) <<endl;
}


Measured memory_bytes: 172300
N, T = map(int, input().split())
c_arr = []
t_arr = []
for _ in range(N):
  c, t = map(int, input().split())
  c_arr.append(c)
  t_arr.append(t)

min_c = c_arr[0]
flag = False
for i, v in enumerate(t_arr):
  if v <= T:
    flag = True
    min_c = min(min_c, c_arr[i])

if flag:
  print(min_c)
else:
  print('TLE')


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
typedef unsigned int uint;
typedef long long llong;
using namespace std;

int main(void) {
    cin.tie(0);

    int A , B;
    cin >> A >> B;

    if(B % A == 0) {
        cout << A+B;
    } else {
        cout << B - A;
    }

    return 0;
}

Measured memory_bytes: 256
M=998244353;n,A,B,K=map(int,input().split());F=[1];a=0
for i in range(n):F+=[F[-1]*(n-i)*pow(i+1,M-2,M)%M]
for i in range(n+1):
 r=K-i*A
 if(r%B==0)&(0<=r//B<=n):a+=F[i]*F[r//B]
print(a%M)

Measured memory_bytes: 73500
#include <bits/stdc++.h>
#define inf 1000000005
#define mod 1000000007
#define eps 1e-10
#define rep(i,n) for(int i = 0; i < (n); ++i) /*0からn-1までのrepeat*/
#define rrep(i,n) for(int i = 1; i <= (n); ++i) /*1からnまでのrepeat*/
#define drep(i,n) for(int i = (n)-1; i >= 0; --i) /*n-1から0までのrepeat*/
#define srep(i,s,t) for (int i = s; i < t; ++i) /*sからt-1までのrepeat*/
#define isin(x,l,r) ((l) <= (x) && (x) < (r)) /*l以上r未満のx*/
#define each(a,b) for(auto& (a): (b)) /*よくわからん*/
#define pct __builtin_popcountll /*1bitの数*/
#define all(a) a.begin(),a.end() /*範囲*/
#define sz(v) (int)(v).size() /*大きさ*/
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) /*重複削除*/
#define cmx(x,y) x=max(x,y) /*最大*/
#define cmn(x,y) x=min(x,y) /*最小*/
#define rev(v) reverse((v).begin(),(v).end()); /*逆順*/
#define so(v) sort((v).begin(), (v).end()); /*ソート*/
#define yn {puts("Yes");}else{puts("No");} /*はい・いいえ*/
#define dame { puts("-1"); return 0;}/*だめ*/
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using namespace std;

using ll = long long;
using unit = unsigned;
using ull = unsigned long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vp = vector<P>;
using vt = vector<T>;
using vs = vector<string>;

int main() {
    string a;
    cin >> a;
    int ct=0;
    int b = sz(a);
    rep(i,b) {
        if (a.at(i) == 'x') {
            ct++;
        }
    }
    if (ct < 8) {
        cout<<"YES"<<endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
using System;
class Program{
	static void Main(){
		int[] s=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		long[] x=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
		long ans=0;
		for(int i=0;i<s[0]-1;i++){
			if((x[i+1]-x[i])*s[1]>s[2]){ans+=s[2];}
			else{ans+=(x[i+1]-x[i])*s[1];}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 18912