akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>//printf("%.*f\n",*********);
#include<vector>//s.erase(n),vector
#include<algorithm>//next_permutation
#include<set>
#include<string>//char('a'=32+'A')
                //to_string,string,substr
#include<sstream>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>//min,max
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)//start==1
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)//end==1
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(a,n) rep(i,n)cin>>a[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//昇順
#define reve(s) reverse(s.begin(),s.end())//反転
#define please return
#define AC 0
#define rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define pi 3.1415926535897932384626//pi
#define nine 1000000000//10^9

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef vector<double> vdouble;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int KETA(int n) { //Sum of Each Digit
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

unsigned ND(unsigned num) {//Number of Digits
	return std::to_string(num).length();//outmax=10
}

bool KIBN(string s) {
	rep(i, s.size() / 2) {
		if (s[i] != s[s.size() - 1 - i])return false;
	}
	return true;
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */


int main(void) {
	rapid_pleaseAC_fast;

	string s;
	cin >> s;
	int cnt = 0;
	rep(i, 4) {
		if (s[i] == '2') {
			cnt++;
		}
	}
	cout << cnt << rt;

	please AC;
}
//参考：---

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<61);

using namespace std;

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n, a, b; cin >> n >> a >> b;
    ll k = n/(a + b);
    n -= k * (a + b);
    ll ans = k * a + min(n, a);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000 + 100
#define ll long long int
ll N[MAXN];
ll w[200];
ll v[200];
ll n;
ll max_V;
int main()
{
    cin>>n>>max_V;
    for(int i = 0;i < n;++i)
        cin>>v[i]>>w[i];
    for(int i = 0;i < n;++i)
        for(int j = max_V;j >= v[i];--j)
            N[j] = max(N[j], N[j - v[i]] + w[i]);
    cout<<N[max_V]<<endl;

    return 0;
}


//12

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
  if(a>b){
  for(int i = 1; i <= a; i++){
       cout<<b;
  }
  }
  else{
     for(int i = 1; i <= b; i++){
       cout<<a;
  }
  }
    cout<<endl;
        return 0;
}


Measured memory_bytes: 256
// 別解
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int W,H,N;
  cin>>W>>H>>N;
  
  int xmax=W;
  int xmin=0;
  int ymax=H;
  int ymin=0;
 
  for(int i=0;i<N;++i){
    int x,y,a;
    cin>>x>>y>>a;
    
    if(a==1){
      if(xmin<=x)
        xmin=x;
    }
    
    if(a==2){
      if(x<=xmax)
        xmax=x;
    }
    
    if(a==3){
      if(ymin<=y)
        ymin=y;
    }
    
    if(a==4){
      if(y<=ymax)
        ymax=y;
    }
  }
  
  int yoko=xmax-xmin;
  int tate=ymax-ymin;
  
  if(yoko<=0 || tate<=0)
    cout<<0<<endl;
  else
    cout<<tate*yoko<<endl;
}


Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Osa_k():
    def __init__(self, n):
        self.sieve = list(range(n + 1))
        self.sieve[0] = 1 #素数でない
        self.sieve[1] = 1 #素数でない
        m = int(math.sqrt(n))
        for i in range(2, m + 1):
            if self.sieve[i] < i:
                continue
            for j in range(i * i, n + 1, i):
                if self.sieve[j] == j:
                    self.sieve[j] = i

    def factorize(self, n):
        prime = defaultdict(int)
        if n == 0 or n == 1:
            return (n, 1)
        opt = n
        while opt > 1:
            prime[self.sieve[opt]] += 1
            opt //= self.sieve[opt]
        return sorted(prime.items())

N = getN()
O = Osa_k(10 ** 6 + 1)

prime = defaultdict(int)
for i in range(2, N + 1):
    for j in O.factorize(i):
        prime[j[0]] += j[1]

ans = 1
for i in prime.items():
    ans *= i[1] + 1
    ans %= mod
print(ans)

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
typedef long long ll;
const int M = 1e9 + 7;
const int INF = 1e9;

int main() {
    ll n;
    cin >> n;
    ll ans = n * (n - 1) / 2;
    cout << ans << endl;
}


Measured memory_bytes: 256
n, m = map(int, input().split())

cost = []
open = []
for i in range(m):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    cost.append(a)
    open.append(c)

dp = [10**7] * (2**n)
dp[0] = 0
for i in range(m):
    key = []
    for j in range(1, n+1):
        if j in open[i]:
            key.append("1")
        else:
            key.append("0")
    key = "".join(key)
    key = int(key, 2)
    for j in range(2**n):
        next = j | key
        dp[next] = min(dp[next], dp[j] + cost[i])

if dp[2**n-1] == 10**7:
    print(-1)
else:
    print(dp[2**n-1])


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

template <
    typename TYPE,
    std::size_t SIZE>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a, i, n) for (ll(i) = a; (i) < (n); ++(i))
#define REP(i, n) REPS(0, i, n)
#define ALL(x) (x).begin(), (x).end()

const int INF = 100001;

int n;
int a, b;

int main()
{
    cin >> n;
    if (n == 2)
    {
        cin >> a >> b;
        cout << a + b;
    }
    else
    {
        cout << "Hello World" << endl;
    }
}

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

using namespace std;
typedef long long ll;

#define out(ans) cout << ans << endl
#define in(n) cin >> n
#define floop(i, N) for (ll i = 0; i < N; i++)
#define floop1(i, N) for (ll i = 1; i <= N; i++)
#define floopi(i, j, N) for (ll j = i + 1; j < N; j++)

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

constexpr ll inf = 1e18;

void solve();

int main()
{
    solve();
}

void solve()
{
    ll h;
    in(h);
    ll ans = 0;
    ll flag = 1;
    while (h != 0)
    {
        h /= 2;
        ans = ans + flag;
        flag *= 2;
    }
    out(ans);
}

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

// 入力
long long N;

// cur: 現在の値、use: 7, 5, 3 のうちどれを使ったか, counter: 答え
void func(long long cur, int use, long long &counter){
    if (cur > N) return; // ベースケース
    if (use == 0b111) ++counter; // 答えを増やす

    // 7 を付け加える
    func(cur * 10 + 7, use | 0b001, counter);

    // 5 を付け加える
    func(cur * 10 + 5, use | 0b010, counter);

    // 3 を付け加える
    func(cur * 10 + 3, use | 0b100, counter);
}

int main() {
    cin >> N;
    long long res = 0;
    func(0, 0, res);
    cout << res << endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define mod 1000000007
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    ll n,i;
    cin>>n;
    ll cte=0,cto=0;
    for(i=1;i<=n;i++)
    {
        if(i%2==0)
        {
            cte++;
        }
        else
        {
            cto++;
        }
    }
    double ans = (double)cto/(double)n;
    cout<<fixed<<setprecision(10)<<ans<<endl;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, p; cin>>a>>p;
	cout << (3*a+p)/2 << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAX_N 100000
#define MAX_M 100000
pair<int, int> itv[MAX_M];
int main(){
  int N, M, ans = 0;
  cin >> N >> M;
  int a[MAX_M], b[MAX_M];
  for(int i = 0; i < M; i++){
    cin >> a[i] >> b[i];
    itv[i].first = b[i], itv[i].second = a[i];
  }
  sort(itv, itv + M);
  int island = 0;
  for(int i = 0; i < M; i++){
    if(island <= itv[i].second){
      island = itv[i].first;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using P = function<E(E,size_t)>;
  Int n;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  P p;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(Int n_,F f,G g,H h,T ti,E ei,
	      P p=[](E a,size_t b){b++;return a;}):
    f(f),g(g),h(h),ti(ti),ei(ei),p(p){
    init(n_);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
    laz.assign(2*n-1,ei);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  inline void eval(Int len,Int k){
    if(laz[k]==ei) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1],laz[k]);
      laz[k*2+2]=h(laz[k*2+2],laz[k]);
    }
    dat[k]=g(dat[k],p(laz[k],len));
    laz[k]=ei;
  }
  T update(Int a,Int b,E x,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k]=h(laz[k],x);
      return g(dat[k],p(laz[k],r-l));
    }
    return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
		    update(a,b,x,k*2+2,(l+r)/2,r));
  }
  T update(Int a,Int b,E x){
    return update(a,b,x,0,0,n);
  }
  T query(Int a,Int b,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return ti;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(Int a,Int b){
    return query(a,b,0,0,n);
  }
  void update(Int k,T x){
    query(k,k+1);//evaluate
    k+=n-1;
    dat[k]=x;
    while(k){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
};


template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  using P = pair<Int, Int>;
  vector<P> vp;
  for(Int i=0;i<n;i++){
    Int l,r;
    cin>>l>>r;
    vp.emplace_back(l,r);
  }
  
  SegmentTree<Int, Int>::F f=[](Int a,Int b){return max(a,b);};
  SegmentTree<Int, Int>::G g=[](Int a,Int b){return a+b;};
  const Int INF = 1e9;
  SegmentTree<Int, Int> seg(m+2,f,g,g,-INF,0);
  vector<Int> v(m+2);
  for(Int i=0;i<m+2;i++) v[i]=i-(m+1);
  seg.build(m+2,v);

  Int ans=0;
  sort(vp.begin(),vp.end());
  for(Int i=0;i<n;i++){
    Int l,r;
    tie(l,r)=vp[i];
    seg.update(0,r+1,1);
    chmax(ans,seg.query(l+1,m+2)-l);
  }
  
  cout<<max(n-m,ans)<<endl;
  return 0;
}


Measured memory_bytes: 15596
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int solve(vector<int> &h, vector<int> &a,int i){
    if (a.at(i) > -1)
    {
        return a.at(i) ;
    }else
    {
        a.at(i) = min(a.at(i-2) + abs(h.at(i) - h.at(i-2)) ,a.at(i-1) + abs(h.at(i)-h.at(i-1))) ;
        return a.at(i) ;
    }
    
    
}

int main(){
    int n ;
    cin >> n ;
    vector<int> h (n) ;
    for (size_t i = 0; i < n; i++)
    {
        /* code */
        cin >> h.at(i) ;
    }
    vector<int> hyo (n,-1) ;
    hyo.at(0) = 0 ;
    hyo.at(1) = abs(h.at(1) - h.at(0)) ;
    for (int i = 2; i < n; i++)
    {
        /* code */
        hyo.at(i) = solve(h,hyo,i) ;
    }
    
    int ans = hyo.at(n-1) ;
    cout << ans << endl ;
    
    

}

Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 500000
#define SENTINEL 1000000000

int S[MAX], count=0;

void merge(int *, int, int, int);
void mergeSort(int *, int, int);

int main()
{
  int n, i, left, right;

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

  left = 0;
  right = n;

  mergeSort(S, left, right);

  for(i=0; i<n; i++)
    {
      if(i < n-1)printf("%d ", S[i]);
      else printf("%d\n%d\n", S[i], count);
    }

  return 0;
}

void merge(int *A, int left, int mid, int right)
{
  int n1 = mid - left;
  int n2 = right - mid;
  int L[n1+1], R[n2+1], i, j, k;

  for(i=0; i<n1; i++)
    {
      L[i] = A[left+i];
    }
  for(i=0; i<n2; i++)
    {
      R[i] = A[mid+i];
    }
  L[n1] = SENTINEL;
  R[n2] = SENTINEL;

  i=0;
  j=0;

  for(k=left; k<right; k++)
    {
      if(L[i] <= R[j])
        {
          A[k] = L[i];
          i = i + 1;
        }
      else
        {
          A[k] = R[j];
          j = j + 1;
        }
      count++;
    }
}

void mergeSort(int *A, int left, int right)
{
  int mid;

  if(left+1 < right)
    {
      mid = (left + right) / 2;
      mergeSort(A, left, mid);
      mergeSort(A, mid, right);
      merge(A, left, mid, right);
    }
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



int main(){
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    V<int> p(3);
    rep(i,n) {
        int d;
        cin >> d;
        if(d <= a) p[0]++;
        else if(d <= b) p[1]++;
        else p[2]++;
    }
    int ans = inf;
    rep(i,3) chmin(ans, p[i]);
    cout << ans << endl;
}

Measured memory_bytes: 3580
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int H, W, i, j;
    while (1) {
        scanf("%d %d", &H, &W);
        if ((H==0)&&(W==0)) {
            break;
        }
        for ( i=1; i<=H; i++) {
            for (j=1; j<=W; j++) {
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
        
    }
    
    
    return 0;
}


Measured memory_bytes: 2144
#include<cstdio>
int n, a[100002], pre[100002], suf[100002];
int abs(int a){ return a < 0 ? -a : a;}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), pre[i] = pre[i-1] + abs(a[i] - a[i-1]);
	for(int i = n; i >= 1; --i) suf[i] = suf[i+1] + abs(a[i] - a[i+1]);
	for(int i = 1; i <= n; ++i) printf("%d\n", pre[i-1] + suf[i+1] + abs(a[i-1] - a[i+1]));
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S;
vector<int> E[2020];
vector<int> Ds[2020];
int SD[2020];
int D[2020][2020];
int lef;

void dfs(int cur,int pre,int id,int d) {
	if(S[cur]=='1') {
		Ds[id].push_back(d);
		SD[id]+=d;
	}
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,id,d+1);
	
}

void dfs1(int cur,int pre,int id,int d) {
	D[cur][id]=d;
	FORR(e,E[cur]) if(e!=pre) dfs1(e,cur,id,d+1);
}

pair<int,int> can(int cur,int pre) {
	pair<int,int> P={0,0};
	
	if(S[cur]=='1') P.first=1;
	FORR(e,E[cur]) if(e!=pre) {
		auto Q=can(e,cur);
		Q.second+=Q.first;
		int mi=min(Q.second,P.second);
		lef-=mi;
		Q.second-=mi;
		P.second-=mi;
		P.first+=Q.first;
		P.second+=Q.second;
	}
	return P;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>S;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(x,N) dfs1(x,x,x,0);
	
	int mi=1<<30;
	FOR(x,N) {
		ZERO(SD);
		FOR(y,N) Ds[y].clear();
		FORR(e,E[x]) dfs(e,x,e,1);
		int sum=0;
		int num=0;
		FOR(y,N) {
			sum+=SD[y];
			if(SD[y]>0) num++;
		}
		
		if(sum%2) continue;
		int ma=*max_element(SD,SD+N);
		if(ma*2<=sum) {
			mi=min(mi,sum/2);
			continue;
		}
		y=max_element(SD,SD+N)-SD;
		lef=(ma-(sum-ma))/2;
		can(y,x);
		if(lef<=0) mi=min(mi,sum/2);
	}
	if(mi==1<<30) mi=-1;
	cout<<mi<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 24448
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

#define DEBUG
#ifndef DEBUG
#define endl "\n"
#define log(args...)
#else
#define log(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); logf(_it, args); }
void logf(istream_iterator<string> it) {
}
template<typename T, typename ... Args>
void logf(istream_iterator<string> it, T a, Args ... args) {
	cout << *it << " = " << a << endl;
	logf(++it, args...);
}
#endif

#define forn(i,k,n) for(ll i=(k); i<(n); i++)

const double PI = acos(-1);
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

void solve() {
	cini(n);
	cini(m);

	int even = n * (n - 1) / 2 + m * (m - 1) / 2;

	cout << even << endl;

}

int main() {
	cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	solve();
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  cin >> s;
  
  ll ans = 0;
  vector<ll> rem(2019, 0);
  rem[0] = 1;
  ll n = 0, ex = 1;
  for(ll i = (ll)s.size()-1; i >= 0; i--) {
    n = (n+(s[i]-'0')*ex)%2019;
    ans += rem[n];
    rem[n]++;
    ex = ex *10 %2019;
  }
  
  cout << ans << "\n";
}

Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
constexpr auto MOD = 1000000007;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VLL;

string s;
long long n, m;

int main()
{
  ll a, b, k;
  cin >> a >> b >> k;
  if (a >= k)
  {
    cout << a - k << " " << b<<endl;
    return 0;
  }
  if(b>=k-a){
    cout << 0 << " " << b - k + a << endl;
    return 0;
  }
  cout << 0 << " " << 0<<endl;
  return 0;
}


Measured memory_bytes: 256
#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() {
  ll A;
  double B;
  cin >> A >> B;
  ll B100 = B * 100 + 0.000001;
  ll ans = ((A * B100) / 100);
  cout << ans << endl;
}


Measured memory_bytes: 3708
n = gets.chomp.to_i
s = n.times.map{gets.chomp}
count = 0
s.each do |si|
  pos = 0
  len = si.length
  bef = ""
  len.times do |i|
    count += 1 if bef == "A" && si[i] == "B"
    bef =  si[i]
  end
end

countOA = 0
countBO = 0
countBA = 0

s.each do |si|
  if si[0] == "B" && si[-1] == "A" then
    countBA += 1
  elsif si[0] == "B" then
    countBO += 1
  elsif si[-1] == "A" then
    countOA += 1
  end
end

countBA -= 1 if [countBO, countOA].max == 0 && countBA != 0

puts count + countBA + [countBO, countOA].min


Measured memory_bytes: 4220
S = input()
T = input()
s = []
t = []
for i in range(len(S)):
  s.append(S[i])
  t.append(T[i])
flag = 0
if s == t:
  print("Yes")
  flag += 1
else:
  for i in range(len(s)):
    A = s[0]
    s.remove(A)
    s.append(A)
    if s == t:
      print("Yes")
      flag += 1
      break
if flag == 0:
  print("No")


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
    ll X, Y; cin >> X >> Y;

    int ans = 0;
    while (X <= Y) {
        X *= 2; ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;

namespace ABC054C
{
    class Program
    {
        static readonly int DIM = 10;

        static void Main(string[] args)
        {
            string[] bufs = Console.ReadLine().Split(' ');
            int N = Int32.Parse(bufs[0]);
            int M = Int32.Parse(bufs[1]);

            int[] path = new int[M];
            for(int i = 0; i < M; i++)
            {
                bufs = Console.ReadLine().Split(' ');
                int a = Int32.Parse(bufs[0]);
                int b = Int32.Parse(bufs[1]);
                path[i] = a * DIM + b;
            }

            Console.WriteLine(Search(path, 1, N - 1));
            return;
        }

        static int Search(int[] path, int pos, int n)
        {
            if(n == 0) { return 1; }

            int res = 0;
            int count = 0;
            int[] queue = new int[7];

            int[] pathNext = new int[path.Length];
            path.CopyTo(pathNext, 0);
            
            for(int i = 0; i < path.Length; i++)
            {
                if (path[i] / DIM == pos)
                {
                    queue[count++] = path[i] % DIM;
                    pathNext[i] = 0;
                }
                else if (path[i] % DIM == pos)
                {
                    queue[count++] = path[i] / DIM;
                    pathNext[i] = 0;
                }
            }

            for (int i = 0; i < count; i++)
            {
                res += Search(pathNext, queue[i], n - 1);
            }

            return res;
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,c;cin>>n>>m>>c;
  int b[m];
  for(int i=0;i<m;i++)cin>>b[i];
  int ans=0;
  for(int i=0;i<n;i++){
    int sum=c;
    for(int j=0;j<m;j++){
      int a;cin>>a;sum+=b[j]*a;
    }
    if(sum>0)ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a, b, c, d;
    int taka, ao;

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

    taka = a / d;
    if (a % d)
        taka++;
    ao = c / b;
    if(c % b)
        ao++;
    
    if (taka >= ao)
        printf("Yes\n");
    else 
        printf("No\n");
    
    return 0;
}

Measured memory_bytes: 1648
# https://abc003.contest.atcoder.jp/submissions/1710595
# usage: 
#   NCR.init(<nの最大値>)
#   NCR.nCr(n, r)
MOD = 10**9+7
class NCR
  @fac = []

  class << self
    def init(n)
      @fac[0] = 1
      @fac[1] = 1
      i = 2
      while i <= n
        @fac[i] = (@fac[i-1]*i)%MOD
        i += 1
      end
      @mod_inv_fac = {}
    end

    def fact(n)
      @fac[n]
    end

    def power(a, b)
      x = 1; y = a
      while b > 0
        x = (x*y)%MOD if b.odd?
        y = (y*y)%MOD
        b /= 2
      end
      x%MOD
    end

    def mod_inv(n)
      power(n, MOD-2)
    end

    def mod_inv_fac(x)
      @mod_inv_fac[x] ||= mod_inv(@fac[x])
    end

    def nCr(n, r)
      return 0 if r > n
      (@fac[n] * (mod_inv_fac(r) * mod_inv_fac(n-r)%MOD))%MOD
    end
  end
end

n, *as = $stdin.read.split.map(&:to_i)
NCR.init(n+1)

chk = Array.new(n+1)
l = r = nil
as.each.with_index do |a, idx|
  if chk[a]
    l = chk[a]
    r = idx+1
    break
  end
  chk[a] = idx+1
end

for k in 1..(n+1)
  p (NCR.nCr(n+1, k) - NCR.nCr(l-1+(n+1)-r, k-1)) % MOD
end


Measured memory_bytes: 25596
def f_must_be_rectangular(N, Positions):
    # 参考: https://atcoder.jp/contests/abc131/submissions/6086451
    # x軸, y軸をまとめて1つのリストで扱う
    import sys
    sys.setrecursionlimit(10**6)

    vertex_maxsize = 10**5 + 1
    target = [[] for _ in range(2 * vertex_maxsize)]
    is_visited = [False] * (2 * vertex_maxsize)
    for x, y in Positions:
        y += vertex_maxsize  # 1つのリストで扱う都合上、ずらす
        target[x].append(y)
        target[y].append(x)

    def dfs(v):
        if is_visited[v]:
            return
        is_visited[v] = True
        count[v // vertex_maxsize] += 1  # vがx軸とy軸のどっちを指しているか
        for u in target[v]:
            dfs(u)  # 頂点vに接続されている頂点へ向かう

    ans = 0
    for i in range(2 * vertex_maxsize):
        if is_visited[i]:
            continue
        count = [0] * 2
        dfs(i)  # 頂点iにつながっている頂点を調べる
        # x座標とy座標のそれぞれについて、ペアにすると矩形が完成する
        # 座標がいくつあるか。その積が解となる
        ans += count[0] * count[1]
    return ans - N  # 最初に与えられた座標の分、引く

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(f_must_be_rectangular(N, Positions))

Measured memory_bytes: 111780
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String s = scanner.next();

    char[] chars = s.toCharArray();
    if (check(chars)) {
      System.out.println("AC");
    } else {
      System.out.println("WA");
    }
  }

  static boolean check(char[] s) {
    if (s[0] != 'A') return false;
    int numC = 0;
    for (int i = 1; i < s.length; i++) {
      if (i >= 2 && i <= s.length - 2 && s[i] == 'C') {
        numC++;
        continue;
      }
      if (s[i] < 'a' || s[i] > 'z') {
        return false;
      }
    }
    return numC == 1;
  }
}

Measured memory_bytes: 23764
import itertools

x = int(input())
my_iter = itertools.combinations_with_replacement([0,1,2,3,4,5], int(x/100))
for p in my_iter:
    s = sum(p)
    if sum(p) % 100 == x % 100:
        z_c = len(list(filter(lambda x:x == 0, p)))
        if z_c >= int(sum(p) / 100):
            print(1)
            break
else:
    print(0)


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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

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

  vi h(n);
  rep(i,0,n) cin >> h[i];

  const ll inf = 1e18;
  vl dp(n, inf);
  dp[0] = 0;

  rep(i,0,n-1) {
    rep(j,i+1,min(i+k+1, n)) ckmin(dp[j], dp[i] + abs(h[i]-h[j]));
  }

  cout << dp[n-1] << '\n';

}

Measured memory_bytes: 1408
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef vector<int> vi;
typedef long long ll;



int main(){
    
    ll x,m,con,MIN;
    cin>>x;
    if(x==1){
        cout<<1<<endl;
        return 0;
    }
    if(x==2){
        cout<<2<<endl;
        return 0;
    }
    rep(i,1,100000){
        m=i*(i+1)/2;
        con=i;
        if(m>=x)break;
    }

        cout<<con<<endl;


    
}






Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

P, Q, R = get_ints

pq = P + Q
qr = Q + R
rp = R + P

puts [pq, qr, rp].min


Measured memory_bytes: 14396
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod

#define N 2010
ll n,a[100010];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
	cin>>a[i];
    }
    sort(a,a+n);
    if(a[0]==a[n-1]){
	if(a[0]==n-1||(1<=a[0]&&a[0]<=n/2))cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
    }
    else if(a[0]+1<a[n-1]){
	cout<<"No"<<endl;
    }
    else{
	ll b=0,c=0;
	for(int i=0;i<n;i++){
	    if(a[i]==a[0])c++;
	    else b++;
	}
	if(c+1<=a[n-1]&&a[n-1]<=c+b/2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
    }
}




Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#define MODN 1000000007

#define modadd(lhs,rhs) (((lhs)+(rhs)) % MODN)
#define modml(lhs,rhs) (((long long)(lhs)*(rhs))%MODN)

int main(void){
    register long i;
    long n;
    scanf("%ld",&n);
    long a[n];
    long ans = 0;
    for(i = 0;i < n;i++)scanf("%ld",&a[i]);
    long cus[n+1];
    cus[n] = 0;
    for(i = n-1;i >= 0;i--)cus[i] = modadd(cus[i+1],a[i]);
    for(i = 0;i < n-1;i++)ans = modadd(ans,modml(a[i],cus[i+1]));
    printf("%ld",ans);
}

Measured memory_bytes: 4828
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
using namespace std;
 
#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ans=0;llfor;///////////////////////////////////////////////////////////
int main(){
  int D;
  cin>>D;
  string S="Christmas";
  for(int i=0;25-D-i>0;i++) S+=" Eve";
  cout<<S<<endl;
return 0;}

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

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			int n = cin.Int();
			int[] l = cin.ArrayInt(n);

			Array.Sort(l);
			int max = 2001;
			int[] lsum = new int[max];
			int index = 0;
			for (int i = 0; i < n; i++) {
				int len = l[i];
				int prev = lsum[index];
				while (index < len) {
					++index;
					lsum[index] = prev;
				}

				lsum[len]++;
			}
		
			int last = lsum[index];
			for (int i = index; i < max; i++) {
				lsum[i] = last;
			}

			long ans = 0;
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					int a = l[i];
					int b = l[j];
					int sub = b - a;

					int temp = lsum[a + b - 1] - lsum[sub];
					if (a > b - a) {
						temp--;
					}

					if (b > b - a) {
						temp--;
					}
					ans += Math.Max(temp, 0);
				}
			}

			Console.WriteLine(ans / 3);
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;

		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
#define MN 505
int k,n,col[MN<<1],N,ans[MN][MN];
int main()
{
	scanf("%d",&k);
	n=(k+3)/4*2;
	N=n<<1;
	for(int i=1;i<=N;i++) col[i]=i;
	if(k==1) return 0*printf("1\n1\n");
	if(k%4==3) col[N]=N-1;
	if(k%4==2) col[N]=col[N-1]=N-2,col[N-2]=N-3;
	if(k%4==1) col[N]=col[N-1]=N-3,col[N-2]=col[N-3]=N-4,col[N-4]=N-5;
	for(int i=1;i<=N;i+=2)
	{
		for(int j=0;j<n;j++)
			ans[j][((i>>1)+j)%n]=col[(j&1)?(i+1):i];
	}
	printf("%d\n",n);
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			printf("%d ",ans[i][j]);
		}
		puts("");
	}
}

Measured memory_bytes: 2176
N, M = gets.chomp.split(" ").map(&:to_i)
node = Struct.new("Node", :to)

edges = []
M.times do
  edges << gets.chomp.split(" ").map(&:to_i)
end

# Union Find

def find(x)
  if @par[x] == x
    return x
  else
    @par[x] = find(@par[x])
    return @par[x]
  end
end

def unite(x, y)
  x = find(x)
  y = find(y)
  if x == y
    return
  end
  if @rank[x] < @rank[y]
    @par[x] = y
  else
    @par[y] = x
    if @rank[x] == @rank[y]
      @rank[x] += 1
    end
  end
end

def same(x, y)
  return find(x) == find(y)
end

ans = 0
M.times do |i|
  @g = Array.new(N+1){node.new([])}
  @par = (0..N).to_a
  @rank = Array.new(N+1, 0)
  M.times do |j|
    next if i == j
    a, b = edges[j]
    @g[a].to << b
    @g[b].to << a    
  end
  (1..N).each do |n1|
    @g[n1].to.each do |n2|
      unite(n1, n2)
    end
  end
  nroot = 0
  (1..N).each do |root|
    if root == @par[root]
      nroot += 1
    end
  end
  if nroot != 1
    ans += 1
  end
end

puts ans


Measured memory_bytes: 1916
#include <bits/stdc++.h>
#define forn(i, n) for (long long i = 0; i < (long long)(n); ++i)
#define for1(i, n) for (long long i = 1; i <= (long long)(n); ++i)
#define fore(i, l, r) for (long long i = (long long)(l); i <= (long long)(r); ++i)
#define fordn(i, n) for (long long i = (long long)(n) - 1; i >= 0; --i)
#define ford1(i, n) for (long long i = (long long)(n); i >= 1; --i)
#define all(x) (x).begin(), (x).end()
#define PI 3.141592653589793
using namespace std;
using ll = long long;
using ld = long double;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, a;
    cin >> n >> a;
    if((n % 500) <= a) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();

        Map<Integer, Integer> m = new HashMap<Integer, Integer>();

        int i = 1;
        int a = s;
        m.put(a, i);

        // start from i == 2
        i++;
        while (true) {
            if (a % 2 == 0) {
                a = a / 2;
            } else {
                a = 3 * a + 1;
            }
            //System.out.println(String.format("%d %d", i, a));
            if (m.containsKey(a)) {
                System.out.println(i);
                return;
            }

            m.put(a, i);
            i++;
        }

    }

}

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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}

int main() {
  string s;
  cin>>s;
  if(s.size()==2){
    cout<<s<<endl;
  }else{
    cout<<s[2]<<s[1]<<s[0]<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int a, b; std::cin >> a >> b;
    std::cout << a*b << std::endl;
    return 0;
}


Measured memory_bytes: 3636
import java.util.*;

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

        int n = sc.nextInt();

        int[] ary = new int[n];
        
        for (int i = 0; i < n; i++)
            ary[i] = sc.nextInt();
        
        int j = n - 1;
        System.out.print(ary[j]);
        while (--j >= 0) {
            System.out.print(' ');
            System.out.print(ary[j]);
        }
        System.out.println();
    }
}



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

typedef long long ll;

int main() {        
	int v[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> v[i][j];
		}
	}
	for (int i = 0; i <= 100; ++i) {
		int a = v[0][0] - i;
		if (a >= 0) {
			for (int j = 0; j <= 100; ++j) {
				int b = v[1][1]  - j;
				if (b >= 0) {
					for (int k = 0; k <= 100; ++k) {
						int c = v[2][2] - k;
				if (c >= 0) {
							bool d = 1;
							vector<int> x = {i,j,k};
							vector<int> y = {a,b,c};
							for (int e = 0; e < 3; ++e) {
								for (int m = 0; m < 3; ++m) {
									if (v[e][m] != x[e] + y[m]) {
										d = 0;
									}
								}
							}
							if (d) {
								cout << "Yes";
								return 0;
							}
						}
					}
				} 
			}
		}
	}
	cout << "No";
}



//a0 + b0   a0 + b1    a0 + b2
//a1 + b1   a1 + b1
                     //a2 + b2


Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const int MOD = 1e9+7;

int dp[3005][3005];
// i番目まで見た時に、i番目より小さい数字がj個残っているような場合の数

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

    int n;
    string s;
    cin >> n >> s;

    for (int i = 0; i < n; i++) dp[0][i] = 1;

    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n - i; j++) {
            if (s[i] == '<') {
                (dp[i+1][j] += dp[i][j]) %= MOD;
                (dp[i+1][n-i] += MOD - dp[i][j]) %= MOD;
            } else {
                (dp[i+1][0] += dp[i][j]) %= MOD;
                (dp[i+1][j] += MOD - dp[i][j]) %= MOD;
            }
        }

        for (int j = 1; j < n-i; j++) {
            (dp[i+1][j] += dp[i+1][j-1]) %= MOD;
        }
    }

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

Measured memory_bytes: 35200
a, b  = map(int, input().split())
count = 0
for i in range(b):
  temp = a + i
  if temp > b:
    break
  li = []
  ni = temp
  for p in range(4):
    li.append(ni // (10 ** (4 - p)))
    ni = ni % (10 ** (4 - p))
  li.append(ni % 10)
  if li == li[::-1]:
    count += 1
print(count)

Measured memory_bytes: 9204
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>	

using namespace std;

int main() {
	long long N;
	cin >> N;
	vector<long long> a(N + 1);
	vector<long long> box(N + 1, 0);
	for (long long i = 1; i <= N; ++i) {
		cin >> a[i];
	}


	long long countOne = 0;
	for (long long i = N; i >= 1; --i) {
		long long balC = 0;
		long long boxA;
		for (long long j = 1;i * j <= N; ++j) {
			balC += box[j * i];
		}
		boxA = balC % 2;
		if (boxA != a[i]) {
			box[i] = 1;
		}
		countOne += box[i];
	}


	cout << countOne << endl;
	for (long long i = 1; i <= N; ++i) {
		if (box[i] == 1) {
			cout << i << " ";
		}
	}
	return 0;
}

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

using namespace std;
#define BUF (1000)
#define ll long long 

int n;

int main(void){
	cin >> n;

	for(int i=0;i<n;i++){
		ll a,b;
		ll big = 0;
		cin >> a >> b;
		ll sc = a*b;
		ll c=min(a,b);
		ll h = max(a,b);
		ll l = min(a,b);
		while(1){
			ll m = (h+l)/2;
			if(m*m<=sc-1){
				l=m;
			}else{
				h=m;
			}
			if(abs(h-l)<=1){
				c=l;
				break;
			}
		}
		if(a==b){
			cout << 2*a-2 << "\n";
			continue;
		}
		if(c*(c+1)<=sc-1) big=1;
		if(a==b) big++;
		cout << 2*c -2 + big << "\n";	
	}


	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,h[MAXN];
void add(int &a,int b) {a+=b; if(a>=MOD) a-=MOD;}
void dec(int &a,int b) {a-=b; if(a<0) a+=MOD;}
int pow_mod(int a,int i)
{
    int s=1;
    while(i)
    {
        if(i&1) s=1LL*s*a%MOD;
        a=1LL*a*a%MOD;
        i>>=1;
    }
    return s;
}
P solve(int l,int r)
{ 
    int minh=INF;
    for(int i=l;i<=r;i++) minh=min(minh,h[i]);
    int cnt=0;
    for(int i=l;i<=r;i++)
    {
        h[i]-=minh;
        if(!h[i]) cnt++;
    }
    int ans1=1,ans2=1;
    int lb=INF,rb=-INF;
    for(int i=l;i<=r;i++)
    {
        if(h[i]==0)
        {
            if(rb!=-INF)
            {
                P p=solve(lb,rb);
                ans1=1LL*ans1*p.F%MOD;
                ans2=1LL*ans2*(p.F+p.S)%MOD;
            }
            lb=INF;rb=-INF;
        }
        else
        {
            lb=min(lb,i);
            rb=max(rb,i);
        }
    }
    if(rb!=-INF)
    {
        P p=solve(lb,rb);
        ans1=1LL*ans1*p.F%MOD;
        ans2=1LL*ans2*(p.F+p.S)%MOD;
    }
    ans2=1LL*ans2*pow_mod(2,cnt)%MOD;
    int mult=pow_mod(2,minh);
    dec(ans2,2LL*ans1%MOD); ans1=1LL*ans1*mult%MOD; add(ans2,ans1);
    return P(ans1,ans2);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    printf("%d\n",solve(1,n).S);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main() {
    int x, y; cin >> x >> y;
    cout << x + y / 2 << endl;
	return 0;
} 

Measured memory_bytes: 256