akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <cmath>
//#include <iomanip>
//#include <map>
//#include <unordered_map>
//#include <cstring>
//#include <queue>

using namespace std;
using ll = long long;
// using pint = pair<int, int>;
// ll INF = 1LL << 60;
int INF = 1 << 30;
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> c(m);
	for (int i = 0; i < m; i++) cin >> c[i];
	vector<int> dp(n + 1, INF);
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			if (i - c[j] >= 0) {
				dp[i] = min(dp[i], dp[i - c[j]] + 1);
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}


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

#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define COUT(x) cout << x << endl;
#define PB(x) push_back(x)
#define MP make_pair
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int INF = 1e9;
const int MOD = 1e9+7;

vector<int> A(10);
vector<int> a,b,c,d;
int n,m,q;
int ans=0;

void dfs(int size=0, int last=1){
    if(size==n){
        int sum=0;
        rep(i,q){
            if((A[b[i]]-A[a[i]])==c[i]){
                sum+=d[i];
            }
        }
        chmax(ans,sum);
        return ;
    }else{
        for(int j=last; j<=m; j++){
            A[size]=j;
            dfs(size+1,j);
        }
    }
}

signed main(){
    cin >> n >> m>> q;
    a.resize(q); b.resize(q); c.resize(q); d.resize(q);
    rep(i,q){
        cin >> a[i] >> b[i]>>c[i]>>d[i];
        a[i]--; b[i]--;
    }
    dfs();
    cout<<ans<<endl;
}


Measured memory_bytes: 3608
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		int n;

		Scanner stdIn = new Scanner(System.in);

		for(int i = 1; stdIn.hasNext(); i++) {
			n = stdIn.nextInt();
			if(n == 0) {
				break;
			}
			System.out.println("Case " + i + ": " + n);
		}
	}

}

Measured memory_bytes: 43292
#include "bits/stdc++.h"
using namespace std;

using ll = long long int;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int a, b, c, k; cin >> a >> b >> c >> k;
	int ct = 0;
	while (b <= a) {
		b *= 2;
		++ct;
	}
	while (c <= b) {
		c *= 2;
		++ct;
	}
	if (ct <= k) cout << "Yes\n";
	else cout << "No\n";
}

Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main(void){
    int n;
    vector <int> a;
    int i;
    int x;
    int min_value = INT_MAX;
    int max_value = INT_MIN;
    
    cin >> n;
    for(i = 0; i < n; i++){
        cin >> x;
        a.push_back(x);
    }
    
    for(i = 0; i < n; i++){
        min_value = min(min_value, a[i]);
        max_value = max(max_value, a[i]);
    }
    
    cout << max_value - min_value << endl;
    
    return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = input()
    fN = 0
    for n in N:
        fN += int(n)
    if int(N)%fN==0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 9068
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {
			
			int n = sc.nextInt();
			
			int ans = (1000 - (n % 1000)) %  1000;
			
			System.out.println(ans);
		}
	}

}

Measured memory_bytes: 35824
//Power
#include <iostream>

using namespace std;

long long  power(long long m, long long n, long long M) {
    if(n == 0) return 1;
    if(n == 1) return m;
    return ((power(m * m % M, n / 2, M) * power(m, n % 2, M))) % M;
}

int main() {
    long long m, n;
    const long long M = 1000000007;
    cin >> m >> n;
    cout << power(m, n, M) << endl;
}


Measured memory_bytes: 3100
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p){ os << "(" << p.first << ", " <<  p.second << ")"; return os; }

using namespace std;
int n;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    vector<int> d(n);
    REP(i, n) cin >> d[i];
    sort(d.begin(), d.end());
    int left = n / 2 - 1;
    int ans = 0;
    // DV(d);
    ans = d[left + 1] - d[left];
    cout << ans << endl;
}


Measured memory_bytes: 640
S = list(input())
N = len(S)
T = []
while True:
    for i in S:
        if not T or T[-1] == i:
            T.append(i)
        else:
            T.pop()
    if S == T:
        break
    S = T[:]
    T.clear()
print(N - len(S))

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

using namespace std;

const int N = 1e3 + 3;

int n, m;
int a[N], b[N], c[N];
int dp[N][(1 << 12) + 5];

int go(int idx, int mask) {
	if (mask == (1 << n) - 1) return 0;
	if (idx > m) return 1e9 + 7;
	if (dp[idx][mask] != -1) return dp[idx][mask];
	int ans = 1e9 + 7;
	ans = min(ans, go(idx + 1, mask | c[idx]) + a[idx]);
	ans = min(ans, go(idx + 1, mask));
	return dp[idx][mask] = ans;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i];
		for (int j = 1; j <= b[i]; j++) {
			int x;
			cin >> x;
			x--;
			c[i] |= (1 << x);
		}
	}
	memset(dp, -1, sizeof(dp));
	int ans = go(1, 0);
	if (ans == (int)(1e9 + 7)) cout << "-1";
	else cout << ans;
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K; cin >> K;
    cout << a[--K] << '\n';
}

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

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

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

#include <functional>
template<typename T>
class SegmentTreeOneAll {
    using Func = function<T(T, T)>;

public:
    vector<T> data;
    int n;
    T init;
    Func update_func;
    Func query_func;
    SegmentTreeOneAll(int _n, T _init, Func up, Func qu) {
        init = _init;
        update_func = up;
        query_func = qu;
        for (n = 1; n < _n; n *= 2)
            ;
        data.resize(2 * n - 1, init);
    }
    void update(int pos, T val) {
        pos += n - 1;
        data[pos] = update_func(data[pos], val);
        while (pos > 0) {
            pos = (pos - 1) / 2;
            data[pos] = query_func(data[2 * pos + 1], data[2 * pos + 2]);
        }
    }
    T query(int l, int r) {
        T res = init;
        for (l += n - 1, r += n - 1; l < r; l = l / 2, r = (r - 1) / 2) {
            if (!(l & 1)) {
                res = query_func(res, data[l]);
            }
            if (!(r & 1)) {
                res = query_func(res, data[r - 1]);
            }
        }
        return res;
    }
};

#include <utility>
using P = pair<int, int>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    auto MIN = [&](P a, P b) {
        return min(a, b);
    };
    const int inf = 1 << 29;
    SegmentTreeOneAll<P> seg1(n + 1, P(inf, inf), MIN, MIN);
    seg1.update(0, P(0, 0));
    vector<int> minCost(n + 1, inf);
    minCost[0] = 0;

    REP(i, 1, n + 1) {
        int l = max(i - m, 0);
        if (s[i] == '1') continue;
        P val = seg1.query(l, i);
        val.first++;
        seg1.update(i, P(val.first, i));
        minCost[i] = val.first;
        dump(i, val.first);
    }
    if (minCost[n] >= inf) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> ans;
    for (int i = n; i > 0;) {
        int l = max(i - m, 0);
        auto pos = seg1.query(l, i);
        ans.push_back(i - pos.second);
        i = pos.second;
    }
    reverse(ans.begin(), ans.end());
    REP(i, 0, ans.size()) {
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }

    return 0;
}


Measured memory_bytes: 3528
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  char s[N];
  for(int i=0;i<N;i++)cin>>s[i];
  if(s[K-1]=='A')s[K-1]='a';
  if(s[K-1]=='B')s[K-1]='b';
  if(s[K-1]=='C')s[K-1]='c';
  for(int i=0;i<N;i++)cout<<s[i];
}
  


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

const int INF = 1001001001;

int main(){
    ll n,d;
    cin>>n>>d;
    vector<ll> x(n),y(n);
    ll count=0;
    rep(i,n){
        cin>>x[i]>>y[i];
        if(d*d>=x[i]*x[i]+y[i]*y[i]){
            count++;
        }
    }
    cout<<count;
    return 0;
}


Measured memory_bytes: 6416
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

const int MAX = 8;
const int dy[4] = { 0,1,0,-1 };
const int dx[4] = { 1,0,-1,0 };

int h, w, c;

int solve(vector<vector<int>> grid, int p[])
{
	int ans = 0;

	for (int cnt = 0; cnt < 5; cnt++) {
		queue<pair<int, int>> q;
		bool visited[MAX][MAX];

		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				visited[i][j] = false;
			}
		}

		int num = grid[0][0];
		q.push({ 0,0 });
		visited[0][0] = true;

		while (q.empty() == false) {
			pair<int, int> now = q.front();
			q.pop();

			grid[now.first][now.second] = p[cnt];

			for (int i = 0; i < 4; i++) {
				int ny = now.first + dy[i];
				int nx = now.second + dx[i];

				if (ny < 0 || ny >= h || nx < 0 || nx >= w) {
					continue;
				}

				if (grid[ny][nx] == num&&visited[ny][nx] == false) {
					q.push({ ny,nx });
					visited[ny][nx] = true;
				}
			}
		}
	}

	bool visited[MAX][MAX];

	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			visited[i][j] = false;
		}
	}

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			int sum = 0;
			queue<pair<int, int>> q;

			if (visited[y][x] == false) {
				q.push({ y,x });
				visited[y][x] = true;
			}

			while (q.empty() == false) {
				pair<int, int> now = q.front();
				q.pop();

				sum++;

				for (int i = 0; i < 4; i++) {
					int ny = now.first + dy[i];
					int nx = now.second + dx[i];

					if (ny < 0 || ny >= h || nx < 0 || nx >= w) {
						continue;
					}

					if (grid[ny][nx] == c&&visited[ny][nx] == false) {
						q.push({ ny,nx });
						visited[ny][nx] = true;
					}
				}
			}

			ans = max(ans, sum);
		}
	}

	return ans;
}

int main()
{
	while (true) {
		cin >> h >> w >> c;

		if (h == 0 && w == 0 && c == 0) {
			break;
		}

		vector<vector<int>> grid(h, vector<int>(w, -1));

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> grid[i][j];
			}
		}

		int ans = 0;

		for (int i = 1; i <= 6; i++) {
			for (int j = 1; j <= 6; j++) {
				for (int k = 1; k <= 6; k++) {
					for (int l = 1; l <= 6; l++) {
						int p[5] = { i,j,k,l,c };
						ans = max(ans, solve(grid, p));
					}
				}
			}
		}

		cout << ans << endl;
	}

	return 0;
}

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

using namespace std;

char s[5], t[5];

int main() {
	scanf("%s%s", s, t);
	
	int res = 0;
	
	for (int i = 0; i < 3; i++) res += (s[i] == t[i]);
	
	printf("%d\n", res);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;
#include <queue>
#include <set>

vc<vc<int>> famitree(int n){
    if(n == 0) return vc<vc<int>>(1);
    auto ft = famitree(n-1);
    int s = ft.size();
    ft.resize(s*2);
    For(i, s) ft[i].push_back(i+s);
    return ft;
}

int main(void){
    Cin(int, n);
    multiset<int> s;
    Rep(1 << n){
        Cin(int, x);
        s.insert(x);
    }
    // Couts(s);

    auto ft = famitree(n);
    /*For(i, ft.size()){
        cout << i << ": "; Couts(ft[i]);
    }*/
    
    vc<int> v(1 << n, 2e9);

    For(i, 1 << n){
        // Cout("#", i);
        if(v[i] <= *s.begin()){
            Cout("No"); return 0;
        }
        auto itr = s.lower_bound(v[i]);
        itr --;
        v[i] = *itr;
        s.erase(itr);
        for(int j : ft[i]){
            v[j] = v[i];
        }
    }
    Cout("Yes");
}


Measured memory_bytes: 23980
#include<iostream>

using namespace std;

int main() {
	int r, g, b;
	cin >> r >> g >> b;

	int s = (r * 100) + (g * 10) + b;

	if (s % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
using System;

namespace tst
{
    class Program
    {
        public static void Main()
        {

            int n = int.Parse(Console.ReadLine());
            string[] In = Console.ReadLine().Split(' ');
            int[] P = new int[n];
            for(int i=0; i<n; i++)
            {
                P[i] = int.Parse(In[i]);
            }
            int cnt = 0;
            if (n == 1)
            {
                cnt++;
            }
            else
            {
                int min = 100000000;
                for(int i=0; i<n; i++)
                {
                    if (P[i] <= min)
                    {
                        min = P[i];
                        cnt++;
                    }

                }
            }
            Console.WriteLine(cnt);
        }

    }
}

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

int main() {
  int k, a, b;
  cin >> k >> a >> b;

  for (int i = 0; i <= b - a; i++) {
    if ((a + i) % k == 0) {
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ss = 1e9;
    int n;
    cin >> n;
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    for(int i = -100;i <=100; i++)
    {    int cost=0;
        for(int j= 0; j < n; j++)
        {
            cost += (i-v[j]) * (i - v[j]);
        }
        ss=min(ss,cost);
    }
    cout<<ss<<"\n";
    return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;


typedef long long ll;
typedef pair <int, int> ii;
typedef pair <int, ii> iii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

#define iINF (1<<30)
#define INF (1LL<<59)
#define forn(i) for(int i = 0;i < n; ++i)
#define form(i,n) for(int i = 0 ;i < n; ++i)
#define NIL -1

const ll mod = 998244353;
int n;
int m;
int ans;
string str;

int main(){
  char stone[200010];
  int wh[200010] ;
  int bl[200010];
  cin>>n ;
  cin>>stone;
  int temp=0;
  int wb=0;
  bool black=false;
  for(int i=0;i<n;i++){
    if((black&&(stone[i]=='#')) ||
       (!black&&(stone[i]=='.'))){
      temp++;
    }else{
      if(black){
        bl[wb]=temp;
        temp=1;
        black=false;
        wb++;
      }else{
        wh[wb]=temp;
        temp=1;
        black=true;
      }
    }
  }
  if(!black){
    wh[wb]=temp;
    temp=0;
    black=false;
  }
  bl[wb]=temp;
  wb++;
  for(int i=1;i<wb;i++){
    bl[i]+=bl[i-1];
    wh[wb-1-i]+=wh[wb-i];
  }
  ans=min(wh[1], bl[wb-2]);
  for(int i=1;i<wb-1;i++){
    ans=min(ans,wh[i+1]+bl[i-1]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#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 FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;
#define INF 1000000000000
#define NOD 1000000007
#define PI 3.141592653589793238462643

int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << (h2-h1)*60 + m2-m1 - k << endl;
}


Measured memory_bytes: 3636
#include <iostream>

using namespace std;

int main()
{
    int A, B, C, K;
    int s = 0;
    cin >> A >> B >> C >> K;
    if (K <= A){
        cout << K;
    }
    else if(K <= A + B){
        cout << A;
    }
    else{
        int k;
        k = K - (A + B);
        cout << A - k;
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, m;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n >> m;
    vector<P> v;
    rep(i, 0, m) {
        int a, b;
        cin >> b >> a;
        v.pb(mp(a, b));
    }
    sort(v.begin(), v.end());
    int ep = 0, ans = 0;
    rep(i, 0, m) {
        if (ep <= v[i].second) {
            ep = v[i].first;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1400
#include<iostream>
#include<vector>
using namespace std;
void sortt(vector<int>* a) {
	for (int i = 0; i < a->size(); i++) {
		int min = a->at(i);
		int iii = i;
		for (int j = i; j < a->size(); j++) {
			if (min > a->at(j)) {
				iii = j;
				min = a->at(j);
			}
		}
		int swap = a->at(i);
		a->at(i) = min;
		a->at(iii) = swap;
	}

}
int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	for (int i = 0; i < n; i++) {
		cin >> d.at(i);
	}
	sortt(&d);
	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			if (d.at(i) == d.at(j)) {
				count++;
				i++;
			}
		}
	}
	cout << d.size() - count << endl;
}

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

int main() {
double n,t,a;
cin >> n >> t >> a;
vector<double>  h(n),hight(n);
double mini = 1000000;
int ans = -1;
for(int i = 0;i < n;i++){
  cin >> h[i];
  hight[i] = abs(a - t + h[i]*0.006);
 if(mini > hight[i]){
  mini = hight[i];
  ans = i+1;
 }
}

cout << ans << endl;
}


Measured memory_bytes: 256
using System;

namespace AtCoder.Abc
{
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var sp = Console.ReadLine().Split(' ');
            var a = int.Parse(sp[0]);
            var b = int.Parse(sp[1]);

            Console.WriteLine(a*b);

            Console.Out.Flush();
        }
    }
}


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

int main() {
  int n; cin >> n;
  int sum_arr = 0;
  vector<int> arr(n + 2);
  arr[0] = 0;
  arr[n + 1] = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
    sum_arr += abs(arr[i] - arr[i - 1]);
  }
  sum_arr += abs(arr[n + 1] - arr[n]);
  for (int i = 1; i <= n; ++i) {
    int diff = abs(arr[i + 1] - arr[i]) + abs(arr[i] - arr[i - 1]) - abs(arr[i + 1] - arr[i - 1]);
    cout << sum_arr - diff << endl;
  }
}


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

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	int a[n];
	for(int i = 0;i < n; ++i)cin >> a[i];
	int sum = accumulate(a,a+n,0);
	int m;
	cin >> m;
	while(m--){
		int p,x;
		cin >> p >> x;
		--p;
		cout << sum + x - a[p] << '\n';
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <ctype.h>
#include <stdio.h>
using namespace std;
int main(){
	char a[11], b[11], c[11];
	cin >> a >> b >> c;

	printf("%c%c%c\n",toupper(a[0]),toupper(b[0]),toupper(c[0]));
	return 0;

}

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

using namespace std;

const int MAX = 2e3+10;
const int MOD = 1e9+7;

int s[MAX], t[MAX];
long long dp[MAX][MAX];

int main(){

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

    int n, m;
    cin >> n >> m;

    for(int i=1;i<=n;++i)
        cin >> s[i];
    
    for(int i=1;i<=m;++i)
        cin >> t[i];
    
    for(int i=0;i<=max(n,m);++i)
        dp[i][0] = dp[0][i] = 1;
    
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i] == t[j])
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
            else
                dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
    
    cout << (dp[n][m] + MOD) % MOD << '\n';

    return 0;
}


Measured memory_bytes: 31744
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define MAXN 100000
using namespace std;

vector<int> edges[2*MAXN+2];
bool done[2*MAXN+2];

void dfs(int u) {
    if (done[u])
        return;
    done[u]=true;
    for(int i=0;i<edges[u].size();i++) {
        int v=edges[u][i];
        if(!done[v])
            dfs(v);
    }
}

int main() {
    int N,M;
    cin>>N>>M;
    for(int i=0;i<N;i++) {
        int K;
        cin>>K;
        for(int j=1;j<=K;j++)
        {
            int l;
            cin>>l;
            l--;
            edges[i].push_back(l+N);
            edges[l+N].push_back(i);
        }
    }
    
    for(int i=0;i<N+M;i++)
        done[i]=false;
    
    dfs(0);
    
    bool ok = true;
    for(int i=0;i<N;i++) {
        if (!done[i]) {
            ok=false;
        }
    }
    
    if(ok)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    
    
}

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

using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> a(N), b(N, 0);
    rep(i, N) cin >> a[i];
    rep(i, N) {
        int c = N - i;
        int s = 0;
        for (int j = c * 2; j <= N; j += c) {
            s += b[j - 1];
        }
        //cout << i << " " << s << " " << a[c - 1] << endl;
        if (s % 2 == a[c - 1]) b[c - 1] = 0;
        else b[c - 1] = 1;
    }
    int M = 0;
    rep(i, N) M += b[i];
    cout << M << endl;
    rep(i, N) {
        if (b[i] == 1) cout << i + 1 << " ";
    }
    cout << endl;
}

Measured memory_bytes: 2432
N = int(input())
S = input()

B = {"S":"W", "W":"S"}
def check(a0, a1):
    b0,b1 = a0,a1
    A = a1
    for i in range(N):
        if a1 == "S":
            if S[i] == "o":
                a2 = a0
            else:
                a2 = B[a0]
        else:
            if S[i] == "o":
                a2 = B[a0]
            else:
                a2 = a0
        A += a2
        a0,a1 = a1,a2
    if A[0] == A[N] and A[0] == b1 and A[N-1] == b0:
        return A[0:N]
    else:
        return -1

Ans = []
Ans.append(check("S","S"))
Ans.append(check("S","W"))
Ans.append(check("W","S"))
Ans.append(check("W","W"))

for ans in Ans:
    if ans == -1:
        continue
    else:
        print(ans)
        exit()
else:
    print(-1)




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

int main ()
{
  int C[100]={};
  int N,M;
  cin >> N >> M;
  int K;
  int tmp;
  for(int i=0;i<N;i++){
  	cin >> K;
    for(int j=0;j<K;j++){
      cin >> tmp;
      C[tmp-1]++;
    }
  }
  int cnt=0;
  for(int i=0;i<M;i++){
    if(C[i]==N) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, D;
  cin >> N >> D;
  vector<llvec> x(N, llvec(D));
  rep(i, N){
    rep(j, D)cin >> x[i][j];
  }
  set<ll> d;
  rep(i, 10000){
    d.insert(i*i);
  }
  ll cnt=0;
  rep(i, N){
    FOR(j, i+1, N){
      ll tmp=0;
      rep(k, D){
        tmp += pow(x[i][k]-x[j][k], 2);
      }
      if(d.count(tmp)>0)cnt++;
    }    
  }
  cout << cnt;
  return 0;
}


Measured memory_bytes: 3996
#include <iostream>
#include<bits/stdc++.h>
#define modulo 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int h,w,n;
    cin>>h>>w;
    char x;
    bool availble[h+2][w+2];
    memset(availble,true,sizeof availble);
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++){
            cin>>x;
            if(x=='#')availble[i+1][j+1]=false;
        }
    }
    int dp[h+2][w+2];
    memset(dp,0,sizeof dp);
    dp[1][1]=1;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(availble[i][j]){
                dp[i][j]+=((dp[(i-1)][j]%modulo+dp[i][(j-1)]%modulo)%modulo);
            }
        }
    }
    cout<<dp[h][w];

    return 0;
}


Measured memory_bytes: 5120
A,V = list(map(int,input().split()))
B,W = list(map(int,input().split()))
T = int(input())

if A <= B:
    if A+V*T >= B+W*T:
        print("YES")
    else:
        print("NO")
else:
    if A-V*T <= B-W*T:
        print("YES")
    else:
        print("NO")


Measured memory_bytes: 9176
#include "bits/stdc++.h"
using namespace std;

void P(int n, char c) {
	for (int i = 0; i < n; i++) {
		cout << c;
	}
}

int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int x = tx - sx, y = ty - sy;
	if (x > 0) {
		P(x, 'R');
	}
	else {
		P(-x, 'L');
	}
	x = -x;
	if (y > 0) {
		P(y, 'U');
	}
	else {
		P(-y, 'D');
	}
	y = -y;

	if (x > 0) {
		P(x, 'R');
	}
	else {
		P(-x, 'L');
	}
	x = -x;
	if (y > 0) {
		P(y + 1, 'U');
	}
	else {
		P(-y + 1, 'D');
	}
	y = -y;

	if (x > 0) {
		P(x + 1, 'R');
	}
	else {
		P(-x + 1, 'L');
	}
	x = -x;
	if (y > 0) {
		P(y + 1, 'U');
	}
	else {
		P(-y + 1, 'D');
	}
	y = -y;
	if (x > 0) {
		P(1, 'R');
	}
	else {
		P(1, 'L');
	}
	if (y > 0) {
		P(1, 'D');
	}
	else {
		P(1, 'U');
	}
	if (x > 0) {
		P(x + 1, 'R');
	}
	else {
		P(-x + 1, 'L');
	}
	if (y > 0) {
		P(y + 1, 'U');
	}
	else {
		P(-y + 1, 'D');
	}
	if (x > 0) {
		P(1, 'L');
	}
	else {
		P(1, 'R');
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    string s;
    cin >> n >> s;
    int open = 0;
    for(char c : s) {
        if(c == '(') {
            open++;
        } else if(open == 0) {
            cout << '(';
        } else {
            open--;
        }
    }
    cout << s;
    while(open--) {
        cout << ')';
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
using namespace std;
const int tINF = (int)INT_MAX;
const long long lINF = (long long)LLONG_MAX;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef DEBUG
			assert(freopen("inp", "r", stdin));
			assert(freopen("out", "w",stdout));
	#else
			#define cerr if(false)cerr
	#endif
    ll n,m ;
    cin >> n >> m;
    if(n == m)
        cout << "Yes\n";
    else
        cout << "No\n";
   cerr << "Time execute: " << (double)clock() / (double)CLOCKS_PER_SEC 
    << " sec" << endl;
}

Measured memory_bytes: 256
N, X, Y = map(int, input().split())

d_dict = [0] * N

for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    d = j - i
    if X < j  and i < Y:
      d = min(d, abs(i-X) + abs(j-Y) + 1)
    # print(i, j, d)
    d_dict[d] += 1

ans = d_dict[1:]
print(*ans, sep='\n')


Measured memory_bytes: 3444
use std::io;


fn main() {
    let (x, y) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    println!("{}", x + y / 2);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#include <vector>
#include <iostream>
#include <limits>

using namespace std;

double solve(vector<double> prob)
{
	int coins = prob.size();
	double res = 0.0;
	// Prob to have dp[i][j] = prob having j heads having toss coins up to the ith one...
	vector<vector<double>>dp(prob.size() + 1, vector<double>(prob.size()+1, 0.0));
	dp[0][0] = 1.0;
	for(int i = 1; i <= coins; i++)
		dp[i][0] = dp[i-1][0] * (1 - prob[i-1]);
		
	for(int tosses = 1; tosses <= coins; ++tosses) {
		for(int heads = 1; heads <= coins; ++heads) {
			dp[tosses][heads] = dp[tosses - 1][heads - 1] * prob[tosses - 1] + dp[tosses - 1][heads] * (1.0 - prob[tosses - 1]); 
		}
	}
	// need to sum correct value when tosses is more
	for(int i = coins; i > coins / 2; i--)
		res += dp[coins][i];
	return res;
}


int main()
{
	int coins;
	cin >> coins;
	vector<double> prob(coins);
	for(int i = 0; i < coins; i++) {
		cin >> prob[i];
	}
	double res = solve(prob);
	cout.precision(numeric_limits<double>::max_digits10);
	cout << res << endl;
	return 0;
}


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

int main() {
	ll A,B;
	cin >> A >> B;
      auto gcd = [](ll a, ll b){
        while(1){
            swap(a,b);
            if(b == 0) return a;
            a%=b;
        }
    };
		auto lcm = [gcd](ll a, ll b){
			return a*b /gcd(a,b);
		};
		cout << lcm(A,B) << endl;
}

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

int main(){
    int n;
    cin >> n ;
    vector <int> p(n+1);
    rep(i,n){
        cin >> p[i+1];
    }
    int k;
    k=1;

    rep(i,n){
        if(p[i+1]!=i+1){
            if(k==1 and p[p[i+1]]==i+1){
                k=0;
                swap(p[p[i+1]],p[i+1]);
            }
            else{
                k=2;
                break;
            }
        }
    }
    if(k==2){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
/*	MASTER HAS FAILED MORE TIMES
	THAN BEGINNER HAS EVER TRIED
*/

#include <bits/stdc++.h>

using namespace std;

#define endl             '\n'
#define allin(a)         a.begin(), a.end()
#define allde(a)         a.rbegin(), a.rend()
#define mem(a, n)        memset(a, n, sizeof(a))
#define Unique(n)        (n).erase(unique(all(n)), (n).end())
#define NumofDigits(n)   ((long long)log10(n)+1)
#define repeat(i, a, n)  for(int i=a; i<n; i++)
#define isPowerOfTwo(n)  (n && !(n & (n - 1)))

typedef long long ll;
typedef long double ld;

int sieve(int n);
unsigned long long pow(long long base, long long power);
long long gcd(long long a, long long b){ return a%b ? gcd(b, a%b) : b; }
long long lcm(long long a, long long b){ return a*b/gcd(a, b); }

void quicken(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
void file(){
    #ifdef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif /*ONLINE_JUDGE*/
}

int main(){
    quicken();

    ll n, h, a, b; cin >> n >> h;
    vector<pair<ll, ll>> ab(n), ba(n);

    repeat(i, 0, n){
        cin >> a >> b;
        ab.push_back({a, b});
        ba.push_back({b, a});
    }
    sort(allde(ab)), sort(allde(ba));
    repeat(i, 0, n){
        if(ba[i].first<=ab[0].first) {n = i; break;}
        h -= ba[i].first;
        if(h<=0) return cout << i+1, 0;
    }

    cout << n + h/ab[0].first + (h%ab[0].first!=0);

    return 0;
}

unsigned long long pow(long long base, long long power){ /// mod?
    if(power==0) return 1;
    if(power==1) return base;

    unsigned long long ans = pow(base, power/2); /// mod?
    ans *= ans; /// ((ans%mod)*(ans%mod))%mod;

    if(power&1) return ans*base; /// ((ans%mod)*(base%mod))%mod;
    return ans;
}

int sieve(int n){
    int c = 0;
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = 0;

    for(long long i=2; i*i<=n; i++)
        if(isPrime[i])
            for(long long j=i*2; j<=n; j+=i)
                isPrime[j] = 0;
    repeat(i, 0, n+1)
        if(isPrime[i]) c++;
    return c; /// primeCount [1:n]
}


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

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define PB push_back
#define MP make_pair
#define MOD 1000000000
#define FOR(i,a,b) for(int i=(a);(i)<(b);(i)++)

typedef unsigned int UI;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<char, int> PCI;
int n , k;
vector<vector<int> > g(2000);
int dist[2000][2000];
void dfs(int u , int from , int p = -1)
{
	for(int i = 0; i < g[u].size(); i++)
	{
		int v = g[u][i];
		if(v != p)
		{
			dist[from][v] = dist[from][u] + 1;
			dfs(v , from , u);
		}
	}
}
int cannotBe[2000];
int main()
{
	//freopen("input.txt" , "r" , stdin);
	scanf("%d %d" , &n , &k);
	for(int i = 1; i < n; i++)
	{
		int u , v;
		scanf("%d %d" , &u , &v);
		u--;v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	//cout << n << endl;
	for(int i = 0; i < n; i++)
	{
		dfs(i , i);
	}
	vector<set<int> >gr(n);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(dist[i][j] > k)
			{
				gr[i].insert(j);
			}
		}
	}

	int ans = 0;
	while(1)
	{
		int bestVert = -1;
		for(int i = 0; i < n; i++)
		{
			if((!cannotBe[i] && gr[i].size() > gr[bestVert].size()) || (!cannotBe[i] && gr[i].size() && bestVert == -1))
			{
				bestVert = i;
			}
		}
		if(bestVert == -1)
			break;
		cannotBe[bestVert] = 1;
		for(auto it = gr[bestVert].begin(); it != gr[bestVert].end(); it++)
		{
			gr[*it].erase(bestVert);
		}
		ans++;
	}
	/*for(int i = n - 1; i >= 0; i--)
	{
		int idx = szIdx[i].second;
		//cout << idx << endl;
		if(gr[idx].size())
		{
			ans++;
			for(auto it = gr[idx].begin(); it != gr[idx].end(); it++)
			{
				int v = *it;
				gr[v].erase(idx);
			}
		}
		szIdx.clear();
		for(int i = 0; i < n; i++)
		{
			szIdx.pb(mp(gr[i].size() , i));
		}
		sort(szIdx.begin() , szIdx.end());

	}*/
	cout << ans;
    return 0;
}


Measured memory_bytes: 203392
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 44, inf = 0x3f3f3f3f;
int n,m,qz[N][N];char S[N][N];
int tx,ty,f[N][N][N][N];
inline int qry(int x1, int y1, int x2, int y2){return qz[x2][y2]-qz[x1-1][y2]-qz[x2][y1-1]+qz[x1-1][y1-1];}
int main() {
	read(n);read(m);
	rep(i,1,n)scanf("%s",S[i]+1);
	rep(i,1,n)rep(j,1,m){
		if(S[i][j]=='P')tx=i,ty=j,S[i][j]='+';
		qz[i][j]=S[i][j]=='#';
	}
	rep(i,1,n)rep(j,1,m)qz[i+1][j]+=qz[i][j];
	rep(i,1,n)rep(j,1,m)qz[i][j+1]+=qz[i][j];
	memset(f,inf,sizeof(f));int res=inf;
	f[1][n][1][m]=0;
	rep(l1,1,n)per(r1,n,1)rep(l2,1,m)per(r2,m,l2)if(f[l1][r1][l2][r2]<inf){
	//	printf("%d %d %d %d:%d\n",l1,r1,l2,r2,f[l1][r1][l2][r2]);
		if(l1<=tx&&tx<=r1&&l2<=ty&&ty<=r2){
			umin(res,f[l1][r1][l2][r2]+qry(l1,l2,tx,ty));
			umin(res,f[l1][r1][l2][r2]+qry(l1,ty,tx,r2));
			umin(res,f[l1][r1][l2][r2]+qry(tx,l2,r1,ty));
			umin(res,f[l1][r1][l2][r2]+qry(tx,ty,r1,r2));
		}
		register int tmp;
		rep(m1,l1,r1-1)rep(m2,l2,r2-1){
			tmp=f[l1][r1][l2][r2]+qry(m1+1,l2,r1,m2)+qry(l1,m2+1,m1,r2);
			umin(f[l1][m1][l2][m2],tmp);umin(f[m1+1][r1][m2+1][r2],tmp);
			tmp=f[l1][r1][l2][r2]+qry(l1,l2,m1,m2)+qry(m1+1,m2+1,r1,r2);
			umin(f[l1][m1][m2+1][r2],tmp);umin(f[m1+1][r1][l2][m2],tmp);
		}
	}
	cout<<res;return 0;
}


Measured memory_bytes: 14976
def selectionSort(A, N):
  cnt = 0
  for i in range(0,N):
    minj  = i
    for j in range(i, N):
      if A[j] < A[minj]:
        minj = j
    cnt = cnt + int(i != minj)
    A[i], A[minj] = A[minj], A[i]
  return cnt


N = int(input())
A = [int(i) for i in input().split()]
cnt = selectionSort(A, N)

for i in range(N):
  if i != 0:
    print(" ", end ="")
  print(A[i], end = "")
  
  
print()
print(cnt)


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

int main()
{
  int n;
  cin >> n;
  vector<int> height(n + 1);
  for (int i = 1; i <= n; i++)
  {
    cin >> height[i];
  }
  vector<ll> dp(n);
  dp[0] = 0x3f3f3f3f;
  dp[1] = 0;
  for (int i = 2; i <= n; i++)
  {
    dp[i] = min(abs(height[i] - height[i - 1]) + dp[i - 1],
                abs(height[i] - height[i - 2]) + dp[i - 2]);
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 1408
package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	xs := make([]int, n)
	for i := range xs {
		fmt.Scan(&xs[i])
	}

	sum := 0
	for _, x := range xs {
		sum += 2 * min(x, k-x)
	}
	fmt.Println(sum)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;

int main() {
    int N,Z,W; cin>>N>>Z>>W;

    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin>>a[i];
    }

    if(N==1){
        cout<<abs(a[0]-W)<<endl;
    }else{
        cout<<max(abs(a[N-1]-W),abs(a[N-2]-a[N-1]));
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pr(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(v) (v).begin(), (v).end()
#define int long long
#define sz(v) (int)(v).size()
#define mod 1000000007 // ((a- b)% mod+ mod)% mod

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

void solve() {
        string str; cin >> str;
        int mx= 0, r= 0;
        for (int i= 0; i< 3; i++) {
                if (str[i]=='R') r++;
                else {
                        mx= max(r, mx);
                        r= 0;
                }
        }
        mx= max(r, mx);
        cout << mx;
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int T= 1;
        //cin >> T;
        while ( T-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 3668
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

    def same(self, x, y):
        return self.root(x)==self.root(y)

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]

n,m = map(int, input().split())
pl = list(map(int, input().split()))

u = UnionFind(n+1)
for _ in range(m):
  x,y = map(int, input().split())
  u.unite(x,y)

res = 0
for i in range(1,n+1):
  if u.same(i,pl[i-1]):
    res += 1
print(res)

Measured memory_bytes: 13812
# frozen_string_literal: true

# なんこれ
tile = gets.chomp.chars
ans = 0
pre = tile[0]
(1...tile.size).each do |ti|
  if tile[ti] == pre
    tile[ti] = pre == '1' ? '0' : '1'
    ans += 1
  end
  pre = tile[ti]
end
puts ans


Measured memory_bytes: 6908
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int h, w;
  cin >> h >> w;
  vector<vi> g(h + 2, vi(w + 2, -2));
  int white = 0;
  rep2(i, 1, h + 1) rep2(j, 1, w + 1) {
    char c;
    cin >> c;
    if(c == '.') {
      g[i][j] = -1;
      white++;
    }
  }
  queue<pair<int, int>> q;
  q.push(P(1, 1));
  g[1][1] = 1;
  while(!q.empty()) {
    int i = q.front().first;
    int j = q.front().second;
    q.pop();
    rep(k, 4) {
      int ni = i + dir[k];
      int nj = j + dir[k + 1];
      if(g[ni][nj] != -1) continue;
      g[ni][nj] = g[i][j] + 1;
      q.push(P(ni, nj));
    }
  }
  int ans;
  if(g[h][w] < 0)
    ans = -1;
  else
    ans = white - g[h][w];
  cout << ans << endl;
}

Measured memory_bytes: 384
use proconio::{input, fastout};
use std::collections::{HashMap, HashSet, VecDeque};


#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(usize, usize); m],
    }

    let mut map = HashMap::new();

    for &(a, b) in ab.iter() {
        (*map.entry(a).or_insert_with(|| vec![])).push(b);
        (*map.entry(b).or_insert_with(|| vec![])).push(a);
    }

    let ans = bfs(&map, n);
    if let Some(ans) = ans{
        println!("Yes");
        for i in ans.iter().skip(1) {
            println!("{}", i);
        }
    } else {
        println!("No");
    }
}



fn bfs(map: &HashMap<usize, Vec<usize>>, n: usize) -> Option<Vec<usize>> {
    let mut ans = vec![0; n];
    let mut set = HashSet::new();
    for i in 2..=n {
        set.insert(i);
    }
    let mut queue = VecDeque::new();
    queue.push_back(1);
    while let Some(key) = queue.pop_front() {
        if let Some(next) = map.get(&key) {
            for i in next.iter() {
                if set.remove(i) {
                    queue.push_back(*i);
                    ans[*i-1] = key;
                }
            }
        }
    }
    if set.is_empty() {
        Some(ans)
    } else {
        None
    }
}

Measured memory_bytes: 21180