akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <string>
#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

map<string,int> mp;
int direction[4]={1,-1,4,-4};

void bfs(){
    string now,s;
    queue<string> q;
    mp["01234567"]=0;
    q.push("01234567");
    while(q.size()){
        int index;
        now=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            if(now[i]=='0'){
                index = i; break;
            }
        }
        for(int i=0;i<4;i++){
            int nx = index+direction[i];
            if(0<=nx&&nx<8&&!(index==3&&i==0)&&!(index==4&&i==1)){
                string next = now;
                swap(next[index],next[nx]);
                if(mp.find(next)==mp.end()){
                    mp[next]=mp[now]+1;
                    q.push(next);
                }
            }
        }
    }
}

void solve(){
    string s;
    bfs();
    while(getline(cin,s)){
        s.erase( remove(s.begin(),s.end(),' ') , s.end() );
        printf("%d\n",mp[s]);
    }
}

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




Measured memory_bytes: 5448
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int x,y;
cin >> x;
if(x==3||x==5||x==7) {
  cout << "YES" << endl;
} else {
  cout << "NO" << endl;
}
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    ll res = 0;
    map<ll,ll> cnt;
    cnt[0]++;
    ll sum = 0;
    ll rest = 0;
    for(ll i= 0;i<n;i++){
	if( i == k-1 ){
	    cnt[0]--;
	}
	if( i >= k ){
	    //cnt[rest]--;
	    rest += a[i-k]-1;
	    rest %= k;
	    cnt[rest]--; 
	}
	sum += a[i]-1;
	sum %= k;
	res += cnt[ sum ];// sum % k == 0個を知りたい
	cnt[ sum ]++;// 今何個
	//cout<<" "<<a[i]<<endl;
	//for(auto i:cnt)cout<<i.first<<' '<<i.second<<endl;
    }

    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 14336
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < (int)n;i++)
#define repb(i, n) for(int i = (int)n;i >= 0;i--)
#define reps(i, m, n) for(int i = (int)m;i < (int)n;i++)
#define repsb(i, m, n) for(int i = (int)m;i >= (int)n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define INF 999999999999999999
using namespace std;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
using namespace std;
std::vector<int> v;
int main(int argc, char const *argv[]) {
  int x,y,mini,maxi;
  while (true){
    cin>>x>>y;
    if(x==0&&y==0)  return 0;
    maxi=max(x,y);
    mini=min(x,y);
    cout<<mini<<" "<<maxi<<endl;
  }
 return 0;
}



Measured memory_bytes: 3016
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    VI a(n); REP(i,n) cin >> a[i];
    out(MAX(a)-MIN(a));

    return 0;
}

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

#define mp make_pair
#define eb emplace_back
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#endif


const int MAXN = 100;
//#define int long long
const int INF = 1e9;

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder


void solve(){
  int n, q;
  cin >> n >> q;
  int c, u, v;
  atcoder::dsu dsu(n + 1);
  for (int i = 0; i < q; i++){
    cin >> c >> u >> v;
    if (!c) dsu.merge(u, v);
    else {
      if (dsu.same(u, v)) cout << "1\n";
      else cout << "0\n";
    }
  }
}

signed main()
{
    #ifdef FILEIO
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif

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

    solve();

    return 0;
}


Measured memory_bytes: 3840
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
using int64 = long long;

int main() {
  int W, a, b;
  cin >> W >> a >> b;
  int move = abs(a - b) - W;
  if (move < 0) {
    move = 0;
  }
  cout << move << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

int f(int a, int b){
  b = b-a;
  a %= 3; b %= 3;
  int aa = 0, bb = 0;
  if(a == 1) aa++;
  if(a == 2) bb++;
  if(b == 1) bb++;
  if(b == 2) aa++;
  
  if(aa == 0){
    if(bb == 0) return 0;
    if(bb == 1) return 2;
    if(bb == 2) return 1;
  }
  if(aa == 1){
    if(bb == 0) return 1;
    if(bb == 1) return 0;
    if(bb == 2) return 2;
  }
  if(bb == 0) return 2;
  if(bb == 1) return 1;
  return 3;
}

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

  int N = s.size();
  int M = t.size();
  vector<int> ss(N+1, 0);
  vector<int> tt(M+1, 0);

  REP(i, N) ss[i+1] += ss[i]+((s[i] == 'A')? 1: 0);
  REP(i, M) tt[i+1] += tt[i]+((t[i] == 'A')? 1: 0);

  int q;
  cin >> q;

  REP(i, q){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(f(ss[b]-ss[a-1], b-a+1) == f(tt[d]-tt[c-1], d-c+1)) YES;
    else NO;
  }

  return 0;
}

Measured memory_bytes: 2512
n = gets.to_i
s = n % 10

if s == 2 || s == 4 || s == 5 || s == 7 || s == 9
    puts "hon"
elsif s == 0 || s == 1 || s == 6 || s == 8
    puts "pon"
else
    puts "bon"
end

Measured memory_bytes: 14176
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int Q;
    cin >> Q;
    
    vector<int> S(100001, 0);
    vector<int> p;
    p.push_back(2);
    for(int i=3; i<100001; i++) {
        S[i] += S[i-1];
        for(int pi=0; pi<p.size(); pi++) {
            if(i%p[pi]) {
                ;
            } else {
                break;
            }
            if(pi==p.size()-1) {
                // if(i<8) cout << "i = " << i << ": ";
                for(int pii=0; pii<p.size(); pii++) {
                    if(((i+1)/2)>p[pii]) {
                        if(((i+1)/2)%p[pii]) {
                            ;
                        } else {
                            break;
                        }
                    } else {
                        pii=p.size()-1;
                    }
                    if(pii==p.size()-1) {
                        S[i]++;
                    }
                }
                // if(i<8) cout << S[i] << endl;
                p.push_back(i);
            }
        }
    }
    
    for(int q=0; q<Q; q++) {
        int l, r;
        cin >> l >> r;
        cout << S[r]-S[l-1] << endl;
    }

    return 0;
    
}

Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
using namespace std;
int n;long a[1<<18];
pair<long,int>dp[1<<18];
main()
{
	cin>>n;
	for(int i=0;i<1<<n;i++)cin>>a[i];
	dp[0]=make_pair(a[0],0);
	for(int i=1;i<1<<n;i++)
	{
		dp[i]=make_pair(a[i],i);
		for(int j=0;j<n;j++)if(i&(1<<j))dp[i]=max(dp[i],dp[i&~(1<<j)]);
	}
	long ans=0;
	for(int i=1;i<1<<n;i++)
	{
		long A=dp[i].second==i?0:a[i];
		for(int j=0;j<n;j++)
		{
			if((i&(1<<j))&&dp[i]!=dp[i&~(1<<j)])A=max(A,dp[i&~(1<<j)].first);
		}
		ans=max(ans,dp[i].first+A);
		cout<<ans<<endl;
	}
}


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

int main()
{   int n,m,a;
    while(~scanf("%d %d %d",&n,&m,&a))
    {
            if(n+m>a&&a>n)
            {
                printf("YES\n");

            }
            else if(a==n)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");

            }
    }
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int A[1000000], n;

/* 二分探索 */
int binarySearch(int key) {
  int left = 0;
  int right = n;
  int mid;
  while(left < right) {
    mid = (left + right) / 2;
    if(key == A[mid]) return 1; /* keyを発見 */
    if(key > A[mid]) left = mid + 1; /* 後半を探索 */
    else if(key < A[mid]) right = mid; /* 前半を探索 */
  }
  return 0;
}

int main(void) {
  int i, q, k, sum = 0;
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++) {
    scanf("%d",&k);
    if(binarySearch(k))
      sum++;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2128
#include<bits/stdc++.h>
using namespace std;
int a,b,c,k,ans;
int main(){
	cin >> a >> b >> c >> k;
	if (k <= a)
		ans = k;
	else if (k <= a + b)
			ans = a;
		 else
		 	ans = a - (k - a - b);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3604
n = int(input())

INF = 2147483647
G = [[INF for j in range(n)] for i in range(n+1)]
check = [0 for i in range(n)]


def prim():
    d = [INF for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    cost = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and d[i] < min_cost:
                min_cost = d[i]
                u = i

        if min_cost == INF:
            break

        cost += d[u]
        check[u] = 2

        for v in range(n):
            if check[v] != 2 and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    check[v] = 1

    return cost


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] != -1:
                G[i][j] = data[j]

    print(prim())


if __name__ == '__main__':
    main()



Measured memory_bytes: 5728
#include <stdio.h>
int main()
{
 int i,j,cd,cr;
 while(1)
 {
   scanf("%d%d", &cd, &cr);
   if(cd==0 && cr==0)
    return 0;
   for(i=0; i<cd; i++)
   {
    for(j=0; j<cr; j++)
    {
     if(i>0 && j>0 && i<cd-1 && j<cr-1)
      printf(".");
     else printf("#");
    }
    printf("\n");
   }
   printf("\n");
  }
return 0;
}

Measured memory_bytes: 572
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt(); //day
            int b = sc.nextInt(); // payment
            if (map.containsKey(a)) {
                map.get(a).add(b);
            } else {
                PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
                pq.add(b);
                map.put(a, pq);
            }
        }
        PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> y.amount - x.amount);
        long count = 0;
        for(int i = 1; i <= m; i++) {
            if (map.containsKey(i)) {
                PriorityQueue<Integer> queue = map.get(i);
                if (queue.peek() != null) {
                    pq.add(new Pair(i, queue.poll()));
                }
            }
            if (!pq.isEmpty()) {
                Pair p = pq.poll();
                count += p.amount;
                PriorityQueue<Integer> queue = map.get(p.index);
                if (!queue.isEmpty()) {
                    pq.add(new Pair(p.index, queue.poll()));
                }
            }
        }
        System.out.println(count);
    }

    public static class Pair {
        int index;
        int amount;
        Pair(int index, int amount) {
            this.index = index;
            this.amount = amount;
        }
    }

}



Measured memory_bytes: 107492
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)

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

int n,k,i,mini,donat,ar[103];

int main(){
    ios_base::sync_with_stdio(false);

    cin>>n>>k; mini=9999;
    for(i=0;i<n;i++){
        cin>>ar[i];
        mini=min(ar[i],mini);
    }
    sort(ar,ar+n); donat=0;
    for(i=0;i<n;i++){
        if(k-ar[i]>=0){donat++; k-=ar[i];}
    }
    cout<<donat+(k/mini)<<"\n";

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#define llint long long

using namespace std;
typedef pair<llint, pair<llint, llint> > E;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

struct node{
	llint w, sum, sz, left, right, id;
	node(){
		w = left = right = -1;
	};
};

llint n, m;
llint x[100005];
vector<E> e, rem;
UnionFind uf(100005), uf2(100005);

vector<llint> vec;
llint s[100005];

llint rt[100005];
vector<node> tree;

void dfs2(llint v){
	if(tree[v].w == -1) return;
	vec.push_back(tree[v].id);
	dfs2(tree[v].left), dfs2(tree[v].right);
}


llint dfs(llint v)
{
	if(tree[v].w == -1) return 0;
	if(tree[v].sum >= tree[v].w){
		dfs2(v);
		return tree[v].sz-1;
	}
	return dfs(tree[v].left) + dfs(tree[v].right);
}


int main(void)
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> x[i];
	llint a, b, y;
	for(int i = 1; i <= m; i++){
		cin >> a >> b >> y;
		e.push_back(make_pair(y, make_pair(a, b)));
	}
	sort(e.begin(), e.end());
	
	for(int i = 1; i <= n; i++){
		tree.push_back(node());
		tree.back().sz = 1;
		tree.back().sum = x[i];
	}
	for(int i = 1; i <= n; i++) rt[i] = i-1;
	
	llint ans = 0;
	for(int i = 0; i < e.size(); i++){
		int u = e[i].second.first, v = e[i].second.second, w = e[i].first;
		if(uf.same(u, v)){
			rem.push_back(e[i]);
			continue;
		}
		tree.push_back(node());
		tree.back().id = i;
		tree.back().w = w;
		tree.back().left = rt[uf.root(u)];
		tree.back().right = rt[uf.root(v)];
		tree.back().sum = tree[tree.back().left].sum + tree[tree.back().right].sum;
		tree.back().sz = tree[tree.back().left].sz + tree[tree.back().right].sz;
		uf.unite(u, v);
		rt[uf.root(u)] = tree.size()-1;
	}
	
	/*for(int i = 0; i < tree.size(); i++){
		cout << i << " : " << tree[i].left << " " << tree[i].right << " " << tree[i].w << " " << tree[i].sum << " " << tree[i].sz << endl;
	}*/
	
	
	set<int> S;
	for(int i = 1; i <= n; i++) S.insert(uf.root(i));
	for(auto it = S.begin(); it != S.end(); it++) ans += (tree[rt[*it]].sz-1) - dfs(rt[*it]);
	
	//cout << ans << endl;
	
	for(int i = 1; i <= n; i++) s[i] = x[i];
	for(int i = 0; i < vec.size(); i++){
		E edge = e[vec[i]];
		int u = edge.second.first, v = edge.second.second, w = edge.first;
		s[uf2.root(v)] += s[uf2.root(u)];
		uf2.unite(u, v);
	}
	for(int i = 0; i < rem.size(); i++){
		int u = rem[i].second.first, v = rem[i].second.second, w = rem[i].first;
		if(!uf2.same(u, v) || s[uf2.root(u)] < w) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 19692
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
for i in range(n):
    d = min(a[i], b[i])
    ans += d
    b[i] -= d
    d = min(a[i+1], b[i])
    a[i+1] -= d
    ans += d
    
print(ans)


Measured memory_bytes: 24232
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    int a, b; char c;
    scanf("%lld %c %lld", &a, &c, &b);
    if(c == '+') cout << a + b << endl;
    else cout << a - b << endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 1000005;
const LL MOD = 1e9+7;

LL r1, c1, r2, c2, fac[N<<1];

LL fpow(LL bs, LL idx){
    LL res = 1;
    bs %= MOD;
    while(idx){
        if(idx & 1) (res *= bs) %= MOD;
        idx >>= 1;
        (bs *= bs) %= MOD;
    }
    return res;
}
inline LL inv(LL x){ return fpow(x, MOD - 2); }
inline LL C(LL x, LL y){ return fac[x] * inv(fac[y]) % MOD * inv(fac[x-y]) % MOD; }
inline LL getVal(LL r, LL c){
    LL res = 0;
    for(int i = 1; i <= c + 1; i++)
        (res += C(r + i, i)) %= MOD;
    return res % MOD;
}

int main(){
    fac[0] = 1;
    for(int i = 1; i <= 2e6+100; i++)
        fac[i] = (fac[i-1] * (LL)i) % MOD;
    read(r1, c1, r2, c2);
    LL ans = getVal(r2, c2) - getVal(r1-1, c2) - getVal(r2, c1-1) + getVal(r1-1, c1-1);
    ((ans %= MOD) += MOD) %= MOD;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 15872
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

(deftype int32 () '(signed-byte 32))
(deftype int64 () '(signed-byte 64))


;;macros
(defmacro println (n)
  `(format t "~a~%" ,n))
(defmacro vint-out (vec)
  `(progn
     (rep i (length ,vec)
          (princ (vref ,vec i))
          (princ " "))
     (fresh-line)))


;;vector
(defmacro vec (type &optional (num 100) (val 0))
  (let* ((g (gensym)))
    `(let* ((,g ,num))
       (make-array ,g :element-type ',type :initial-element ,val
                   :adjustable nil :fill-pointer ,g))))

(defmacro double-vec (type &optional (dim1 100) (dim2 100) (val 0))
  `(make-array '(,dim1 ,dim2) :element-type ',type :initial-element ,val))

(defmacro vint (&optional (num 0) (val 0))
  `(vec int32 ,num ,val))

(defmacro double-vec (type &optional (dim1 100) (dim2 100) (val 0))
  `(make-array '(,dim1 ,dim2) :element-type ',type :initial-element ,val))

(defmacro vref (vector pos &optional value)
  (let ((g (gensym)))
    `(let ((,g ,value))
       (if ,g
           (setf (aref ,vector ,pos) ,g)
           (aref ,vector ,pos)))))

(defmacro chvar (sym comp predicate)
  (let ((g (gensym)))
    `(let ((,g ,comp))
       (if (or (null ,sym) (not (funcall ,predicate ,sym ,g)))
           (setf ,sym ,g)))))

(defmacro chmax (sym comp &optional (predicate #'>))
  `(chvar ,sym ,comp ,predicate))

(defmacro chmin (sym comp &optional (predicate #'<))
  `(chvar ,sym ,comp ,predicate))

(defmacro defchangef (name op default-val)
  `(defmacro ,name (var &optional (val ,default-val))
     `(setq ,var (,',op ,val ,var))))

;;本体
(defun main()
  (let* ((a (read)) (b (read))
         (height (loop for i below (- b a) sum i)))
    (println (- height a))))

#-swank(main)


Measured memory_bytes: 16100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (2e9)

int main() {
  ll ans = 0;
  ll n, p; cin >> n >> p;
  string s; cin >> s;

  if(10 % p == 0) {
    for(int i = s.length() - 1; i >= 0; i--) {
      if((s[i]-'0') % p == 0) ans += i + 1;
    }
    cout << ans << endl;
    return 0;
  }

  vector<ll> sum(n+1);
  ll ten = 1;
  for(int i = n - 1; i >= 0; i--) {
    ll a = (s[i]-'0') * ten % p;
    sum[i] = (sum[i+1] + a) % p;
    ten *= 10; ten %= p;
  }
  vector<ll> cnt(p);
  for(int i = n; i >= 0; i--) {
   cnt[sum[i]]++;
  }
  for(auto i = cnt.begin(); i != cnt.end(); i++) {
    ans += *i * (*i - 1) / 2;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2180
#include <stdio.h>

int main()
{
    int n;
    char s[4001];
    int rgb_buc[3][4001] = {0},rgb[] = {'R','G','B'};
    scanf("%d %s",&n,s);

    int i,j,k;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < 3; j++)
        {
            if(rgb[j] == s[i]){rgb_buc[j][i + 1] = 1;break;}
        }
    }

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < 3; j++)
        {
            rgb_buc[j][i + 1] += rgb_buc[j][i];
        }
    }

    long long ans = 0,buf = 0;
    char ii,jj;
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if(s[i] == s[j])continue;
            for (k = 0; k < 3; k++)
            {
                if(rgb[k] == (int)'R' + 'G' + 'B' - s[i] - s[j])break;
            }
            
            buf = rgb_buc[k][n] - rgb_buc[k][j + 1];
            if(2 * j - i <= n)if(buf != 0 && (int)s[2 * j - i] == (int)'R' + 'G' + 'B' - s[i] - s[j])buf--;
            
            ans += buf;
        }
    }
    printf("%lld",ans);
}

//'R' + 'G' + 'B'

Measured memory_bytes: 1776
#include <bits/stdc++.h>
#define R real()
#define I imag()
using namespace std;
typedef complex <double> point;
struct S{
  double x,y,z,r;
  S(){x=y=z=r=0;}
  S(double x,double y,double z,double r):x(x),y(y),z(z),r(r){};
};

S s[2001],b[20],E;
vector <int> B[20];

double get_dis(S a,S b){
  a.x-=b.x,a.y-=b.y,a.z-=b.z;
  return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
}

bool check(S s,S p){
  S res;
  point A=point(s.x,s.y),B=point(p.x,p.y);
  if(abs(A))B*=(conj(A)/abs(A));
  res.y=B.I;

  A=point(abs(A),s.z),B=point(B.R,p.z);
  if(abs(A))B*=(conj(A)/abs(A));
  res.x=B.R,res.z=B.I;
  
  double X=get_dis(s,S(0,0,0,0)),r=0;
  if(res.x<0) r=get_dis(res,S(0,0,0,0));
  else if(X<res.x) r=get_dis(res,S(X,0,0,0));
  else r=sqrt(res.z*res.z+res.y*res.y);
  if(max(get_dis(res,S(0,0,0,0)),get_dis(res,S(X,0,0,0)))<=p.r)return 0;
  return p.r>=r;
  
}

double cal(S a){return a.r/((a.x*a.x)+(a.y*a.y)+(a.z*a.z));}

int main(){
  int n,m,r;
  while(1){
    cin>>n>>m>>r;
    if(!n&&!m&&!r)break;

    for(int i=0;i<n;i++)cin>>s[i].x>>s[i].y>>s[i].z>>s[i].r;
    for(int i=0;i<m;i++)cin>>b[i].x>>b[i].y>>b[i].z>>b[i].r;
    cin>>E.x>>E.y>>E.z;
    for(int i=0;i<n;i++)s[i].x-=E.x,s[i].y-=E.y,s[i].z-=E.z;
    for(int i=0;i<m;i++)b[i].x-=E.x,b[i].y-=E.y,b[i].z-=E.z;

    for(int i=0;i<m;i++){
      B[i].clear();
      for(int j=0;j<n;j++)
	if(check(b[i],s[j]))B[i].push_back(j);
    }


    double ans=0;
    for(int i=0;i<(1<<m);i++){
      int used[2001]={},cnt=0;
      double sum=0;
      for(int j=0;j<m;j++){
	if(!((i>>j)&1))continue;
	for(int k=0;k<B[j].size();k++)cnt+=!used[B[j][k]],used[B[j][k]]=1;
	if(cnt>r)break;
	sum+=cal(b[j]);
      }
      ans=max(ans,sum);
    }
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1488
from math import inf
import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [inf] * n
for a in A:
    j = bisect.bisect_left(dp, a)
    dp[j] = a
ans = 0
for i in range(n):
    if dp[i] != inf:
        ans = i
print(ans + 1)



Measured memory_bytes: 10444
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        
        int a = scan.nextInt();
        int b =scan.nextInt();
        
        System.out.print(a*b+" ");
        System.out.println(2*a+2*b);
             
    }
}



Measured memory_bytes: 26204
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>


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; }
//constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
const long double PI = acos((long double)(-1));

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

vector<bool> isprime;

void eratos(int n) {
	isprime.resize(n + 1);
	for (int i = 0; i <= n; i++) {
		isprime[i] = true;
	}
	isprime[0] = false;
	isprime[1] = false;
	for (int i = 2; i * i <= n; i++) {
		if (isprime[i]) {
			int j = i + i;
			while (j <= n) {
				isprime[j] = false;
				j = j + i;
			}
		}
	}
}
int main()
{
	/*
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    */
	eratos(100000);
	vector<int> pr; pr.emplace_back(2); for (int i = 3; i * i <= inf - 7; i += 2) if (isprime[i]) pr.emplace_back(i);
	int l, r; scanf("%d %d", &l, &r);
	vector<int> v; for (int i = l; i <= r; i++) v.emplace_back(i);
	vector<int> cnt(v.size());
	for (auto p : pr) {
		int idx = (l + p - 1) / p * p - l;
		for (int i = idx; i < v.size(); i += p) {
			while (v[i] > 0 and v[i] % p == 0) {
				cnt[i]++;
				v[i] /= p;
			}
		}
	}
	for (int i = 0; i < v.size(); i++) if (v[i] > 1) cnt[i]++;
	int res = 0; for (int i = 0; i < cnt.size(); i++) if (isprime[cnt[i]]) res++;
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 10760
#include<iostream>
#include<string>
#include<cstdio>
#include <cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    int A, B; cin >> A >> B;
    cout << 100 << " " << 100 << endl;
    char grid[110][110];
    rep(i, 100) {
        rep(j, 100) {
            if(i < 50) grid[i][j] = '.';
            else grid[i][j] = '#';
        }
    }
    A --; B --;
    int k = 100 - 1, l = 100 - 1;
    while(A > 0) {
        grid[k][l] = '.';
        A --;
        l -= 2;
        if(l < 0) {
            if(k % 2 == 1) {
                k -= 2;
                l = 98;
            } else {
                k -= 2;
                l = 99;
            }
        }
    }
    k = 0, l = 0;
    while(B > 0) {
        grid[k][l] = '#';
        B --;
        l += 2;
        if(l >= 100) {
            if(k % 2 == 0) {
                k += 2;
                l = 1;
            } else {
                k += 2;
                l = 0;
            }
        } 
    }
    rep(i, 100) {
        rep(j, 100) {
            cout << grid[i][j];
        }
        cout << endl;
    }
	return 0;
}

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

int cost=0;
int arr[100001];

int calculate(int N,int K)
{
	int dp[N];
	for(int i=0;i<N;i++)
	{
		dp[i]={INT_MAX};
	}
	for(int i=0;i<N;i++)
	{
		if(i==0)
			dp[i]=0;
		else if(i<K)
		{
			for(int j=0;j<i;j++)
			{
				dp[i]=min(dp[i],dp[j]+abs(arr[j]-arr[i]));
				//cout<<dp[j]+abs(arr[j]-arr[i])<<endl;
			}
		}
		else
		{
			for(int j=K;j>0;j--)
			{
				dp[i]=min(dp[i],dp[i-j]+abs(arr[i-j]-arr[i]));
			}
		}
	}
	// for(int i=0;i<N;i++)
	// 	cout<<dp[i]<<" ";
	return dp[N-1];
}

int main()
{
	int N,K;
	cin>>N>>K;
	for(int i=0;i<N;i++)
		cin>>arr[i];
	cout<<calculate(N,K)<<endl;
}

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

int s[20];
int a[55],b[55],c[55],d[55];
int sum = -inf;
int n,m,q;

void check(){
	int no = 0;
	for(int i=0;i<q;i++){
		if(s[b[i]] - s[a[i]] == c[i]){
			no += d[i];
		}
	}
	sum = max(sum,no);
	return;
}


void dfs(int now,int val){
	s[now] = val;
	if(now == n){
		check();
		return;
	}
	for(int i=val;i<=m;i++){
		dfs(now+1,i);
	}
}


int main(){
	cin>>n>>m>>q;
	for(int i=0;i<q;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	dfs(1,1);
	cout<<sum<<endl;
	return 0;
} 


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

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

    int x;
    cin >> x;

    int happy = 0;
    happy += x / 500 * 1000;
    x %= 500;
    happy += x / 5 * 5;
    cout << happy << endl;
}

Measured memory_bytes: 256
N = int(input())
NList1 = []
NList2 = []
ans = 0
for i in range(N):
  tmp = input()
  NList1.append(tmp)
  NList2.append(tmp)
M = int(input())
MList = []
for k in range(M):
  tmp = input()
  MList.append(tmp)
NList2 = list(set(NList2))
for t in NList2:
  tmp2 = NList1.count(t) - MList.count(t)
  ans = max(ans,tmp2)
print(str(ans))

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

void run() {
  int n, l;
  std::cin >> n >> l;
  std::vector<std::string> s(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> s[i];
  }
  std::sort(s.begin(), s.end(), [](std::string &a, std::string &b) {
    return a + b < b + a;
  });
  for (auto &&x: s) std::cout << x;
  std::cout << std::endl;
}

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


Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}



int main(){
    ll n;
    cin>>n;
    vector<D> ps(n),qs(n+1);
    cin>>ps>>qs;
    ll N=2*n+1;
    vector<D> A(N);
    for(int i=0;i<n;i++){A[i*2+1]=ps[i];}
    for(int i=0;i<=n;i++){A[i*2]=qs[i];}
    for(int i=1;i<N;i++){A[i]+=A[i-1];}
    auto sum=[&](ll l,ll r){return A[r]-(l==0?0:A[l-1]);};
    vector<vector<D>> dp(N,vector<D>(N,E));
    vector<vector<ll>> K(N,vector<ll>(N,0));
    for(int i=0;i<N;i+=2){dp[i][i]=sum(i,i); K[i][i]=i;}
    for(int i=2;i<N;i+=2){
        for(int j=0;j+i<N;j+=2){
            ll l=K[j][i+j-2],r=K[j+2][i+j];
            for(ll k=l;k<=r;k++){
                if(k&1 && j<k && k<i+j && dp[j][i+j]>dp[j][k-1]+dp[k+1][i+j]){
                    dp[j][i+j]=dp[j][k-1]+dp[k+1][i+j];
                    K[j][i+j]=k;
                }
            }
            dp[j][i+j]+=sum(j,i+j);
        }
    }
    cout<<fixed<<setprecision(12)<<dp[0].back()<<endl;
    
    return 0;
}



Measured memory_bytes: 26428
pub struct Poper<'a> {
	iter: std::str::SplitWhitespace<'a>,
}

impl<'a> Poper<'a> {
	pub fn new(iter: std::str::SplitWhitespace) -> Poper {
		Poper { iter: iter }
	}
	pub fn read<T: std::str::FromStr>(&mut self) -> T
	where
		<T as std::str::FromStr>::Err: std::fmt::Debug,
	{
		self.iter.next().unwrap().parse().unwrap()
	}
}

fn main() {
	let input = {
		use std::io::Read;
		let mut s = String::new();
		std::io::stdin().read_to_string(&mut s).unwrap();
		s
	};
	let mut iter = Poper::new(input.split_whitespace());
	let word: String = iter.read();

	use std::collections::HashMap;
	let mut map = HashMap::new();
	for c in word.chars() {
		let n = map.entry(c).or_insert(0);
		*n += 1;
	}
	let mut ok = true;
	for &n in map.values() {
		if 2 != n {
			ok = false;
			break;
		}
	}
	if ok {
		println!("Yes");
	} else {
		println!("No");
	}
}


Measured memory_bytes: 4352
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define ld          long double
#define pb          push_back
#define endl        '\n'
#define pii         pair<long long int,long long int>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll )x.size()
#define hell        1000000007
#define jell        998244353
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define DEC(N)  cout << std::fixed; cout << setprecision(N);
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  200005
std::vector<ll> a[N];
ll vis[N];
std::vector<ll> v;
ll cnt=0;
void dfs(ll node)
{
	cnt++;
	vis[node]=1;
	for(auto i:a[node])
	if(!vis[i])
	dfs(i);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
  //cin>>t;
    for(int ok=1;ok<=t;ok++)
    {
        ll n,m;
        cin>>n>>m;
        map<pair<ll,ll>,ll>lol;
        for(int i=1;i<=m;i++)
        {
        	ll x,y;
        	cin>>x>>y;
        	if(x>y)
        		swap(x,y);
        	if(lol[{x,y}]==0)
        	{
        		a[x].pb(y);
        		a[y].pb(x);
        		lol[{x,y}]++;
        	}

        }
        for(int i=1;i<=n;i++)
        {
        	//cnt=0;
        	if(!vis[i])
        	{
        		dfs(i);
        		v.pb(cnt);
        		cnt=0;
        	}
        }
        priority_queue<ll>pq;
        for(auto i:v)
        {
        	pq.push(i);
        }
        v.clear();
        ll ans=0;
        while(!pq.empty())
        {
             while(!pq.empty())
             {
             	  if(pq.top()-1>0)
             	  	v.pb(pq.top()-1);
             	  pq.pop();
             }
             ans++;
             for(auto i:v)
             	pq.push(i);
             v.clear();
        }
        cout<<ans;

     
    }
    return 0;
}

Measured memory_bytes: 34884
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
from collections import deque
INF = float("inf")
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)
#print(sx,sy)
d = [(1,0),(-1,0),(0,1),(0,-1)]

R = [[INF]*W for _ in range(H)]
R[sx][sy] = 0
reach = set([])
reach.add((sx,sy))
Q = deque([[sx,sy]])
while Q:
  x,y = Q.popleft()
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if R[x][y] == K:
    #L.add((x,y))
    #if stp == K:
    continue
  #stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    #print(nx,ny)
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or R[nx][ny] != INF:
      continue
    reach.add((nx,ny))
    R[nx][ny] = R[x][y] + 1
    Q.append([nx, ny])
    #print(Q)

ans = INF

for t in reach:
  x,y = t[0],t[1]
  nokori = min(x,H-1-x,y,W-1-y)
  step = (nokori+K-1)//K + 1 #1は最初のステップ
  ans = min(ans,step)
print(ans)
        
        
        
              

Measured memory_bytes: 27484
# ATC001 A

# recursive function
# x, y からスタートして行けるところを探索する
# r[x, y] = x, y まで来るのにかかったステップ数
def search(x, y, r):
    # right
    if x < H - 1 and S[x + 1][y] == "." and r[x + 1][y] == -1:
        r[x + 1][y] = r[x][y] + 1
        search(x + 1, y, r)
    # down
    if y < W - 1 and S[x][y + 1] == "." and r[x][y + 1] == -1:
        r[x][y + 1] = r[x][y] + 1
        search(x, y + 1, r)
    # left
    if 0 < x and S[x - 1][y] == "." and r[x - 1][y] == -1:
        r[x - 1][y] = r[x][y] + 1
        search(x - 1, y, r)
    # up
    if 0 < y and S[x][y - 1] and r[x][y - 1] == -1:
        r[x][y - 1] = r[x][y] + 1
        search(x, y - 1, r)


H, W = map(int, input().split())
S = [input() for h in range(H)]
ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue

        # h,w
        record = [[[h, w]]]
        count = 0
        while True:
            if record[count] == []:
                break
            li = []
            for p in record[count]:
                h = p[0]
                w = p[1]
                next_to_p = []
                if h > 0 and S[h - 1][w] == "." and [h - 1, w] not in record[count - 1] + li:
                    next_to_p.append([h - 1, w])
                if w > 0 and S[h][w - 1] == "." and [h, w - 1] not in record[count - 1] + li:
                    next_to_p.append([h, w - 1])
                if h < H - 1 and S[h + 1][w] == "." and [h + 1, w] not in record[count - 1] + li:
                    next_to_p.append([h + 1, w])
                if w < W - 1 and S[h][w + 1] == "." and [h, w + 1] not in record[count - 1] + li:
                    next_to_p.append([h, w + 1])
                li = li + next_to_p
            record.append(li)
            count += 1

        ans = max(ans, count - 1)

print(ans)

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define _ << ' ' <<
using namespace std;
using ll = long long;

string n;
int k;
int dp[100][4][2];

int f(int i, int r, int s)
{
    if (r > k)
        return 0;
    if (i == n.size())
        return r == k;
    int& sol = dp[i][r][s];
    if (sol != -1)
        return sol;

    sol = 0;
    int d = n[i] - '0';
    for (int j = 0; j <= 9; ++j)
    {
        if (s == 0 && j > d)
            continue;
        sol += f(i + 1, r + (j != 0 ? 1 : 0), (j < d ? 1 : s));
    }
    return sol;
}

int main()
{
    cin >> n >> k;
    memset(dp, -1, sizeof dp);
    cout << f(0, 0, 0);
}


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

int main()
{
  int A, B;
  cin >> A >> B;
  if (A == B) {
    cout << "Draw" << endl;
  } else if (A == 1 || (B != 1 && A > B)) {
    cout << "Alice" << endl;
  } else {
    cout << "Bob" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;

int main(void){
  int n;
  cin>>n;
  double a,sum=0.0,ans; 
  for(int i=0;i<n;i++){
    cin>>a;
    sum+=(1.0/a);
  }
  ans=(1/sum);
  printf("%lf\n",ans);

	return 0;
}

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl;
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

// Aliases
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

int main() {
    while(true) {
        int n, r;
        cin >> n >> r;
        if(n == 0 && r == 0) break;
        int loc = 1;
        stack<pair<int, int>> st;
        REP(i, r) {
            int p, c;
            cin >> p >> c;
            st.push(pair<int, int>(p, c));
        }
        while(!st.empty()) {
            auto ro = st.top();
            st.pop();
            if(ro.second >= loc) {
                loc += ro.first - 1;
            }
            else if(ro.first + ro.second > loc) {
                loc -= ro.second;
            }
        }
        cout << n - loc + 1 << "\n";
    }

    return 0;
}



Measured memory_bytes: 3012
N,A,B=map(int, input().split())
D=list(map(int, input().split()))
D=sorted(D)[::-1]
import math
from math import comb
print(sum(D[:A])/A)
ans=0
if D[0]!=D[A-1]:
  n=D.count(D[A-1])
  k=D[:A].count(D[A-1])
  print(comb(n,k))
else:
  ans=0
  n=D.count(D[A-1])
  for i in range(A,min(n,B)+1):
    ans+=comb(n,i)
  print(ans)

Measured memory_bytes: 9136
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
N=read()
a=list(reads())
count=0
for i in range(N):
  if (i+1)%2==0:
    continue
  elif a[i]%2==0:
    continue
  else:count+=1
print(count)

Measured memory_bytes: 67748