akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define R register
typedef long long ll;
typedef std::pair<ll, int> pii;

const int MN = 1e5 + 5;

pii d[MN];

std::map<ll, int> mp;

int n, fa[MN], sz[MN], rt;

ll dp[MN];

struct Edge {
	int to;
	Edge *nxt;
	Edge(Edge *nxt = nullptr, int to = 0) : to(to), nxt(nxt){}
}*hd[MN];

inline void ins(int u, int v) {hd[u] = new Edge(hd[u], v);}

void dfs(int u) {
	for (R Edge *e = hd[u]; e != nullptr; e = e -> nxt) {
		R int v = e -> to;
		dfs(v);
		dp[u] += sz[v] + dp[v];
	}
}

void solve(int u) {
	for (R Edge *e = hd[u]; e != nullptr; e = e -> nxt) {
		R int v = e -> to;
		dp[v] += (n - sz[v]) + (dp[u] - dp[v] - sz[v]);
		solve(v);
	}
}

int main() {
	std::ios::sync_with_stdio(false);

	std::cin >> n;
	for (R int i = 1; i <= n; ++i) {
		R ll x;
		std::cin >> x;
		mp[x] = i;
		d[i] = pii(x, i);
		sz[i] = 1;
	}
	
	std::sort(d + 1, d + n + 1);
	for (R int i = n; i > 1; --i) {
		R int v = d[i].second;
		R ll res = d[i].first;
		if (mp[res + (sz[v] << 1) - n])	 {
			fa[v] = mp[res + (sz[v] << 1) - n];
			sz[fa[v]] += sz[v];
		}
		else {
			std::cout << "-1" << std::endl;
			return 0;
		}
	}
	for (R int i = 1; i <= n; ++i)
		if (fa[i]) ins(fa[i], i);
		else rt = i;
	dfs(rt);
	solve(rt);
	for (R int i = 1; i <= n; ++i)
		if (dp[d[i].second] != d[i].first){
			std::cout << "-1" << std::endl;
			return 0;
		}

	for (R int i = 1; i <= n; ++i)
		if (fa[i])
			std::cout << fa[i] << " " << i << std::endl;
	return 0;
}

Measured memory_bytes: 16384
#include <iostream>
#include <algorithm>
//#include <numeric>
using namespace std;
#define FOR(i,a,b) for (size_t i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (size_t i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define INF 1e7

long gcd(long a, long b)
{
  long r;
  do {
    r = b % a;
    //printf("%ld = %ld * ? + %ld\n", b, a, r);
    b = a;
    a = r;
  } while(r);

  return b;
}

long search_root(long a)
{
  int ans = 1, tmp = a;
  for (int i = 2; i * i <= tmp; i++) {
    //cout<<i<<tmp<<endl;
    if (tmp % i == 0) {
      ans *= i;
      while (tmp % i == 0) tmp /= i;
    }
  }

  return ans * tmp;
}

int main()
{
  long p, q;
  cin>>p>>q;

  cout<<search_root(q / gcd(p, q))<<endl;

  return 0;
}



Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double pi=3.14159265358979323846;
bool chmin(auto &a,auto b){if(a>b){a=b;return true;}return false;}
bool chmax(auto &a,auto b){if(a<b){a=b;return true;}return false;}
void outvi(vi v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
void outvvi(vvi v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
int main(){
    ll n,k;cin>>n>>k;
    vector<vvi> dp(n,vvi(n+3,vi(k+3)));
    dp[0][0][0]=1;
    dp[0][1][2]=1;
    REP(i,1,n){
        rep(j,n+2){
            rep(l,k+3){
                if(l<j*2)continue;
                dp[i][j][l]+=dp[i-1][j+1][l-j*2]*((j+1)*(j+1));
                dp[i][j][l]+=dp[i-1][j][l-j*2]*(1+2*j);
                if(j)dp[i][j][l]+=dp[i-1][j-1][l-j*2];
                dp[i][j][l]%=mod;
            }
        }
    }
    cout<<dp[n-1][0][k]%mod<<endl;
}

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

using namespace std;
typedef long long ll;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin>>n;

	string s;
	cin>>s;

	int cnt =1;

	for(int i=0;i<n-1;i++)
	{
		if(s[i]!=s[i+1])cnt++;
	}
	cout<<cnt<<'\n';
	return 0;
}

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

int main() {
    string S;
    cin>>S;
    if(S=="ABC"){
        cout<<"ARC"<<endl;
    }
    else{
        cout<<"ABC"<<endl;
    }
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define MAX 100005
#define ll long long
#define upperlimit 1000100
#define INF 1e18
#define eps 1e-8
#define endl '\n'
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define MOD 1000000007
#define slld(t) scanf("%lld",&t)
#define sd(t) scanf("%d",&t)
#define pd(t) printf("%d\n",t)
#define plld(t) printf("%lld\n",t)
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define vi vector<int>
#define clr(a) memset(a,0,sizeof(a))
#define debug(a) printf("check%d\n",a)
#define csl ios::sync_with_stdio(false);cin.tie(0);
#define fi(a,b,c) for(int i=a;i<b;i=i+c)
#define fj(a,b,c) for(int j=a;j<b;j+=c)
using namespace std;
 
ll gcd(ll n1,ll n2) {
	if(n1%n2==0)return n2;
	return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent) {
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%MOD;
		base=(base*base)%MOD;
		exponent/=2;
	}
	return ans;
}
ll max(ll a,ll b,ll c) {
	return max(a,max(b,c));
}
int max(int a,int b,int c) {
	return max(a,max(b,c));
}

int main()
{
	string a,b;
	cin>>a;
	cin>>b;
	int counter=0;
	for (int i = 0; i < a.length(); ++i)
	{
		/* code */
		counter += (a[i]!=b[i]);
	}
	cout<<counter;
}

Measured memory_bytes: 3904
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
ll const VMAX = 100000;
double pi = 3.141592653589793238;

int main() {
  ll n, w;
  cin >> n >> w;
  vector<ll> vs(n), ws(n);
  rep(i, n) cin >> ws[i] >> vs[i];

  vector<vector<ll>> dp(n+1, vector<ll>(VMAX+1, INF));
  dp[0][0] = 0;
  // rep(i, n) dp[i][0] = 0;

  rep(i, n) {
    rep(j, VMAX+1) {
      if (j-vs[i] >= 0)
        chmin(dp[i+1][j], dp[i][j-vs[i]] + ws[i]);

      chmin(dp[i+1][j], dp[i][j]);
    }
  }
/*
  rep(i, n+1) {
    rep(j, VMAX+1) cout << dp[i][j] << " ";
    cout << endl;
  } */

  ll ans = 0;

  rep(i, VMAX+1) {
    if (dp[n][i] <= w) ans = i;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 80256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele long long
#define fi first
#define se second
using namespace std;
#define maxn 200010
#define sigma 26
struct BIT{
	ele n,a[maxn];
	inline void init(ele n){
		this->n=n;
		memset(a,0,sizeof(a));
	}
	inline void add(ele i,ele k){
		++i;
		for (int j=i; j<=n; j+=j&(-j)) a[j]+=k;
	}
	inline ele qry(ele i){
		++i;
		ele ans=0;
		for (int j=i; j; j-=j&(-j)) ans+=a[j];
		return ans;
	}
	inline ele qry(ele l,ele r){
		if (l>r) return 0;
		return qry(r)-qry(l-1);
	}
};
ele n,L[sigma],p[sigma][maxn];
pair<ele,ele> a[maxn];
char s[maxn];
BIT b;
int main(){
	scanf("%s",s); n=strlen(s);
	memset(L,0,sizeof(L));
	for (int i=0; i<n; ++i){
		ele c=s[i]-'a';
		p[c][L[c]++]=i;
	}
	ele tmp=0,t1;
	for (int i=0; i<sigma; ++i)
		if (L[i]&1) ++tmp,t1=p[i][L[i]/2];
	if (tmp>1) puts("-1");
	else{
		ele cnt=0;
		for (int c=0; c<sigma; ++c)
			for (int i=0; i<L[c]-1-i; ++i) a[cnt++]=make_pair(p[c][i],p[c][L[c]-1-i]);
		sort(a,a+cnt);
		b.init(n);
		ele ans=0;
		for (int i=0; i<cnt; ++i){
			ans+=b.qry(a[i].fi-1)*2;
			ans+=b.qry(a[i].fi+1,a[i].se-1);
			b.add(a[i].se,1);
		}
		if (tmp)
			for (int i=0; i<cnt; ++i)
				if (t1<a[i].fi || t1>a[i].se) ++ans;
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 45184
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

template<typename T>
struct SegmentTree{
private:
    int n;
    vector<T> node;
    using F=function<T(T,T)>;
    F op;
    T id;
    T get(int a,int b,int k,int l,int r){
        if(b<=l||r<=a)return id;
        if(a<=l&&r<=b){
            return node[k];
        }
        else{
            return op(get(a,b,2*k+1,l,(l+r)/2),get(a,b,2*k+2,(l+r)/2,r));
        }
    }
public:
    SegmentTree(int sz,F op,T id):op(op),id(id){
        n=1;
        while(n<sz)n*=2;
        node.resize(2*n-1,id);
    }
    SegmentTree(const vector<T> & v, F op,T id):SegmentTree(v.size(),op,id){
        for(int i=0;i<v.size();++i){
            node[i+n-1]=v[i];
        }
        for(int i=n-2;i>=0;--i){
            node[i]=op(node[2*i+1],node[2*i+2]);
        }
    }
    void update(int a,T x){
        a+=n-1;
        node[a]=x;
        while(a>0){
            a=(a-1)/2;
            node[a]=op(node[2*a+1],node[2*a+2]);
        }
    }
    T get(int a){
        return node[a+n-1];
    }
    T get(int a,int b){
        return get(a,b,0,0,n);
    }
};

int main(){
    int n,q;
    cin>>n>>q;
    int c[n];
    rep(i,n){
        cin>>c[i];
        --c[i];
    }
    pair<pair<int,int>,int> p[q];
    rep(i,q){
        int l,r;
        cin>>l>>r;
        --l;
        p[i]={{r,l},i};
    }
    sort(p,p+q);
    int ans[q];
    int index[n];
    rep(i,n)index[i]=-1;
    auto op=[](int a,int b)->int{return a+b;};
    SegmentTree<int> segtree(n,op,0);
    int ite=0;
    rep(i,q){
        int l=p[i].first.second;
        int r=p[i].first.first;
        while(ite<r){
            if(index[c[ite]]!=-1){
                segtree.update(index[c[ite]],0);
            }
            index[c[ite]]=ite;
            segtree.update(ite,1);
            ++ite;
        }
        ans[p[i].second]=segtree.get(l,r);
    }
    rep(i,q)cout<<ans[i]<<endl;
}


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

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

class State {
public:
	int cost, x, y;

	State(int _cost, int _x, int _y) {
		cost = _cost;
		x = _x;
		y = _y;
	}
};

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

int main(void) {
	int sx, sy;

	while (cin >> sx >> sy && (sx || sy)) {
		int n;
		cin >> n;

		bool t[10][10][10];
		memset(t, 0, sizeof(t));
		rep(i,n)
		{
			int x, y;
			cin >> x >> y;
			REP(j,-1,2)
				REP(k,-1,2)
				{
					int nx = x + j;
					int ny = y + k;
					if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10)
						t[i][ny][nx] = true;
				}
		}

		queue<State> open;
		open.push(State(-1, sx, sy));
		bool ans = false;

		if (n == 0) {
			cout << "NA\n";
			continue;
		}

		while (!open.empty()) {
			State st = open.front();
			open.pop();

			if (st.cost == n - 1) {
				ans = true;
				break;
			}

			rep(i,12)
			{
				int nx = st.x + dx[i];
				int ny = st.y + dy[i];
				int nc = st.cost + 1;

				if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10 && t[nc][ny][nx]) {
					open.push(State(nc, nx, ny));
					t[nc][ny][nx] = false;
				}
			}
		}
		cout << (ans ? "OK" : "NA") << endl;
	}

	return 0;
}

Measured memory_bytes: 3088
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 2000100;



int main(){
        _
        int n; cin>> n;
        vi a(n);
        for(int i = 0; i<n; i++) cin >> a[i];
        int alice = 0, bob = 0;
        sort(all(a));
        reverse(all(a));
        for(int i = 0; i<n; i++){
            if(i%2==0)alice+=a[i];
            else bob+=a[i];
        }
        cout<<abs(alice-bob)<<endl;


return 0;
}




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

int main() {
    int N;
    cin >> N;
    if (N%10==7){
      cout << "Yes" << endl;
  		return 0;
    }
    N/=10;
    if (N%10==7){
      cout << "Yes" << endl;
   		return 0;
    }
  	N/=10;
    if (N%10==7)
      cout << "Yes" << endl;
  	else 
      cout << "No" << endl;
}



Measured memory_bytes: 3636
x1, y1, x2, y2 = map(int, raw_input().split())
dire = [[1, 1], [-1, 1], [-1, -1], [1, -1]]


if x2 - x1 >= 0:
    xd = 1
else:
    xd = -1
if y2 - y1 >= 0:
    yd = 1
else:
    yd = -1
index = dire.index([xd, yd])
x3 = x2 + dire[(index+1)%4][0] * abs(y1 - y2)
y3 = y2 + dire[(index+1)%4][1] * abs(x1 - x2)
x4 = x3 + dire[(index+2)%4][0] * abs(y2 - y3)
y4 = y3 + dire[(index+2)%4][1] * abs(x2 - x3)
print x3, y3, x4, y4

Measured memory_bytes: 2696
#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
bool compare_by_b(pair<int, long long> a, pair<int, long long> b) {
    if(a.second != b.second) {
        return a.second > b.second;
    } else {
        return a.first > b.first;
    }
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, long long>> AC;
    rep(i, 0, N) {
        pair<int, long long> p;
        long long a;
        cin >> a;
        p.first = 1;
        p.second = a;
        AC.push_back(p);
    }
    rep(i, 0, M) {
        pair<int, long long> p;
        int b;
        long long c;
        cin >> b >> c;
        p.first = b;
        p.second = c;
        AC.push_back(p);
    }
    sort(AC.begin(), AC.end(), compare_by_b);
    int r = 0;
    long long res = 0;
    rep(i, 0, N) {
        int b = AC[i].first;
        long long c = AC[i].second;
        // cout << "i:" << i << ",b:" << b << ",c:" << c << endl;
        if(r + b < N) {
            res += b * c;
            r+=b;
        } else {
            res += (N - r) * c;
            break;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 6536
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int arr[105];
int nums[105];
int main(){
    scanf("%d",&n);
    int best=-1;
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
        best=max(best,arr[x]);
        nums[arr[x]]++;
    }
    
    if (best==1 && n>2){
        printf("Impossible");
        return 0;
    }
    
    int temp;
    for (int x=0;x<=best;x++){
        temp=max(best-x,x);
        if (nums[temp]==0){
            printf("Impossible");
            return 0;
        }
        nums[temp]--;
    }
    
    for (int x=1;x<=((best+1)>>1);x++){
        if (nums[x]){
            printf("Impossible");
            return 0;
        }
    }
            
    printf("Possible");
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	int m1,d1,m2,d2;cin>>m1>>d1>>m2>>d2;
	if(m1!=m2)cout<<"1"<<endl;
	else cout<<"0"<<endl;
}

Measured memory_bytes: 256
N, W = gets.split.map(&:to_i)
WVs = readlines.map{|l| l.split.map(&:to_i)}

class Array
  def cs
    self.inject([0]){|a, x| a << a[-1] + x}
  end
end

w1 = WVs[0][0]
h = WVs.group_by{|w, v| w}
vs = (w1 .. w1 + 3).map{|w| h.has_key?(w) ? h[w].map{|a| a[1]}.sort.reverse : []}
ss = vs.map{|a| a.size}
css = vs.map(&:cs)
ans = 0
(0 .. [N, ss[0]].min).each do |i0|
  break if w1 * i0 > W
  (0 .. [N - i0, ss[1]].min).each do |i1|
    break if w1 * i0 + (w1 + 1) * i1 > W
    (0 .. [N - (i0 + i1), ss[2]].min).each do |i2|
      break if w1 * i0 + (w1 + 1) * i1 + (w1 + 2) * i2 > W
      (0 .. [N - (i0 + i1 + i2), ss[3]].min).each do |i3|
        break if w1 * i0 + (w1 + 1) * i1 + (w1 + 2) * i2 + (w1 + 3) * i3 > W
        v = css[0][i0] + css[1][i1] + css[2][i2] + css[3][i3]
        ans = v if v > ans
      end
    end
  end
end
puts ans

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

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

    if (n == 1){
        int y;
        cin >> y;
        cout << abs(w - y) << endl;
        return 0;
    }

    int gomi;
    for (int i = 0; i < n - 2; i++)
        cin >> gomi;
    int x, y;
    cin >> x >> y;

    cout << max(abs(x - y), abs(y - w)) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;  
void dfs(vector<vector<int> >&graph,int src,vector<int> &vis){
	vis[src]=1;
	for(int i=0;i<graph[src].size();i++){
		if(vis[graph[src][i]]==0){
			dfs(graph,graph[src][i],vis);
		}
	}
}
int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<vector<int> > graph(n+1);
    for(int i=0;i<m;i++){
    	int a,b;
    	cin>>a>>b;
    	graph[a].push_back(b);
    	graph[b].push_back(a);
	}
	vector<int> vis(n+1,0);
	vector<int> ans;
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			ans.push_back(i);
			dfs(graph,i,vis);
		}
	}
	cout<<(ans.size()-1)<<"\n";
	return 0; 
} 

Measured memory_bytes: 10292
xyabc = list(map(int, input().split()))
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

max_p = sorted(p, reverse=True)[:xyabc[0]]
max_q = sorted(q, reverse=True)[:xyabc[1]]
if len(r) > xyabc[0] + xyabc[1]:
    max_r = sorted(r, reverse=True)[:xyabc[0] + xyabc[1]]
else: 
    max_r = sorted(r, reverse=True)
apple_list = sorted(max_p + max_q + max_r, reverse=True)[:xyabc[0] + xyabc[1]]
print(sum(apple_list))

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

using namespace std;
typedef long long ll;

#define cout (cout << setprecision(12))

int main() {
    int n, m, tmp, sum = 0;
    vector<int> a;

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        a.push_back(tmp);
        sum += tmp;
    }

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());

    string ans = "Yes";
    for (int i = 0; i < m; i++) {
//        cout << a[i] << " " << sum / (4.0 * m) << endl;
        if (1.0 * a[i] < sum / (4.0 * m)) {
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
#include<set>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
llfor;///////////////////////////////////////////////////////////
int main(){
 ll n,m;sc(n);sc(m);
 ll ans=0;
 if(abs(n-m)>1){
  pr(ans);
  return 0;
 }
 ll dog=1;
 rep(i,0,n){dog=(dog*(n-i))%(llpow(10,9)+7);}
 ll monk=1;
 rep(i,0,m){monk=(monk*(m-i))%(llpow(10,9)+7);}
 ans=(dog*monk)%(llpow(10,9)+7);
 //pr(dog);pr(monk);
 //猿全体、犬全体の配置を考える
 if(n==m){
  ans*=2;
 }
 pr(ans%(llpow(10,9)+7));
  
return 0;}

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

long long f(int n) {
  return (long long)(n <= 1 ? 0 : (ll)(n * (ll)(n-1)) / 2);
}

int main() {
  ll n; cin >>n;
  vector<ll> a(n);
  map<ll, ll> b;
  for (int i = 0; i < n; i++) {
    cin >>a[i];
    b[a[i]]++;
  }

  ll ret = 0;
  map<ll, ll> c, d;
  for (auto i : b) {
    ret += f(i.second);
    c[i.first] = f(i.second);
    d[i.first] = f(i.second-1);
  }

  for (int i = 0; i < n; i++) {
    cout << ret - c[a[i]] + d[a[i]] << endl;
  }
  return 0;
}

Measured memory_bytes: 28600
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = 1
    for i in range(n):
        if a[i]%2 == 1:
            res *= 1
        else:
            res *= 2
    print(3**n-res)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
//minamoto
#include<bits/stdc++.h>
#define R register
#define pb push_back
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
vector<string>s;string t,ans,cur;int n,m,cnt;
void solve(string &s){
	vector<int>p1,p2;string t="";
	fp(i,0,s.size()-1)(s[i]=='a'?p1:p2).pb(i);
	if(s[0]=='a'){
		int las=-1;
		fp(i,0,p1.size()-1)if(p1[i]>las)las=p2[i],t+="ab";
	}else{
		fp(i,0,p1.size()-1){
			string p="";
			int x=i,y=i;
			while(233){
				if(x<p1.size()&&(y==p2.size()||p1[x]<p2[y]))p+='a',++x;
				else if(y<p2.size())p+='b',++y;
				else break;
			}
			if(p>t)t=p;
		}
	}
	s=t;
}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d",&n),cin>>t;
	for(auto v:t){
		cnt+=v=='a'?1:-1,cur+=v;
		if(!cnt)s.pb(cur),cur="";
	}
	for(auto &v:s)solve(v);
	reverse(s.begin(),s.end());
	for(auto v:s){
		int fl=1;
		fp(i,0,min(v.size(),ans.size())-1)
			if(v[i]!=ans[i]){
				if(v[i]<ans[i])fl=0;
				break;
			}
		if(fl)ans=v+ans;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
}

int32_t main()
{
	//c_p_c();
	string s, t;
	cin >> s >> t;
	int n = s.length();
	int m = t.length();
	int ans = 10000;
	for(int i=0;i<(n-m+1);i++){
		int temp = i;
		int diff = 0;
		for(int j=0;j<m;j++){
			if(s[temp]!=t[j]){
			    diff++;
			}
				temp++;
		}
		ans = min(ans, diff);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3592
n,m,s=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(n)]
g=[[] for _ in range(n)]
maxs=0
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])
    maxs+=a

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*(maxs+1) for _ in range(n)]
s=min(s,maxs)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    c,d=cd[v]
    nss=min(ss+c,maxs)
    if ans[v][nss]>t+d:
        heappush(todo,[t+d,v,nss])
        ans[v][nss]=t+d
for i in range(1,n):
    print(min(ans[i]))



Measured memory_bytes: 104296
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n = int(input())
s = input()
if n % 2 != 0:
    print("No")
else:
    if s[:n // 2] == s[n // 2:]:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 5692
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			if(n == 0){
				break;
			}
			for(int i = 0;i < n;i++){
				int m = scan.nextInt();
				int e = scan.nextInt();
				int j = scan.nextInt();
				if(m == 100 || e == 100 || j == 100){
					System.out.println("A");
				}else{
					if(m + e >= 180){
						System.out.println("A");
					}else{
						int ave = (m + e + j) / 3;
						if(ave >= 80){
							System.out.println("A");
						}else if(ave >= 70){
							System.out.println("B");
						}else if(ave >= 50 && (m >= 80 || e >= 80)){
							System.out.println("B");
						}else{
							System.out.println("C");
						}
					}
				}
			}
		}
	}
}

Measured memory_bytes: 28268
//
// Created by kashi on 26-05-2020.
//
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define Endl endl

    int main(){
        string s,t;
        cin>>s>>t;
        t.erase(t.end()-1);
        if(s==t)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        return 0;

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
// (setq-default c-basic-offset 2)

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

  map<string, int> memo;
  int m = 0;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    memo[s]++;
    m = max(m, memo[s]);
  }

  vector<string> ret;
  for (auto& [k, v] : memo) {
    if (v == m) ret.push_back(k);
  }
  sort(ret.begin(), ret.end());
  for (auto& s : ret) {
    cout << s << endl;
  }
  return 0;
}


Measured memory_bytes: 27228
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=nxt(),k=nxt();
    ll ans=0;
    ll mod=1e9+7;
    for(ll i=k;i<=n+1;i++)
    {
        ll mx=(n*(n+1))/2-((n-i)*(n-i+1))/2;
        ll mn=(i*(i-1))/2;
        ll x=mx-mn+1;
        (ans+=x)%=mod;
        //cout<<mx<<" "<<mn<<endl;
    }
    cout<<ans<<endl;
    
    
    
    
    return 0;   
}




 
 


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
typedef pair < ll, double > pii;
const int maxn = 500005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

pii q[maxn];
int n, L, v, t;
int l = 1, r = 0;
ll pourWater, remainWater = 0;
double temperature = 0;

int main() {
    n = read(), L = read();
    for (reg int i = 1; i <= n; i++) {
        t = read(), v = read();
        while (remainWater + v > L) {
            pourWater = min(q[l].first, remainWater + v - L);
            q[l].first -= pourWater;
            remainWater -= pourWater;
            temperature -= q[l].second * pourWater;
            if (!q[l].first) l++;
        }
        remainWater += v, temperature += 1LL * t * v;
        q[++r] = make_pair(v, t);
        while (l < r && q[r].second < q[r - 1].second) {
            q[r - 1].second = (q[r].first * q[r].second + q[r - 1].first * q[r - 1].second) / (q[r].first + q[r - 1].first);
            q[r - 1].first += q[r].first; r--;
        }
        printf("%.7f\n", temperature / L);
    }
    return 0;
}


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

int main() {
    string s;
    cin >> s;
    int tmp_count = 0;
    int max_count = 0;
    for (char x: s) {
        if (x == 'A' || x == 'C' || x == 'G' || x == 'T') {
            tmp_count += 1;
        } else {
            tmp_count = 0;
        }
        if (max_count < tmp_count) {
            max_count = tmp_count;
        }
    }
    cout << max_count;
}

Measured memory_bytes: 256
import collections

def WizMove(sh,sw,cost):
    q.append([sh,sw])
    s[sh][sw] = cost
    nextQ.append([sh,sw])

h,w = list(map(int,input().split()))

c = list(map(int,input().split()))
c = [c[0] - 1,c[1] - 1]
d = list(map(int,input().split()))
d = [d[0] - 1,d[1] - 1]

s = []

for i in range(h):
    s.append(list(input()))

q = collections.deque()
nextQ = collections.deque()

q.append(c)
nextQ.append(c)
s[c[0]][c[1]] = 0
cost = 0

while len(nextQ) > 0:
    while len(q) > 0:
        wiz = q.popleft()
        if wiz[0] > 0:
            if s[wiz[0] - 1][wiz[1]] == ".":
                WizMove(wiz[0] - 1 , wiz[1] , cost)
        if wiz[0] < h - 1:
            if s[wiz[0] + 1][wiz[1]] == ".":
                WizMove(wiz[0] + 1 , wiz[1] , cost)
        if wiz[1] > 0:
            if s[wiz[0]][wiz[1] - 1] == ".":
                WizMove(wiz[0] , wiz[1] - 1 , cost)
        if wiz[1] < w - 1:
            if s[wiz[0]][wiz[1] + 1] == ".":
                WizMove(wiz[0] , wiz[1] + 1 , cost)
    cost += 1
    count = len(nextQ)
    for k in range(count):
        wiz = nextQ.popleft()
        for i in range(max(0,wiz[0]-2),min(h,wiz[0] + 3)):
            for j in range(max(0,wiz[1]-2),min(w,wiz[1] + 3)):
                if s[i][j] == ".":
                    WizMove(i,j,cost)

ans = s[d[0]][d[1]]
if ans == ".":
    ans = -1
print(ans)

Measured memory_bytes: 175916
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _h cout<<"here"<<endl;
#define fill(a,v) memset(a,v,sizeof(a));
#define all(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(i,n) cout<<a[i]<<" \n"[i==n-1];// printf("%s\n"," " );
#define ff first
#define ss second
#define pu push_back
const int inf = 1e9+10;
const ll INF = 1e16+10;
const int MOD = 1e9+7;
const int MAXN = 2e5+10;

int main(){
    ll n;
    cin>>n;
    vector<ll> v(n+1,0);
    rep(i,n){
        int in;
        cin>>in;
        v[in]=i+1;
    }
    rep(i,n){
        cout<<v[i+1]<<" ";
    }
}


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

int main() {
 int n,m; cin >> n >> m;
 vector<string> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
      a[i]=a[i]+'#';
      a[i]='#'+a[i];
  }

  for(int i=0;i<m+2;i++){
  cout << '#';
  }
  cout << endl;
  for(int i=0;i<n;i++){
  cout << a[i] << endl;
  }
  for(int i=0;i<m+2;i++){
  cout << '#';
  }
  cout << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
long  mp[maxn];
long long  jump[maxn][35];
long long ans;
int main()
{
//    freopen("in.txt","r",stdin);
    long long  n,l, q,a,b;
    scanf("%lld",&n);
    for(int i=1; i<=n; ++i)
        scanf("%lld",&mp[i]);
    scanf("%lld",&l);
    int rmost=1;
    for(int i=1;i<=n;++i)
    {
        while(rmost<=n&&mp[rmost]-mp[i]<=l)
            rmost++;
        jump[i][0]=rmost-1;
    }
    for(int j=1;j<=30;++j)
    {
        for(int i=1;i<=n;++i)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }
    scanf("%lld",&q);
    for(int i=1; i<=q; ++i)
    {
        ans=0;
        scanf("%lld%lld",&a,&b);
        if(a>b)
        {
            int t=a;
            a=b;
            b=t;
        }
        int now=a;
        for(int i=30;i>=0;--i)
        {
            if(jump[now][i]<b)
            {
                ans+=(1<<i);
                now=jump[now][i];
            }
        }
        printf("%lld\n",ans+1);
    }
    return 0;
}


Measured memory_bytes: 28928
#include<stdio.h>
int main()
{
	int a[5],i,g,t,p,r[5];
	while(1){
		g=p=t=0;
		scanf("%d",&a[0]);
		if(a[0]==0){
			break;
		}
		scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]);
		for(i=0;i<5;i++){
			switch(a[i]){
			case 1:
				g++;
				break;
			case 2:
				t++;
				break;
			case 3:
				p++;
				break;
			}
		}
		if((g!=0&&t!=0&&p!=0)||g==5||t==5||p==5){
			for(i=0;i<5;i++){
				r[i]=3;
			}
		}else if(g==0){
			for(i=0;i<5;i++){
				if(a[i]==2){
					r[i]=1;
				}else{
					r[i]=2;
				}
			}
		}else if(t==0){
			for(i=0;i<5;i++){
				if(a[i]==3){
					r[i]=1;
				}else{
					r[i]=2;
				}
			}
		}else{
			for(i=0;i<5;i++){
				if(a[i]==1){
					r[i]=1;
				}else{
					r[i]=2;
				}
			}
		}
		for(i=0;i<5;i++){
			printf("%d\n",r[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 2732
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                res = res + '0';
            }
            if (s.charAt(i) == '1') {
                res = res + '1';
            }
            if (s.charAt(i) == 'B' && res.length() > 0) {
                res = res.substring(0, res.length() - 1);
            }
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 27020
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long v = sc.nextInt();
        long b = sc.nextInt();
        long w = sc.nextInt();
        long t = sc.nextInt();
        
        long mae;
        long ato;
        if (a < b) {
            mae = a + v * t;
            ato = b + w * t;
        } else {
            mae = a - v * t;
            ato = b - w * t;
        }
        
        
        boolean ok = false;
        if (a < b) {
            if (mae >= ato) ok = true;
        } else {
            if (ato >= mae) ok = true;
        }
        if (ok) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 35736
#include<stdio.h>

int ceil_10(int order){
  if(order % 10 == 0) return order;
  else return (int)(((double)(order) * 0.1 + 1)) * 10;
}

int main(){
  int i, j, memory;
  int total = 0;
  int max = 0;
  int ceil_min[5]= {};
  int order[5] = {};
  
  for(i = 0; i < 5; i++){
    scanf("%d", &order[i]);
    ceil_min[i] = ceil_10(order[i]);
  }
  
  for(i = 0; i < 5; i++){
    if(max < ceil_min[i] - order[i]){
      max = ceil_min[i] - order[i];
      memory = i;
    }
  }
  
  for(j = 0; j < 5; j++){
    if(j == memory){
      total += order[j];
    }
    else{
      total += ceil_min[j];
    }
  }
  printf("%d", total);

  return 0;
}


Measured memory_bytes: 128
#include <cstdio>

long maks(long a, long b, long c);

int main() {
    int t;
    scanf("%d", &t);
    for (;t > 0; t--) {
        long a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a = a*a;
        b = b*b;
        c = c*c;
        if ( maks(a, b, c) == (a + b + c - maks(a, b, c))) {
             printf("YES\n");
        } else printf("NO\n");
    }
    return 0;
}

long maks(long a, long b, long c) {
     if ((a > b)&&(a > c)) {return a;}
     else if ((b > a)&&(b > c)) {return b;}
     else {return c;}
}

Measured memory_bytes: 1008
package main

import (
	"fmt"
)

const MOD = 1000000007

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

func main() {
	var N int
	var S string
	fmt.Scanf("%d\n%s\n", &N, &S)

	rs := []rune(S)
	cnt := N
	for i := 1; i < N; i++ {
		if rs[i-1] == rs[i] {
			cnt--
		}
	}
	fmt.Println(cnt)

}


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

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
        int n, d, a;
        cin >> n >> d >> a;

        vector<pair<ll, ll>> p(n);
        REP(i, n) {
                cin >> p[i].first >> p[i].second;
        }

        sort(p.begin(), p.end());

        vector<ll> x(n), h(n);
        REP(i, n) {
                x[i] = p[i].first;
                h[i] = (p[i].second + a - 1) / a;
        }

        vector<int> reach(n);
        for (int l = 0, r = 0; l < n; l++) {
                while (r < n && x[r] - x[l] <= 2 * d) {
                        r++;
                }
                reach[l] = r;
        }

        ll ans = 0, cur = 0;
        vector<ll> m(n + 1, 0);
        REP(i, n) {
                cur -= m[i];

                ll t = max(0LL, h[i] - cur);
                ans += t;

                cur += t;
                m[reach[i]] += t;
        }

        cout << ans << endl;
        
        return 0;
}


Measured memory_bytes: 8832
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=200000+10,lgn=20;
int f[maxn*5],g[maxn*5],mi[maxn],left[maxn][lgn+10],right[maxn][lgn+10],v[lgn+10],x[maxn];
int i,j,k,l,r,s,t,n,m,tot,top;
int main(){
	scanf("%d%d",&n,&t);
	fo(i,1,n) scanf("%d",&x[i]);
	v[0]=t;
	t/=2;
	while (t){
		v[++top]=t;
		t/=2;
	}
	v[++top]=0;
	reverse(v,v+top+1);
	fo(j,0,top){
		left[1][j]=1;
		fo(i,2,n)
			if (x[i]-x[i-1]<=v[j]) left[i][j]=left[i-1][j];else left[i][j]=i;
		right[n][j]=n;
		fd(i,n-1,1)
			if (x[i+1]-x[i]<=v[j]) right[i][j]=right[i+1][j];else right[i][j]=i;
	}
	f[0]=0;
	g[0]=n+1;
	fo(s,1,(1<<(top+1))-1){
		f[s]=0;
		g[s]=n+1;
		fo(i,0,top)
			if (s&(1<<i)){
				r=s^(1<<i);
				if (f[r]==n) f[s]=n;
				else f[s]=max(f[s],right[f[r]+1][i]);
				if (g[r]==1) g[s]=1;
				else g[s]=min(g[s],left[g[r]-1][i]);
			}
	}
	fo(i,0,n) mi[i]=n+2;
	fo(i,0,(1<<top)-1){
		r=((1<<top)-1)^i;
		mi[f[i]]=min(mi[f[i]],g[r]);
	}
	fd(i,n-1,0) mi[i]=min(mi[i],mi[i+1]);
	fo(i,1,n){
		l=left[i][top];r=right[i][top];
		if (mi[l-1]<=r+1) printf("Possible\n");else printf("Impossible\n");
	}
}

Measured memory_bytes: 57600
//#include <algorithm>
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <map>



typedef unsigned long long ULONG;
using namespace std;



int main(void) {
	ULONG N;
	cin >> N;

	map<ULONG, int> primes;

	// decompositPrime
	ULONG a = 2;
	// √n ≧ a ( n ≧ a * a ) の間ループ処理
	while (N >= a * a) {
		// a で割り切れたら、a は素因数
		// そして、割られる数を a で割る
		// a で割り切れなかったら、 a を 1 増加させる
		if (N % a == 0) {
			if (primes[a] == 0) {
				primes[a] = 1;
			}
			else {
				primes[a]++;
			}
			N /= a;
		}
		else {
			a++;
		}
	}
	// 最後に残った n は素因数
	if (N > 1 && primes[N] == 0) {
		primes[N] = 1;
	}
	else if(N > 1){
		primes[N]++;
	}


	// 素因数を数える
	auto begin = primes.begin();
	auto end = primes.end();
#ifdef _DBG_
	for (map<ULONG, int>::iterator iter = begin; iter != end; iter++) {
		cout << "Prime:" << iter->first << "Val" << iter->second << endl;
	}


	int aaa;
	cin >> aaa;
#endif


	// 素因数を減らしていく
	int count = 0;
	
	for (map<ULONG, int>::iterator iter = begin; iter != end; iter++) {
		int firstNum = iter->second;
		int prevCount = 1;
		while (firstNum >= prevCount) {
			count++;
			firstNum -= prevCount;
			prevCount++;
		}
	}

	cout << count;

	return 0;
}

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

typedef long long ll;

const int MOD = 998244353;

ll fexp(ll x, ll e) {
	ll ans = 1;
	for(; e > 0; e /= 2) {
		if(e & 1) {
			ans = ans * x % MOD;
		}
		x = x * x % MOD;
	}
	return ans;
}

ll fat[300300], ifat[300300];
ll comb(int n, int a) {
	return fat[n] * ifat[a] % MOD * ifat[n - a] % MOD;
}

int main() {
	fat[0] = ifat[0] = 1;
	for(int i = 1; i < 300300; i++) {
		fat[i] = fat[i - 1] * i % MOD;
		ifat[i] = fexp(fat[i], MOD - 2);
	}
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n;
	std::cin >> n;
	ll a, b;
	std::cin >> a >> b;
	ll k;
	std::cin >> k;
	ll ans = 0;
	for(int i = 0; i <= n; i++) {
		ll need = k - a * i;
		if(need < 0) {
			break;
		} else if(need % b != 0 || need / b > n) {
			continue;
		}
		need = need / b;
		ans = (ans + comb(n, i) * comb(n, need)) % MOD;
	}
	std::cout << ans << std::endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  ll h, w;
  cin >> h >> w;

  ll ans = (h * w + 1) / 2;
  if (h == 1 || w == 1) ans = 1;

  cout << ans << endl;

  return 0;
}


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

int max_(int a, int b){
	if(a >= b) return a;
	return b;
}

int DFS(vector <int> adj[], int dp[], int u, int *ans){
	if(dp[u] != -1) return dp[u];
	int m = adj[u].size();
	dp[u] = 0;
	for(int i = 0; i < m; i++){
		dp[u] = max_(dp[u], 1 + DFS(adj, dp, adj[u][i], ans)); 
	}
	if(*ans < dp[u]) *ans = dp[u];
	return dp[u];
}

int main(){
	int n, m; cin>>n>>m;
	vector <int> adj[n];
	for(int i = 0; i < m; i++){
		int a, b; cin>>a>>b;
		adj[a-1].push_back(b-1);
	}
	int dp[n];
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	for(int i = 0; i < n; i++) DFS(adj, dp, i, &ans);	
	cout<<ans<<endl;
}

Measured memory_bytes: 9472
#include <iostream>
#include <vector>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)

vector<int> sieve_of_eratosthenes() {
	int n = 1000000;
	vector<int> primes(n);
	for (int i = 2; i < n; i++)primes[i] = i;
	for (int i = 2; i*i < n; i++) {
		if (primes[i]) {
			for (int j = i * i; j < n; j += i) primes[j] = 0;
		}
	}
	return primes;
}

int main() {
	auto p = sieve_of_eratosthenes();

	vector<int> q(1000000);
	rep(i, 3, p.size()) {
		if (p[i] && p[(p[i] + 1) / 2]) {
			q[i] = 1;
		}
	}
	rep(i, 1, q.size())	q[i] += q[i - 1];

	ll Q; cin >> Q;
	rep(i, 0, Q) {
		ll l, r; cin >> l >> r;
		cout << q[r] - q[l - 1] << endl;
	}

	return 0;
}

Measured memory_bytes: 8448
from sys import exit

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
ab = sorted(ab, key = lambda x : x[1])

total = 0
for a,b in ab:
    total += a
    if total <= b:
        continue
    else:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 55264
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;i<(n);i++)
string s[20];
bool f[20][20];
int ans=0,h,w;
struct Corr{
    int y;
    int x;
    int depth;
};
queue<Corr> q;

int bfs(int y, int x){
  if(s[y].at(x)=='#') return 0;
  REP(i,20) REP(j,20) f[i][j]=0;
  Corr start={y,x,0};q.push(start);f[y][x]=1;
  //cout<<"start,x:"<<start.x<<" y:"<<start.y<<" d:"<<start.depth<<endl;
  
  while(!q.empty()){
    Corr now=q.front();q.pop();
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    //cout<<" now,x:"<<now.x<<" y:"<<now.y<<" d:"<<now.depth<<endl;
    
    REP(i,4){
      Corr next={now.y+dy[i],now.x+dx[i],now.depth+1};
      if(next.x>=0&&next.x<w&&next.y>=0&&next.y<h
         &&s[next.y].at(next.x)=='.'&&f[next.y][next.x]==0){
        f[next.y][next.x]=1;
        ans=max(ans,now.depth+1);
        q.push(next);
      }
    }
  }
  
}

int main(){
  cin>>h>>w;
  REP(i,h) cin>>s[i];
  REP(i,h) REP(j,w) bfs(i,j);

  cout<<ans;
}

Measured memory_bytes: 256
module Main

open System

let nm =
    Console.ReadLine().Split(' ')
        |> Array.map int

let mutable xs = Array2D.zeroCreate nm.[0] nm.[0]

for _ in 1..nm.[1] do
    let ab =
        Console.ReadLine().Split(' ')
            |> Array.map int

    let a = ab.[0] - 1
    let b = ab.[1] - 1

    xs.[a, b] <- true
    xs.[b, a] <- true


let mutable ts = [| for _ in 1..nm.[0] -> false |]

let rec solve idx =
    ts.[idx] <- true

    if Array.forall (fun x -> x) ts then
        1
    else
        let mutable res = 0

        for i in 0..(nm.[0] - 1) do
            let x = xs.[idx, i]
            if x && not ts.[i] then
                res <- res + solve i
                ts.[i] <- false

        res

Console.WriteLine(solve 0)


Measured memory_bytes: 13396