akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

// chmax, chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N,M;
vector<int> par, rnk;
vector<int> grp;

// 初期化
void init () {
    REP(i,N) {
        par[i] = i;
        rnk[i] = 0;
        grp[i] = 1;
    }
}

// 木の根を求める
int find ( int x ){
    if ( par[x] == x ) return x;
    else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void unite( int x, int y){
    x = find(x);
    y = find(y);
    if ( x == y ) return;
    
    int total = grp[x] + grp[y];
    grp[x] = total;
    grp[y] = total;
    
    if ( rnk[x] < rnk[y] ){
        par[x] = y;
    } else {
        par[y] = x;
        if ( rnk[x] == rnk[y] ) rnk[x]++;
    }
}

// xとyが同じ集合に属するか否か
bool same( int x, int y ){
    return find(x) == find(y);
}

int main() {
    cin >> N >> M;
    par.resize(N); rnk.resize(N); grp.resize(N);
    
    init();
    
    REP(i,M){
        int x,y;
        cin >> x >> y; --x; --y;
        unite(x,y);
    }
    
    int ans = 0;
    REP(i,N){
        ans = max(ans,grp[i]);
    }
    
    cout << ans << endl;
    
    
    return 0;
}


Measured memory_bytes: 5592
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
int nx[4] = {1,0,-1,0};
int ny[4] = {0,1,0,-1};
class BIT{
    private:
        vector<ll> bit;
        ll size;
    public:
        BIT(ll n){
            bit.resize(n+1);
            size = n;
        }
        ll sum(ll i){
            ll res = 0;
            while(i > 0){
                res += bit[i];
                i -= i&-i;
            }
            return res;
        }
        void add(ll i,ll x){
            while(i <= size){
                bit[i] += x;
                i += i&-i;
            }
        }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n+1),na(n+1);
    rep(i,n) cin >> a[i];
    ll l = -1,r = 1e10;
    ll len = n*(n+1)/2;
    while(r-l>1){
        ll m = (l+r)/2;
        vector<ll> ra(n+1,0),nra(n+1,0);
        rep(i,n){
            if (a[i] < m) na[i] = -1;
            else na[i] = 1;
            ra[i+1] = ra[i]+na[i];
            nra[i+1] = ra[i+1];
        }
        SORT(nra);
        nra.erase(unique(all(nra)),nra.end());
        rep(i,n+1){
            ra[i] = upper_bound(all(nra),ra[i])-nra.begin();
            na[i] = ra[i];
        }
        SORT(na);
        BIT bit(n+1);
        ll cnt = 0;
        rep(i,n+1){
            bit.add(ra[i],1);
            cnt += n+1-(lower_bound(all(na),ra[i])-na.begin())-(bit.sum(n+1)-bit.sum(ra[i]-1));
        }
        if (cnt >= (len+1)/2) l = m;
        else r = m;
    }
    PRINT(l);
}


Measured memory_bytes: 4256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int count = 0;
    for (int i = 1; i <= N; i++) {
      int pi = sc.nextInt();
      if (pi != i) count++;
    }
    if (count == 0 || count == 2) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }
}


Measured memory_bytes: 24020
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

int main() {
    FIO;
    int n; 
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ind = 0;
    ll begin = 1000;
    ll end = 0;
    while(ind<n){
        int j = ind;
        ind++;
        while(ind<n && a[ind] >= a[ind-1]) ind++;
        ll cnt = begin/a[j];
        end += cnt*(a[ind-1]-a[j]);
        begin += cnt*(a[ind-1]-a[j]);
    }
    cout<<begin<<endl;
	return 0;
}

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

typedef long long ll;
#define int         ll
typedef vector<int> vi;
#define test        int t; cin >> t; while(t--)
#define max(a,b)   (a>b?a:b)
#define min(a,b)   (a<b?a:b)
const int mod = 1000000007;


int32_t main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int ans=0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; k++) {
                ans+=__gcd(i,__gcd(j,k));
            }
        }
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 3644
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
void print(char str[],int a,int b){
    for(int i = a; i <= b; i++)  printf("%c",str[i]);
    printf("\n");
}
 
void replace(char str[],char p[],int a,int b){
    int p_length = b-a+1;
    for(int i = 0; i < p_length;i++) str[a+i] = p[i];
}
 
void reverse(char str[],int a,int b){
    int left = a,right = b;
    while(left < right){
        swap(str[left++],str[right--]);
    }
}
 
int main(){
    char str[1001],p[1001],order[8];
    int q,a,b;
    scanf("%s",str);
    scanf("%d",&q);
    for(int i = 0; i < q; i++){
        scanf("%s %d %d",order,&a,&b);
        switch(order[2]){
        case 'i':
            print(str,a,b);
            break;
        case 'v':
            reverse(str,a,b);
            break;
        case 'p':
            scanf("%s",p);
            replace(str,p,a,b);
            break;
        }
    }
}


Measured memory_bytes: 2696
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
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(){
    ll n;cin >> n;
    cout << n <<':';
    vl v;
    while(true){
        bool check=false;
        repl(i,2,sqrt(n)+1){
            if(n%i==0){
                n/=i;
                v.pb(i);
                check=true;
                break;
            }
        }
        if(check)continue;
        if(n!=1)v.pb(n);
        break;
    }
    rep(i,v.size()){
        cout <<" ";
        cout <<v[i];
    }
    cout <<endl;
}


Measured memory_bytes: 3148
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define RREP(i,a,b) for(ll i=(a); i>=(b); i--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> p;
typedef vector<pair<ll, ll>> vpl;


int main(){
    int n; cin >> n;
    for(int i=1; i<=9; i++){
        int p = i*100 + i*10 + i;
        if(n <= p){
            cout << p << endl;
            break;
        }
    }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main()
{
	map< string, vector<int> > m;
	int n, i;
	string s;
	while (cin >> s)
	{
		if (cin.eof()) break;
		cin >> n;
		m[s].push_back(n);
	}
	map< string, vector<int> >::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << endl;
		sort((*it).second.begin(), (*it).second.end());
		for (i = 0; i < (*it).second.size(); i++)
		{
			cout << (*it).second[i];
			if (i < (*it).second.size()-1)
				cout << " ";
			else
				cout << endl;
		}
		it++;
	}
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int h, w;
  cin >> h >> w;
  int a[h][w];
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      char c;
      cin >> c;
      if(c=='.') a[i][j] = 0;
      else a[i][j] = 1;
    }
  }
  bool t[w],y[h];
  for(int i=0; i<h; i++){
    y[i] = false;
    int tmp = 0;
    for(int j=0; j<w; j++){
      tmp += a[i][j];
    }
    if(tmp == 0) y[i] = true;
  }
  for(int i=0; i<w; i++){
    t[i] = false;
    int tmp = 0;
    for(int j=0; j<h; j++){
      tmp += a[j][i];
    }
    if(tmp == 0) t[i] = true;
  }
  for(int i=0; i<h; i++){
    if(y[i]) continue;
    for(int j=0; j<w; j++){
      if(t[j]) continue;
      if(a[i][j]==1) cout << "#";
      else cout << ".";
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}

int main(){
    ll x, y; cin >> x >> y;
    for(ll a = 0; a <= 50; ++a){
        for(ll b = 0; b <= 25; ++b){
            if(a+b == x && (2*a + 4*b) == y){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
import logging
logging.basicConfig(level=logging.CRITICAL,format=' %(asctime)s - %(levelname)s - %(message)s')

def power(n):
    i = 1
    logging.info('func start')
    while n > 0:
        i *= 2
        n -= 1
        logging.debug('i = {}, n = {}'.format(i,n))
    logging.info('func end')
    return i

i = 0
n = int(input())
logging.info('in loop')
while not (power(i + 1) > n):
    i = i + 1
    logging.debug('i = {}, pow(i) = {}'.format(i,power(i)))

logging.info('out loop')
print(power(i ))


Measured memory_bytes: 4584
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(i):
    # if all([v != -1 for v in visited]):
    #     return
    color = visited[i]
    for nextIdx, wgt in graph[i]:
        if visited[nextIdx] == -1:
            if wgt % 2 == 0:
                visited[nextIdx] = color
            else:
                visited[nextIdx] = int(not color)
            dfs(nextIdx)

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b, w = map(int, input().split())
    graph[a - 1].append([b - 1, w])
    graph[b - 1].append([a - 1, w])

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)


Measured memory_bytes: 85204
N, M = map(int, input().split())
from math import sqrt

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

g_list = divisor(M)
g_list.sort(reverse=True)
ans = 0
for g in g_list:
    if M//g >= N:
        ans = g
        break
print(ans)

Measured memory_bytes: 63008
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
#define ALL(a)  (a).begin(),(a).end()
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
int per(int n, int r) {
	r = n - r;
	int sum = 1;
	int i;
	for (i = n; i >= r + 1; i--)sum *= i;
	return sum;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};

int ctoi(const char c) {
	return c - '0';
}
int keta(int a) {
	return to_string(a).size();
}

signed main() {
	string s;
	cin >> s;
	rep(i, s.size()) {
		cout << 'x';
	}
	cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main ()
{
    char a[300];
    gets (a);
    int i;
    for (i=0;a[i]!='\0';i++)
    {
        if (a[i]==',')
            {
            printf (" ");
            }
        else
        {
            printf ("%c",a[i]);
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <cstdio>

int main(){
    char s[4];
    scanf("%s",s);
    int counta = 0;
    int countb = 0;
    int countc = 0;
    for(int i = 0; i < 3; i++){
        if(s[i] == 'a'){
            counta++;
        }else if(s[i] == 'b'){
            countb++;
        }else if(s[i] == 'c'){
            countc++;
        }
    }
    if(counta == 1 && countb == 1 && countc == 1){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

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

int main() {
  long N;
  cin >> N;
  vector<long> T(N);
  for (long i = 0; i < N; i++) cin >> T.at(i);
  long ans = 1;
  for (auto t : T) {
    ans = lcm(ans, t);
  }
  cout << ans << "\n";
}

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

using namespace std;

#define ll long long

int main() {
  ll K;
  cin >> K;

  vector<ll> a(K);
  a[0] = 7 % K;
  for (int i = 1; i < K; i++) {
    a[i] = (a[i - 1] * 10 + 7) % K;
  }

  for (int i = 0; i < K; i++) {
    if (a[i] == 0) {
      cout << i + 1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 11088
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

int pow(int x, int n){
  if(n == 0)return 1;
  if(n % 2 == 0)return pow(x * x % MOD, n/2);
  else return x * pow(x, n-1) % MOD;
}

signed main(){
  int n;cin>>n;int h[110000];rep(i,n)cin>>h[i];h[0]--;
  rep(i,n-1){
    if(h[i] < h[i+1])h[i+1]--;
    else if(h[i] > h[i+1]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<string>
#define rep(i,n) for (int i=0; i<n; i++)
using namespace std;
int main() {
  double w,h,x,y;
  cin >> w >> h >> x >> y;
  double cw = w/2;
  double ch = h/2;
  int ans1 = 0;
  int ans2 = 0;
  double sum = w*h/2;
  if (cw == x) {
    ans1 = 1;
  }
  if (ch == y) ans2 = 1;
  if (ans1+ans2 == 2) {
    printf("%f",sum);
    cout <<' ' << 1 << endl;
  }
  if (ans1+ans2==1) {
    printf("%f",sum);
    cout << ' ' << 0 << endl;
  }
  if (ans1+ans2==0) {
    printf("%f",sum);
    cout << ' ' << 0 << endl;
  }
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
 #define rep(i, n) for (int i = 0; i < (int)(n); i++)
 #define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
int main(){
    int n;
    cin>>n;
    vector<int> p(n);
    rep(i,n){
        cin>>p[i];
    }
    all(p);
    p[n-1] /= 2;
    int sum=0;
    rep(i,n){
        sum += p[i];
    }
    cout<<sum<<endl;
}

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

int H, W, blacks;
queue<pair<int, pair<int, int>>> Q;
int dist[1002][1002]; // represents 2D distance
bitset<1002> G[1002];
char tmp;

int d;
short dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
pair<int, int> u, newu;
void bfs()
{
	Q.push(make_pair(0, make_pair(0, 0)));
	while (!Q.empty())
	{
		d = Q.front().first;
		u = Q.front().second;
		Q.pop();
		if (dist[u.first][u.second] != -1)
			continue;									 // If visited (distance has been set), continue
		dist[u.first][u.second] = d; // Set distance

		for (int i = 0; i < 4; i++)
		{
			newu = make_pair(u.first + dx[i], u.second + dy[i]);
			if (newu.first < 0 || newu.first >= H || newu.second < 0 || newu.second >= W)
				continue; // Don't go out of bounds
			if (G[newu.first][newu.second] == true)
				continue; //  Ignore if black - cannot step on black square
			Q.push(make_pair(d + 1, newu));
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dist, -1, sizeof(dist));
	cin >> H >> W;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> tmp;
			if (tmp == '.')
				G[i][j] = false;
			else
			{
				G[i][j] = true;
				blacks++;
			}
		}
	}

	bfs();
	// for (int i = 0; i < H; i++)
	// {
	// 	for (int j = 0; j < W; j++)
	// 		cout << dist[i][j] << " ";
	// 	cout << "\n";
	// }
	if (dist[H - 1][W - 1] == -1)
		cout << -1 << "\n"; // Impossible
	else
		cout << H * W - blacks - dist[H - 1][W - 1] - 1 << "\n";
}


Measured memory_bytes: 4224
package main

import (
	"fmt"
)

func main() {
	// input K N, K: 湖の円周 N: 家の件数
	var k, n int
	fmt.Scan(&k, &n)

	// input An, An: 家の位置(湖北端から時計回り)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	// 初期値で先頭と終端の距離を求めておく
	base := k - a[n-1] + a[0]
	for i := 0; i < n-1; i++ {
		// 家間での距離を測り、最大のものを保持する
		base = max(base, a[i+1] - a[i])
	}
	// 家間の距離が最大の区間を除いた距離が最短
	fmt.Println(k - base)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n;
    cin >> n;
    int ans = 0, A = 0, B = 0, AB = 0, BA = 0;
    rep(i, n)
    {
        string s;
        cin >> s;
        rep(i, s.size() - 1) if (s[i] == 'A' && s[i + 1] == 'B') ans++;
        if (s[0] == 'A' && s[s.size() - 1] == 'B')
            AB++;
        else if (s[0] == 'B' && s[s.size() - 1] == 'A')
            BA++;
        else if (s[0] == 'B')
            B++;
        else if (s[s.size() - 1] == 'A')
            A++;
    }
    if (BA > 0)
    {
        ans += (BA - 1);
        if (A > 0)
            ans++, A--;
        else if (AB > 0)
            ans++, AB--;
        if (B > 0)
            ans++, B--;
        else if (AB > 0)
            ans++, AB--;
    }
    int tmp = 0;
    rep(i, AB + 1) tmp = max(tmp, min(A + i, B + AB - i));
    ans += tmp;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
 
using namespace std;
 
typedef long long ll;
 
 
int add(int a, int b)
{
    int x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}
 
ll pw(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 cnt[100005];
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, k;
    cin >> n >> k;
    cnt[k] = 1;
    ll ans = k;
    for(int i = k-1; i >= 1; --i)
    {
        int rp = k/i;
        cnt[i] = pw(rp, n);
        for(int j = i+i; j <= k; j += i)
        {
            cnt[i] = cnt[i] + mod - cnt[j];
            if(cnt[i] >= mod)
                cnt[i] -= mod;
        }
        ans += 1LL * cnt[i] * i;
        ans %= mod;
    }
    cout << ans;
    return 0;
}

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

int main() {
	string s;
	cin >> s;
	int chk=0;
	int j;
	for (int i = 1; i <= 3; i++) {
		if (s[0] == s[i]) {
			j = i;
			chk++;
		}
	}
	if (chk != 1) {
		cout << "No" << endl;
	}
	else {
		if (j == 1) {
			if (s[2] == s[3]) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
		if (j == 2) {
			if (s[1] == s[3]) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
		if (j == 3) {
			if (s[1] == s[2]) {
				cout << "Yes" << endl;
			}
			else {
				cout << "No" << endl;
			}
		}
	}

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vector(N);
  rep(i, N){
  	cin >> vector.at(i);
  }
  sort(vector.begin(), vector.end());
  reverse(vector.begin(), vector.end());
  int sum = 0;
  rep(i, N){
    if(i % 2 == 0){
    	sum += vector.at(i);
    }
    if(i % 2 == 1){
    	sum -= vector.at(i);
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3604
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;

struct Road{
    int e,next;
}r[210000];int R[110000],num;
int f[110000],n,x,y;

void addr(int x,int y){
    r[++num]=(Road){y,R[x]};
    R[x]=num;
}

void dfs(int u,int fa){
    for(int i=R[u];i;i=r[i].next){
        int v=r[i].e;
        if(v==fa)continue;
        dfs(v,u);
        f[u]^=f[v]+1;
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        addr(x,y);addr(y,x);
    }dfs(1,0);
    if(f[1]==0)printf("Bob\n");
    else printf("Alice\n");
    return 0;
}

Measured memory_bytes: 7296
import sys
sys.setrecursionlimit(1000000)
 
N,A,B,C,D = map(int,input().split())
S = input()


if "##" in S[A-1:C] or "##" in S[B-1:D]:
    print('No')
    exit()

if C < D:
    print("Yes")
    exit()

if S[B-2] != "#" and S[B] == ".":
    print("Yes")
    exit()
    
if S[B-2] == "#" and S[B] == "." and S[B+1] == ".":
    print("Yes")
    exit()

for i in range(N):
    
    if i+B+2 >= N:
        print("No")
        exit()
    
    if i+B+2 > D:
        print("No")
        exit()
        
    if S[i+B] == "." and S[i+B+1] == "." and S[i+B+2] == ".":
        print("Yes")
        exit()



Measured memory_bytes: 3572
N=int(input())
s=input()
t=input()

ans=""
for i in range(N):
    ans=ans+s[i]

count=0

for i in range(N):
    flag=True
    for j in range(i+1):
        #print(s[N-1-i+j])
        if s[N-1-i+j]==t[j]:
            pass
        else:
            flag=False
    if flag:
        count=i+1
#print(count)
for i in range(count,N):
    ans=ans+t[i]

print(len(ans))

Measured memory_bytes: 38640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    int n, m;
    cin >> n >> m;
    int k = n;
    n = max(n, m);
    m = min(k, m);

    rep(i, n) cout << m;
    cout << endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> ans(n);
    for (int i=0; i<n-1; i++) {
        int a;
        cin >> a;
        ans[a-1]++;
    }
    for (int i=0; i<n; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4060
#include<stdio.h>
#include<math.h>
int main(){

	double x1,y1,x2,y2;
	double sq_x,sq_y;

	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	sq_x = pow((x1-x2),2);
	sq_y = pow((y1-y2),2);
	double distance = sqrt(sq_x+sq_y);
	printf("%.4lf\n",distance );
}


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

int a[105][105];

int main() {
	int h, w, n; cin >> h >> w >> n;

	int w_cnt = 0, h_cnt = 0;
	bool rev = false;
	for (int i = 0,tmp; i < n; i++) {
		cin >> tmp;
		while (tmp) {
			if (w_cnt == -1 || w_cnt == w) {
				rev = !rev;
				h_cnt++;
				w_cnt += w_cnt == w ? -1 : 1;
			}
			a[h_cnt][w_cnt] = i + 1;
			tmp--;
			w_cnt += (!rev ? 1 : -1);
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << a[i][j] << ' ';
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		StringBuilder builder = new StringBuilder();
		String line;
		Map<Integer, Integer> memo = new TreeMap<Integer, Integer>();
		while ((line = reader.readLine()) != null) {
			if (line.isEmpty()) {
				break;
			}
			int n = Integer.parseInt(line.split(",")[0]);
			Integer a = 0;

			if ((a = memo.get(n)) == null) {
				memo.put(n, 1);
			} else {
				memo.put(n, a + 1);
			}
		}
		Map<Integer, Integer> result = new TreeMap<Integer, Integer>();
		while ((line = reader.readLine()) != null) {
			if (line.isEmpty()) {
				break;
			}
			int n = Integer.parseInt(line.split(",")[0]);
			Integer a = 0;
			if ((a = result.get(n)) == null) {
				if ((a = memo.get(n)) != null) {
					result.put(n, a + 1);
				}
			} else {
				result.put(n, a + 1);
			}
		}
		for (Entry<Integer, Integer> entry : result.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

	}
}

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

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int infI=1e9+5;
const long long infL=1e16;
const int MOD=1e9+7;
const int MAX=5e5+5;

#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define pll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define forn(i,a,b) for(ll i=a;i<b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define popb pop_back()
#define se second
#define fi first
#define test(t) int t;cin>>t;while(t--)
#define debug(x) cerr<<"=>"<<#x<<" = "<<x<<endl

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    if(b==1){
        return a;
    }
    ll temp=power(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2){
        temp=(temp*a)%MOD;
    }
    return temp;
}

//only use if mod is prime
ll mod_inv(ll a,ll mod){
    a%=mod;
    return power(a,mod-2);
}

void extended_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    ll x1,y1;
    extended_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return;
}

//TLE can also occur if vectors are not passed by reference, debug statements can also cause TLE.
//priority_queue implements max heap by default

vector<int> seg[4*MAX];
int hi[4*MAX],lo[4*MAX],last[MAX];

void uptree(int st){
    int l = 2*st;
    int r = l+1;
    int indl=0,indr=0;
    while(indl<seg[l].size() and indr<seg[r].size()){
        if(seg[l][indl]<seg[r][indr]){
            seg[st].pb(seg[l][indl]);
            ++indl;
        }
        else{
            seg[st].pb(seg[r][indr]);
            ++indr;
        }
    }
    while(indl<seg[l].size()){
        seg[st].pb(seg[l][indl]);
        ++indl;
    }
    while(indr<seg[r].size()){
        seg[st].pb(seg[r][indr]);
        ++indr;
    }
}

void init(int st,int l,int r){
    seg[st].clear();
    hi[st] = r;
    lo[st] = l;
    if(l == r){
        seg[st].pb(last[l]);
        return;
    }
    int mid = (l+r)/2;
    init(2*st,l,mid);
    init(2*st+1,mid+1,r);
    uptree(st);
}

int query(int st,int l,int r){
    if(hi[st]<l or lo[st]>r){
        return 0;
    }
    if(hi[st]<=r and lo[st]>=l){
        // cout<<lo[st]<<" "<<hi[st]<<" "<<lower_bound(seg[st].begin(),seg[st].end(),l)-seg[st].begin()<<endl;
        return lower_bound(seg[st].begin(),seg[st].end(),l)-seg[st].begin();
    }
    return query(2*st,l,r)+query(2*st+1,l,r);
}

int main(){
    fastio;
    // think about edge cases like n=1(especially graph questions).
    int n,q;
    cin>>n>>q;
    vi a(n+1,0);
    forn(i,1,n+1){
        cin>>a[i];
    }
    map<int,int> fnd;
    forn(i,1,n+1){
        last[i] = (fnd.find(a[i])!=fnd.end()?fnd[a[i]]:-1);
        fnd[a[i]] = i;
    }
    init(1,1,n);
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<query(1,l,r)<<endl;
    }
    return 0;
}

Measured memory_bytes: 151104
#AGC014A
import sys

a,b,c=map(int,raw_input().split())
if a%2 or b%2 or c%2:
 print 0
 sys.exit()
if a==b and b==c:
 print -1
 sys.exit()

i=0
while True:
 ta=(b+c)/2
 tb=(c+a)/2
 tc=(a+b)/2
 a=ta
 b=tb
 c=tc
 i+=1
 if a%2 or b%2 or c%2:
  print i
  break


Measured memory_bytes: 2568
import java.util.Scanner;

class Main {
public static void main (String[] args){
Scanner sc = new Scanner(System.in); 
int S = sc.nextInt();
if (S >= 0 && S < 86400){
int h = S / 3600;
int m = S % 3600 / 60;
int s = S % 3600 % 60;
System.out.println(h + ":" + m + ":" + s);
}
}
}



Measured memory_bytes: 26124
H, W = map(int, input().split())
Ss = []
for i in range(H):
    S = list(input())
    Ss.append(S)

seq = 0
w_bright_cell = [[0]*W for i in range(H)]
for i in range(H):
    seq = 0
    for j in range(W):
        if Ss[i][j] == "#":
            seq = 0
            w_bright_cell[i][j] = -1
            continue
        seq += 1
        w_bright_cell[i][j] = seq
    
    obstacle_flag = True
    for j in range(W-1, -1, -1):
        if w_bright_cell[i][j] == -1:
            obstacle_flag = True
            continue
        if obstacle_flag:
            obstacle_flag = False
            seq = w_bright_cell[i][j]
            continue
        w_bright_cell[i][j] = seq

seq = 0
h_bright_cell = [[0]*W for i in range(H)]
for j in range(W):
    seq = 0
    for i in range(H):
        if Ss[i][j] == "#":
            seq = 0
            h_bright_cell[i][j] = -1
            continue
        seq += 1
        h_bright_cell[i][j] = seq

    obstacle_flag = True
    for i in range(H-1, -1, -1):
        if h_bright_cell[i][j] == -1:
            obstacle_flag = True
            continue
        if obstacle_flag:
            obstacle_flag = False
            seq = h_bright_cell[i][j]
            continue
        h_bright_cell[i][j] = seq

now_max = 0
for i in range(H):
    for j in range(W):
        h = h_bright_cell[i][j]
        w = w_bright_cell[i][j]
        now_max = max((now_max, h+w))

print(now_max-1)

Measured memory_bytes: 244488
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <bitset>
#include <vector>

#define MAX_N (5000)
#define MAX_K (5000)

using namespace std;

int main(int argc, char *argv[]) {
  // read inputs
  int N, K, as[MAX_N];
  scanf("%d %d", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%d", &as[i]);
  }

  vector<bitset<MAX_K>> dp1ss(N + 1, bitset<MAX_K>()),
      dp2ss(N + 1, bitset<MAX_K>());
  vector<vector<int>> dp3ss(N + 1, vector<int>(K + 1, 0));
  // calculate dp1ss
  // initialize
  for (int k = 0; k < K; k++) {
    dp1ss[0][k] = k == 0 ? 1 : 0;
  }
  // update
  for (int i = 0; i < N; i++) {
    const int a = as[i];
    for (int k = 0; k < K; k++) {
      int dp = 0;
      dp = dp || dp1ss[i][k];
      dp = dp || (k - a >= 0 && dp1ss[i][k - a]);
      dp1ss[i + 1][k] = dp;
    }
  }
  // printf("dp1ss\n");
  // for (int i = 0; i <= N; i++) {
  //   printf("i = %d:", i);
  //   for (int k = 0; k < K; k++) {
  //     printf(" %d", dp1ss[i][k]);
  //   }
  //   printf("\n");
  // }
  // calculate dp2ss
  // initialize
  for (int k = 0; k < K; k++) {
    dp2ss[N][k] = k == 0 ? 1 : 0;
  }
  // update
  for (int i = N - 1; i >= 0; i--) {
    const int a = as[i];
    for (int k = 0; k < K; k++) {
      int dp = 0;
      dp = dp || dp2ss[i + 1][k];
      dp = dp || (k - a >= 0 && dp2ss[i + 1][k - a]);
      dp2ss[i][k] = dp;
    }
  }
  // printf("dp2ss\n");
  // for (int i = 0; i <= N; i++) {
  //   printf("i = %d:", i);
  //   for (int k = 0; k < K; k++) {
  //     printf(" %d", dp2ss[i][k]);
  //   }
  //   printf("\n");
  // }
  // calculate dp3ss
  for (int i = 1; i <= N; i++) {
    const int a = as[i - 1];
    int cnt = 0;
    for (int k = 0; k <= K; k++) {
      // printf("i = %d, k = %d\n", i, k);
      if (k - 1 >= 0 && dp2ss[i][k - 1]) {
        // printf("increment\n");
        cnt++;
      }
      if (k - a - 1 >= 0 && dp2ss[i][k - a - 1]) {
        // printf("decrement\n");
        cnt--;
      }
      dp3ss[i][k] = cnt;
    }
  }
  // printf("dp3ss\n");
  // for (int i = 0; i < N; i++) {
  //   printf("i = %d:", i);
  //   for (int k = 0; k <= K; k++) {
  //     printf(" %d", dp3ss[i][k]);
  //   }
  //   printf("\n");
  // }

  // solve
  int ans = N;
  for (int i = 0; i < N; i++) {
    const int a = as[i];
    for (int k = 0; k < K; k++) {
      if (dp1ss[i][k] && (dp3ss[i + 1][K - k] > 0)) {
        // printf("as[%d] = %d is needed, k = %d\n", i, as[i], k);
        ans--;
        break;
      }
    }
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 104320
// Problem : B - Distance 
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x 



void solve()
{
	int n ,d;
	cin>>n>>d;
	int  ans=0;
	int res=0;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		ans=x*x+y*y;
		if(ans<=d*d)
		 res++;
	}
	cout<<res<<endl;
	
}



int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 3660
import qualified Data.IntMap as M

main = do
  li <- getLine
  let [n,m] = map read $ words li
  li <- getLine
  let as = map read $ words li
  let ans = compute n m as
  print ans

{-
IntMapのheap的能力
deleteFindMax :: IntMap a -> ((Key, a), IntMap a)
insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
で券がなくなるまでどんどん半額にしていく。
-}

compute :: Int -> Int -> [Int] -> Int
compute n m as = sum $ map (uncurry (*)) $ loop m am
  where
    am = M.fromListWith (+) [ (a,1) | a <- as ]
    loop m am
      | m > c = loop (m-c) $ M.insertWith (+) (div x 2) c am1
      | True  = (div x 2, m) : (x, c - m) : M.assocs am1
      where
        ((x,c),am1) = M.deleteFindMax am

Measured memory_bytes: 54652
A,B,C,K= map(int, input().split())
res = 0

if K <= A:
    print(K)
    exit( )
else:
    res += A
    K = K-A

if K <= B:
    print(res)
    exit( )
else:
    K = K-B

if K <= C:
    res -= K
    print(res)
    exit( )
else:
    res += C
    print(res)

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

struct UnionFind {
    vector<int> par, rank;
    UnionFind(int n = 1) {
        init(n);
    }
    void init(int n = 1) {
        par.resize(n + 1);
        rank.resize(n + 1);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }
    int root(int x) {
        if(par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        par[x] = y;
        return true;
    }
};
int R[100500], C[100500];
bool r[100500], c[100500];
int main() {
    int N;
    cin >> N;
    UnionFind uni(N + 1);
    for(int i = 1; i <= N; i++) {
        cin >> R[i] >> C[i];
        if(r[R[i]] or c[C[i]]) {
            cout << -1 << endl;
            return 0;
        }
        r[R[i]] = true;
        c[C[i]] = true;
        uni.merge(R[i], C[i]);
    }
    int ans = N;
    for(int i = 1; i <= N; i++) {
        if(uni.root(i) == i) ans--;
        //cerr << uni.root(i) << endl;
    }
    cout << ans << endl;
}


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

struct UnionFind{
    vector<int> parent,size;
    
    UnionFind(int n): parent(n,-1),size(n,1){}
    void init(int n){ 
        parent.assign(n,-1);
        size.assign(n,1);
        return;
    }

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

    bool same(int x, int y){
        return root(x)==root(y);
    }

    void unite(int x,int y){
        int gx = root(x);
        int gy = root(y);
        if (gx==gy) return;
        else{
            if(size[gx]<size[gy]){
                size[gy]+=size[gx];
                parent[gx]=gy;
            } else{
                size[gx]+=size[gy];
                parent[gy]=gx;
            }
        }
    }
    int get_size(int x){
        return size[root(x)];
    }    
};

struct edge{
    int u,v;
    ll cost;
};

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

edge es[1000000];
int V,E;

ll kruskal(){
    sort(es,es+E,comp);
    UnionFind UF = UnionFind(V);
    ll res = 0;
    FOR(i,0,E){
        edge e = es[i];
        if (!UF.same(e.u,e.v)){
            UF.unite(e.u,e.v);
            res += e.cost;
        }
    }
    return res;
}

int main(){
    int N; cin >> N;
    vector<pair<pair<int,int>,int> > v(N),w(N);
    int x,y;
    FOR(i,0,N){
        cin >> x >> y;
        v[i] = make_pair(make_pair(x,y),i);
        w[i] = make_pair(make_pair(y,x),i);
    }
    V = N;
    E = 2 * (N-1);
    sort(v.begin(),v.end());
    sort(w.begin(),w.end());
    FOR(i,0,N-1){
        es[i].u = v[i].second;
        es[i].v = v[i+1].second;
        es[i].cost = (ll) min(abs(v[i+1].first.first-v[i].first.first),abs(v[i+1].first.second-v[i].first.second));
        es[i+N-1].u = w[i].second;
        es[i+N-1].v = w[i+1].second;
        es[i+N-1].cost = (ll) min(abs(w[i+1].first.first-w[i].first.first),abs(w[i+1].first.second-w[i].first.second));

    }
    ll ans = kruskal();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7424
#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  
  int diff = b - a;
  
  int sum = 0;
  for (int i = 1; i < diff; i++) {
    sum += i;
  }
  
  sum -= a;
  
  cout << sum << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import fractions

N,M=map(int,input().split())
A=list(map(int,input().split()))

have2=[0]*len(A)

for index,item in enumerate(A):
    while item%2==0:
        item/=2
        have2[index]+=1

if len(list(set(have2)))!=1:
    print(0)
    exit()

f=0
f2=1
for item in A:
    f=fractions.gcd(f2,item)
    f2=f2*item//f
if M>=f2//2:
    M-=f2//2
    print(max(M//f2+1,0))
else:
    print(0)


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

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b, k;
  cin >> a >> b >> k;
  set<int> s;
  for(int i=0; i<k && a+i<=b; i++) s.insert(a + i);
  for(int i=0; i<k && b-i>=a; i++) s.insert(b - i);
  vector<int> tmp;
  for(auto x : s) tmp.push_back(x);
  sort(tmp.begin(), tmp.end());
  for(auto x : tmp) cout << x << endl;
  return 0;
}


Measured memory_bytes: 256
s = input()

while s:
    if s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "erase":
        s = s[5:]
    elif s[:5] == "dream":
        if s[5:8] == "era":
            s = s[5:]
        elif s[5:7] == "er":
            s = s[7:]
        else:
            s = s[5:]
    else:
        print("NO")
        exit()
print("YES")

Measured memory_bytes: 3188
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

bool isprime[1000];

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

  ll n;
  cin >> n;

  //素数ならtrue
  memset(isprime, true, sizeof(isprime));
  isprime[0] = isprime[1] = false;
  for (int i = 2; i * i <= 1000; i++) {
    if (isprime[i]) {
      for (int j = 2 * i; j <= 1000; j += i) {
        isprime[j] = false;
      }
    }
  }

  // n!の素因数分解
  ll cnt[105] = {};
  FOR(i, 1, n+1) {
    ll t = i;
    FOR(j, 2, i+1) {
      while(t%j == 0) {
        cnt[j]++;
        t /= j;
      }
    }
  }

  ll ret = 0;
  // p^4 * q^4 * r^2
  REP(p, n+1) REP(q, n+1) REP(r, n+1) {
    if(!isprime[p] || !isprime[q] || !isprime[r] || p >= q) continue;
    if(p == r || q == r) continue;
    if(cnt[p] >= 4 && cnt[q] >= 4 && cnt[r] >= 2) {
      ret++;
    }
  }

  // p^14 * q^4
  REP(p, n+1) REP(q, n+1) {
    if(!isprime[p] || !isprime[q]) continue;
    if(p == q) continue;
    if(cnt[p] >= 14 && cnt[q] >= 4) {
      ret++;
    }
  }

  // p^24 * q^2
  REP(p, n+1) REP(q, n+1) {
    if(!isprime[p] || !isprime[q]) continue;
    if(p == q) continue;
    if(cnt[p] >= 24 && cnt[q] >= 2) {
      ret++;
    }
  }

  // p^74
  REP(p, n+1) {
    if(!isprime[p]) continue;
    if(cnt[p] >= 74) {
      ret++;
    }
  }

  cout << ret << endl;

  return 0;
}


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

int main() {
    int n;
    std::cin >> n;

    std::vector<int> h(n);
    for(int i = 0; i < n; ++i) {
        std::cin >> h[i];
    }

    std::vector<int> dp(n);
    dp[0] = 0;
    dp[1] = std::abs(h[0] - h[1]);
    for(int i = 2; i < n; ++i) {
        dp[i] = std::min(dp[i - 2] + std::abs(h[i - 2] - h[i]),
                         dp[i - 1] + std::abs(h[i - 1] - h[i]));
    }

    std::cout << dp[n - 1] << "\n";
}

Measured memory_bytes: 1024
require 'prime'

n = gets.chomp.to_i
ans = 0
# n, m = gets.chomp.split(" ").map(&:to_i)

prime = Prime.prime_division(n)

prime.each do |arr|
  i = 1
  while 2*arr[1] >= i**2+i do
    i+=1
  end
  ans += i-1
end

puts ans

Measured memory_bytes: 14444
n=int(input())
satis=[]

for i in range(n):
	satis.extend(map(int,input().split()))

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

Measured memory_bytes: 15024