akhauriyash/Code-Regression huggingface dataset:
n=int(input())
l=[]
lis=[]
for _ in range(n):
    a=int(input())
    l.append(a)

    li=[]
    for _ in range(a):
        c,d=map(int,input().split())
        li.append([c,d])
    lis.append(li)

ans=-1
for i in range(2**n-1,-1,-1):
    mark=bin(i)[2:]
    mark=(n-len(mark))*'0'+mark
    s=0
    record=[-1]*n
    f=1
    for j in range(n):
        for k in range(l[j]):
            number=lis[j][k][0]-1
            hou=lis[j][k][1]
            if int(mark[j])==1:
                if record[number]==-1:
                    record[number]=hou
                elif record[number]!=hou:f=0
            if f==0:break
        if f == 0: break

    if f==1:
        F=True
        for i in range(n):
            if record[i]!=-1:
                if record[i]!=int(mark[i]):
                    F=False
                    break
        if F==True:
            print(mark.count('1'))
            exit()














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

int main(){
  string a,b;
  cin >> a >> b;
  string s=a+b;
  int x=0;
  for (int i=0;i<s.length();++i){
     x=x*10+(s[i]-'0');
  }
  for (int i=0;i<1000;++i){
     if (x==i*i){
        cout << "Yes" << endl;
        return 0;
     }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

int i_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int i_asort(const void* a, const void* b) {
	return(*(int*)a - *(int*)b);
}

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}
// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
ll _pfact(ll a);
static ll pf[100000000];
static ll pc;

ll _pfact(ll a) {
	long i, r;
	if (a % 2 == 0) {
		pf[pc] = 2; pc++;
		return(_pfact(a / 2));
	}
	r = sqrt(a);
	for (i = 3; i <= r; i += 2) {
		if (a % i == 0) {
			pf[pc] = i; pc++;
			return(_pfact(a / i));
		}
	}
	if (a != 1) {
		pf[pc] = a; pc++;
	}
	return 0;

}


#pragma endregion


//ABC  115-C Chrismas Eve

int main(void) {
	int        i, n, k;
	int        h[100001];

	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &h[i]);

	qsort(h, n, sizeof(int), i_asort);

	int min = 1000000001;
	for (i = 0; i <= n - k; i++) 
		min = _min(h[i + k - 1] - h[i], min);
	

	printf("\n%d\n", min);
	return 0;
}


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

struct UnionFind {
  UnionFind () {}
  UnionFind (int n) { init(n); }

  vector<int> parent, rank;

  void init(int n) {
    parent.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; ++i) {
      parent[i] = i; rank[i] = 1;
    }
  }

  int root(int v) {
    return parent[v] = (parent[v] == v ? v : root(parent[v]));
  }

  bool same(int u, int v) {
    return root(u) == root(v);
  }

  bool is_root(int v) {
    return root(v) == v;
  }

  void unite(int u, int v) {
    if (same(u, v)) return;
    u = root(u); v = root(v);

    if (rank[u] > rank[v]) swap(u, v);
    rank[u] += rank[v];
    parent[v] = u;
  }

  int element_count(int v) {
    return rank[root(v)];
  }
};

int main() {
  int n, k, l;
  cin >> n >> k >> l;

  UnionFind a(n), b(n);

  for (int i = 0; i < k; ++i) {
    int u, v;
    cin >> u >> v;
    u--; v--;

    a.unite(u, v);
  }

  for (int i = 0; i < l; ++i) {
    int u, v;
    cin >> u >> v;
    u--; v--;

    b.unite(u, v);
  }

  map<pair<int, int>, int> m;
  for (int i = 0; i < n; ++i) {
    m[make_pair(a.root(i), b.root(i))]++;
  }

  for (int i = 0; i < n; ++i) {
    cout << m[make_pair(a.root(i), b.root(i))] << (i + 1 == n ? "\n" : " ");
  }
}


Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
int main() {
  int n, x, ans = 0, d;
  cin >> n >> x;
  vector<int> l(n);
  REP(i, n) cin >> l[i];
  REP(i, n + 1) {
    if (i == 0) { d = 0; ans++; }
    else { d = d + l[i - 1]; if (d <= x) ans++; }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::stdin;

fn main () {
    let mut nk = String::new();
    stdin().read_line(&mut nk).unwrap();
    let nk: Vec<usize> = nk.trim().split_whitespace().flat_map(str::parse).collect();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();


    let (n, k) = (nk[0], nk[1]);
    let s: String = s.trim().chars().enumerate().map(|(i, c)| if i + 1 == k { (c as u8 + 32) as char } else { c }).collect();
    println!("{}", s);
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;
const ll MAX = 61;

ll A[200005];
ll B[200005][MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    REP(i, N) {
        cin >> A[i];
        A[i]--;
        B[i][0] = A[i];
    }
    FOR(i, MAX, 1) {
        REP(j, N) {
            B[j][i] = B[B[j][i - 1]][i - 1];
        }
    }

    ll ans = 0;
    REP(i, MAX) {
        if (((K >> i) & 1) == 0)
            continue;
        ans = B[ans][i];
    }
    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 100504
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5, mod = 1e9 + 7;
int n, m, a[maxn + 10], b[maxn + 10];
int dcnt;
int s[maxn + 10], scnt;
int ans = 1, f[maxn + 10];

struct data {
	int x, y;
	bool operator < (const data &t) const {
		return x == t.x ? y < t.y : x < t.x;
	}
	bool operator == (const data &t) const {
		return x == t.x && y == t.y;
	}

}d[maxn + 10];

namespace bit {
	int c[maxn + 10];

	void modify(int p, int v) {
		for (; p <= scnt; p += p & -p) c[p] = (c[p] + v) % mod;
	}

	int query(int p) {
		int ans = 0;
		for (; p; p -= p & -p) ans = (ans + c[p]) % mod;
		return ans;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
	for (int i = 1; i <= n; ++i) {
		int p = lower_bound(b + 1, b + m + 1, a[i]) - b - 1;
		if (p >= 1 && p < m)
			d[++dcnt] = (data){a[i] - b[p], b[p + 1] - a[i]};
	}
	sort(d + 1, d + dcnt + 1);
	dcnt = unique(d + 1, d + dcnt + 1) - d - 1;
	for (int i = 1; i <= dcnt; ++i) s[++scnt] = d[i].y;
	sort(s + 1, s + scnt + 1);
	scnt = unique(s + 1, s + scnt + 1) - s - 1;
	for (int i = 1; i <= dcnt; ++i)
		d[i].y = lower_bound(s + 1, s + scnt + 1, d[i].y) - s;
	sort(d + 1, d + dcnt + 1);
	for (int i = 1, lst; i <= dcnt; i = lst) {
		for (lst = i; lst <= dcnt && d[lst].x == d[i].x; ++lst);
		for (int j = i; j < lst; ++j) {
			f[j] = (1 + bit::query(d[j].y - 1)) % mod;
			ans = (ans + f[j]) % mod;
		}
		for (int j = i; j < lst; ++j)
			bit::modify(d[j].y, f[j]);
	}
	printf("%d", ans);
}


Measured memory_bytes: 2688
#include<iostream>
#include<cstring>

int num[101];
int n;
long long memo[21][101];

long long calc(int sum, int cnt){
	long long res = 0;

	if (sum < 0 || sum > 20)return 0;
	if (cnt == n - 1){
		if (sum == num[n - 1])return memo[sum][cnt] = 1;
		return 0;
	}

	if (memo[sum][cnt])return memo[sum][cnt];


	res += calc(sum + num[cnt], cnt + 1);
	if (cnt != 0)res += calc(sum - num[cnt], cnt + 1);

	return memo[sum][cnt] = res;
}

int main(){

	std::cin >> n;
	for (int i = 0; i < n; i++)std::cin >> num[i];

	memset(memo, 0, sizeof(memo));

	std::cout << calc(0, 0) << std::endl;

	return 0;
}

Measured memory_bytes: 1184
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

long long n;
long long a[3], d;

bool read() {
  if (scanf("%lld%lld%lld%lld%lld", &n, &a[0], &a[1], &a[2], &d) < 5) {
    return false;
  }
  return true;
}

const vector<long long> xs = {2, 3, 5};

map<long long, long long> dp;

long long getDp(long long n) {
  if (dp.count(n)) {
    return dp[n];
  }
  auto &cur = dp[n];
  cur = infll;
  if ((ld) n * d < infll) {
    cur = min(cur, n * d);
  }
  for (int i = 0; i < 3; i++) {
    long long x = xs[i];
    long long b = a[i];
    long long k = n % x;
    cur = min(cur, k * d + b + getDp(n / x));
    k = (x - k) % x;
    cur = min(cur, k * d + b + getDp((n + x - 1) / x));
  }
  return cur;
}

void solve() {
  dp.clear();
  dp[0] = 0;
  dp[1] = d;
  printf("%lld\n", getDp(n));
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  int t;
  scanf("%d", &t);
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


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

int main(){
    int n,sum=0;
    cin >> n;
    vector<int> b(n-1);
    vector<int> a(n,0);
    rep(i,n-1) cin >> b[i];
    a[0] = b[0];
    int m_b = b[0];
    for(int i=1;i<n-1;i++){
        if(m_b > b[i]) a[i] = b[i];
        else a[i] = m_b;
        m_b = b[i];
    }
    a[n-1] = b[n-2];
    for(auto i: a){
        sum+=i;
    }
    cout << sum << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define re register
int cnt[310],f[1510][1010],g[1510][1010],g1[1510][1010],cct;
const int mod=998244353,B=610;
char ss[310];
int main()
{
	re int n,k;
	scanf("%s%d",ss+1,&k);
	n=strlen(ss+1);
	if(ss[1]=='1')
	{
		re int i=1;cct++;
		while(i<=n&&ss[i]=='1')cnt[cct]++,i++;
	}else cct++;
	for(re int i=1;i<=n;i++)
	if(ss[i]=='0'){
		i++;cct++;
		while(i<=n&&ss[i]=='1')cnt[cct]++,i++;
		i--;
	}
	f[B][0]=1;
	for(re int i=cct;i;i--)
	{//printf("****%d %d\n",i,cnt[i]);
		for(re int j=0;j<=n;j++)
			for(re int k=0;k<=n;k++)
			{
				g[j+B][k]=g1[j+B][k]=f[j+B][k];
				g[j+B][k]=(g[j+B][k]+g[j+B-1][k])%mod;
			}
		for(re int j=n;j>=0;j--)
			for(re int k=0;k<=n;k++)
			{
				if(k)g1[j+B][k]=(g1[j+B][k]+g1[j+B+1][k-1])%mod;
			}
		for(re int j=0;j<=n;j++)
			for(re int k=0;k<=n;k++)
			{
				f[j+B][k]=0;
				f[j+B][k]=(1ll*f[j+B][k]+g[j+B-1][k]+(mod-g[j+B-cnt[i]-1][k])+g1[j+B][k])%mod;
			//	if(f[j+B][k])printf("****%d %d %d %d %d\n",j,k,f[j+B][k],g[j+B-1][k],g1[j+B][k]);
			}
	}
	re int ans=0;
	for(re int i=0;i<=k&&i<=n;i++)
	{
		ans=(ans+f[B][i])%mod;
	}
	printf("%d\n",ans);
}

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

using namespace std;

void solve()
{
    int a, b;
    cin >> a >> b;
    for (int i = 0; i <= a; i++)
    {
        int j = a - i;
        if (i * 2 + j * 4 == b)
        {
            cout << "Yes";
            return;
        }
    }
    cout << "No";
}

int main()
{
    int tt = 1;
    //cin >> tt;
    while (tt--) solve();
}

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

using namespace std;

long long int arr[1000000][2],ans[105][100003];
vector<long long int>crr;
long long int W,N;

long long int napsk(long long int w,long long int idx)
{
	if(ans[idx][w]!=-1)
		return ans[idx][w];

	if(idx==N+1)
		return 0;
	if(w>W)
		return 0;
	long long int aa,bb;
	aa=0;
	if(w+arr[idx][0]<=W)
		aa=napsk(w+arr[idx][0],idx+1)+arr[idx][1];
	bb=napsk(w,idx+1);
	ans[idx][w]=max(aa,bb);
	return ans[idx][w];
}

int  main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int n,a,b,c,d,w;
	cin>>N>>W;

	for (long long int i = 1; i <=N ;++i)
	{
		cin>>arr[i][0]>>arr[i][1];
	}
	for (int i = 0; i < 105; ++i)
	{
		for (int ii = 0; ii < 100003; ++ii)
		{
			ans[i][ii]=-1;
		}
	}
	b=napsk(0,1);
	cout<<b<<endl;
	return 0;
}

Measured memory_bytes: 84224
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==1)cout<<0<<endl;
    else{
        long long ans=1;
        for(int i=n-1;i>=2;i--){
            ans+=i;
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
#define INF 99999999 
using namespace std;

int N,M,Q;
vector<ll> a,b,c,d;

// Q組の(a,b,c,d)に対して計算を行う　
ll calc(const vector<int> &A){
    ll res = 0;
    for (int i = 0; i < Q; i++)
    {
        if(A[b[i]] - A[a[i]] == c[i]) res += d[i];
    }
    return res;
}

void dfs(vector<int> &A, ll &res){
    if(A.size() == N+1){
        ll tmp = calc(A);
        res = max(res,tmp);
        return;
    }
    ll ba = A.back(); //Aの末尾
    for (int add = ba; add <= M; add++) // 末尾より大きいものに対して
    {
        A.push_back(add); // Aに追加
        dfs(A,res); 
        A.pop_back(); //　Aから取り出す
    }
    /*
    A = {1,"1"}, 
    (push) A = {1,1,"1"}, 
    return, 
    (pop) A = {1,1}, 
    A = {1,1,"2"}, ...
    */
}
int main()
{
    cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    for (int i = 0; i < Q; i++)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    ll res = 0;
    vector<int> A({1});
    dfs(A,res);
    cout << res << endl;;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n; string s , nuevo; int t = 0;
	cin >> n;
	string li[2];
	for(int i = 0 ; i < 2 ; i++ ){
		cin >> li[i];
		t += li[i].size();
	}
	int it1 = 0 , it2 = 0; 
	for(int i = 0 ; i < t ; i++){
		if(i % 2 == 0){
			nuevo += li[0][it1];
			it1++;
		}else if( i % 2 != 0){
			nuevo += li[1][it2];
			it2++;
		}
	}
	cout << nuevo;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
inf = 10**9
dp = [inf]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min((dp[i-1] +abs(h[i]-h[i-1])),(dp[i-2]+abs(h[i]-h[i-2])))
print(dp[n-1])

Measured memory_bytes: 13924
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<iomanip>
#include<stdio.h>
using namespace std;
 
int main(){
 
  int n, ans;
  cin >> n;
 
  for(int i=1; ; i++){
    ans=i*i;
    if(n<ans){
      ans=(i-1)*(i-1);
      cout << ans << endl;
      return 0;
    }
  }
 
  return 0;
}

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

using namespace std;

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

  string s, t;
  cin >> s >> t;
  int n = s.size(), m = t.size(), ans = n;
  for (int i = 0; i <= n - m; ++i) {
    int cur = 0;
    for (int j = 0; j < m; ++j) cur += s[i + j] != t[j];
    ans = min(ans, cur);
  }
  cout << ans;

  return 0;
}


Measured memory_bytes: 3652
import sys
readline = sys.stdin.readline

INF = 10**18

S = list(map(ord, readline().strip()))
T = list(map(ord, readline().strip()))
N = len(S)
M = len(T)

ans = INF

for i in range(N-M+1):
    res = 0
    for j in range(M):
        if S[i+j] != T[j]:
            res += 1
    
    ans = min(ans, res)

print(ans)

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

int main() {
    ll n , m ;
    cin >> n >> m ;
    ll i ;
    vector<ll> v(n) , dis ;
    for ( i = 0 ; i< n ;i++) cin >> v[i] ;

    sort(v.rbegin(),v.rend()) ;
    ll ans = accumulate(v.begin(),v.end(),0LL) ;
    for ( i = 0 ; i< n ;i++) {
        ll x = v[i] ;
        while(x){

                dis.pb(x-x/2) ;
                x/=2 ;
        }
    }

    sort(dis.rbegin(),dis.rend()) ;
    ll x= dis.size() ;
    for ( i = 0 ; i< x ; i++) {
        if (m==0) break ;
        m-- ;
        ans-=dis[i] ;

    }
    cout << ans << endl ;



}


Measured memory_bytes: 35684
import numpy as np
import math
import heapq

N = int(input())
A = list(input().split())
A = [[int(A[i]),i+1] for i in range(N)]
heapq.heapify(A)

ans = []
for i in range(N):
    x = heapq.heappop(A)
    ans.append(x[1])

print(*ans)


Measured memory_bytes: 34884
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

const int L = 8;

int n, m, c[9] = { 6, 7, 3, 6, 5, 4, 5, 5, 2 };
bool ava[9];
array<int, 10> dp[L][5001];

int main() {
	cin >> n >> m;
	inc(i, m) {
		int a;
		cin >> a;
		ava[9 - a] = true;
	}
	
	dp[0][0] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
	inc(I, n) {
	inc(j, n / 2) {
		int i = I % L;
		if(dp[i][j][9] == 0) { continue; }
		inc(k, 9) {
			if(! ava[k]) { continue; }
			auto x = dp[i][j];
			x[k]++;
			setmax(dp[(i + c[k]) % L][j + 1], x);
		}
		dp[i][j] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
	}
	}
	
	int D = -1;
	dec1(j, n / 2) {
		if(dp[n % L][j][9] == 1) {
			D = j;
			break;
		}
	}
	assert(D != -1);
	
	inc(i, 9) {
		inc(j, dp[n % L][D][i]) { cout << 9 - i; }
	}
	cout << endl;
	
	return 0;
}


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

int main() {
    ll n, m;
    cin >> n >> m;
    vector<int> a(m);
    rep(i, m) cin >> a[i];
    ll sum = accumulate(a.begin(), a.end(), 0);
    if(n < sum) {
        cout << -1 << endl;
    } else {
        cout << n - sum << endl;
    }
    return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>

typedef long long ll;

ll dp[5][8000];

int main() {

	int K,S;

	scanf("%d %d",&K,&S);

	dp[0][0] = 1ll;

	int i,j,k;

	for (i = 1; i <= 3; ++i) {
		for (j = 0; j <= S; ++j) {
			for (k = 0; k <= K; ++k) {
				if (j >= k) {
					dp[i][j] += dp[i - 1][j - k];
				}
			}
		}
	}

	printf("%lld\n",dp[3][S]);

	return 0;
}

Measured memory_bytes: 384
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static char[][] table;
	static int[] dx = { 0, 1, 1, 1, 0,-1,-1,-1};
	static int[] dy = { 1, 1, 0,-1,-1,-1, 0, 1};

	static int cnt(int turn, int x, int y) {
		int cnt = 0;
		for (int d=0; d<8; d++) {
			int tmp = 0;
			int nx = x, ny = y;
			while (true) {
				nx = nx + dx[d];
				ny = ny + dy[d];
				if (nx < 0 || ny < 0 || 8 <= nx || 8 <= ny) break;
				if ((turn == 0 && table[ny][nx] == 'x') || (turn == 1 && table[ny][nx] == 'o')) tmp++;
				if ((turn != 0 && table[ny][nx] == 'x') || (turn != 1 && table[ny][nx] == 'o')) {
					cnt += tmp;
					break;
				}
				if (table[ny][nx] == '.') break;
			}
		}
		return cnt;
	}

	static boolean _draw(int turn, int d, int x, int y) {
		if (x < 0 || y < 0 || 8 <= x || 8 <= y) return false;
		if (table[y][x] == '.') return false;
		if (turn == 0 && table[y][x] == 'o') return true;
		if (turn == 1 && table[y][x] == 'x') return true;
		boolean f = _draw(turn, d, x+dx[d], y+dy[d]);
		if (f) {
			table[y][x] = turn == 0 ? 'o' : 'x';
		}
		return f;
	}

	static void draw(int turn, int x, int y) {
		table[y][x] = turn == 0 ? 'o' : 'x';
		for (int d=0; d<8; d++) {
			_draw(turn, d, x+dx[d], y+dy[d]);
		}
	}

	static boolean turnA() {
		int max = -1, mi = -1, mj = -1;

		for (int i=0; i<8; i++) {
			for (int j=0; j<8; j++) {
				if (table[i][j] != '.') continue;
				int cnt = cnt(0, j, i);
				if (max < cnt) {
					max = cnt;
					mi = i;
					mj = j;
				}
			}
		}

		if (max > 0) draw(0, mj, mi);

		return max != -1;
	}

	static boolean turnB() {
		int max = -1, mi = -1, mj = -1;

		for (int i=7; i>=0; i--) {
			for (int j=7; j>=0; j--) {
				if (table[i][j] != '.') continue;
				int cnt = cnt(1, j, i);
				if (max < cnt) {
					max = cnt;
					mi = i;
					mj = j;
				}
			}
		}

		if (max > 0) draw(1, mj, mi);

		return max != -1;
	}

	static void solve() {
		table = new char[8][8];
		for (int i=0; i<8; i++) {
			table[i] = in.next().toCharArray();
		}

		int turn = 0;
		boolean f = true;
		int p = 0;
		while (f && p < 100) {
			if (turn == 0) f = turnA();
			else f = turnB();
			turn = (turn + 1)%2;
			p++;
		}

		for (int i=0; i<8; i++) {
			for (int j=0; j<8; j++) {
				out.print(table[i][j]);
			}
			out.println();
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26392
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int K;
    cin >> K;
    int x=K/2;
    int y=(K+1)/2;
    cout << x*y << endl;



}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
image_1 = []
n.times { image_1 << gets.chomp.split("") }
image_2 = []
m.times { image_2 << gets.chomp.split("") }
new_images = []

(0..n - m).each do |w|
  (0..n - m).each do |h|
    new_image = []
    image_1[w, m].each do |row|
      new_image << row[h, m]
    end
    new_images << new_image
  end
end

puts new_images.include?(image_2) ? "Yes" : "No"


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

int main()
{
    long long a;
    string b;
    cin>>a>>b;
    int s[3];
    s[0]=b[0]-48;
    s[1]=b[2]-48;
    s[2]=b[3]-48;
    long long z;
    z=a*(s[0]*100+s[1]*10+s[2])/100;
    cout<<z;
    return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define POWT(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;


int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	int ans = k;
	REP(i, n-1) {
		ans *= (k - 1);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(2*N);
    for (int i = 0; i < 2*N; i++)
        cin >> A[i];
    sort(A.rbegin(), A.rend());
    int ans = 0;
    for (int i = 0; i < 2*N; i+=2) {
        ans += A[i+1];
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'

constexpr int INF = 2e18;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 3;

// #define MULTIPLE_TEST_CASES
void solve() {
  char n;
  cin >> n;

  if (islower(n)) {
    cout << 'a' << endl;
  } else {
    cout << 'A' << endl;
  }
}

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;

#ifdef MULTIPLE_TEST_CASES
  cin >> t;
#endif
  while (t--)
    solve();
}

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

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

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<int>());
    
    bool flg = s < t;

    if(flg) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        //値を取得
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int answer = (int)Math.pow(N,3); //順列
      
        //出力
        System.out.println(answer);
    }
}

Measured memory_bytes: 35692
import java.io.*;
import java.util.*;

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

		int a = in.nextInt();
		int b = in.nextInt();

		if (a > 9 || b > 9)
			System.out.println(-1);
		else
			System.out.println(a*b);
	}
}



Measured memory_bytes: 23124
import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.*
import kotlin.math.*
fun main(){
    var fs = CodeForces.FastReader()
    var n = fs.nextInt()
    var m = fs.nextInt()
    var k = fs.nextLong()
    var a = fs.readLongArray(n)
    var b = fs.readLongArray(m)
    var sumsA = LongArray(n+1)
    var sumsB = LongArray(m+1)
    for(i in 1 until sumsA.size) sumsA[i] += sumsA[i-1] + a[i-1]
    for(i in 1 until sumsB.size) sumsB[i] += sumsB[i-1] + b[i-1]
    var best = 0
    for (i in 0 until sumsA.size) {
        if(k-sumsA[i] < 0) continue
        var sumj:Long = k-sumsA[i]
        var L = 0; var P = sumsB.size -1
        var ans = i
        while (L <= P) {
            var mid = L + (P-L)/2
            if(sumsB[mid] > sumj) P = mid-1
            else L = mid +1
        }
        ans += L + (P-L)/2 -1
        best = max(best,ans)
    }
    println(best)
}

class CodeForces {
    internal class FastReader {
        private var br: BufferedReader = BufferedReader(InputStreamReader(System.`in`))
        private var st: StringTokenizer? = null

        operator fun next(): String {
            while (st == null || !st!!.hasMoreElements()) {
                try {
                    st = StringTokenizer(br.readLine())
                } catch (e: IOException) {
                    e.printStackTrace()
                }

            }
            return st!!.nextToken()
        }

        fun nextInt(): Int {
            return Integer.parseInt(next())
        }

        fun nextLong(): Long {
            return java.lang.Long.parseLong(next())
        }

        fun nextDouble(): Double {
            return java.lang.Double.parseDouble(next())
        }

        fun nextLine(): String {
            var str = ""
            try {
                str = br.readLine()
            } catch (e: IOException) {
                e.printStackTrace()
            }
            return str
        }

        fun readIntArray(n: Int): IntArray {
            val a = IntArray(n)
            for (i in 0 until n) a[i] = nextInt()
            return a
        }
        fun readLongArray(n: Int): LongArray {
            val a = LongArray(n)
            for (i in 0 until n) a[i] = nextLong()
            return a
        }

        fun readDoubleArray(n: Int): DoubleArray {
            val a = DoubleArray(n)
            for (i in 0 until n) a[i] = nextDouble()
            return a
        }
    }
}


Measured memory_bytes: 65416
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll A;
string S = "";

int main() {
	scanf("%lld", &A);
	cin >> S;
	if(A >= 3200) {
		cout << S << endl;
	}
	else {
		cout << "red\n";
	}
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll n, K;
    cin >> n >> K;

    string S;
    cin >> S;

    ll res = 0;

    ll baseHappy = 0;
    rep(i, n - 1) {
        if (S[i] == S[i+1]) baseHappy++;
    }

    put(min(baseHappy + 2 * K, n - 1));
}
signed main(){ Main();return 0;}

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

int main()
{
  int K, N;
  cin >> K >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  int length_max = (K-A.at(N-1)) + A.at(0);
  for (int i = 0; i < N-1; i++)
  {
    int tmp = A.at(i+1) - A.at(i);
    if (length_max < tmp) length_max = tmp;
  }
  cout << K - length_max << endl;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

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

	int cnt[5];
	for (int i = 0; i < 5; i++)
	{
		cnt[i] = 0;
	}

	for (int i = 0; i < 3; i++)
	{
		cnt[a[i]]++;
		cnt[b[i]]++;
	}

	int judgenum=1;
	for (int i = 1; i < 5; i++)
	{
		judgenum *= cnt[i];
	}

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

Measured memory_bytes: 256
import math

n = int(input())

kirisute = math.floor(n/1.08)
kiriage = math.ceil(n/1.08)

#print(kiriage)
#print(kirisute)

if math.floor(kiriage*1.08) == n:
    print(kiriage)
elif math.floor(kirisute*1.08) == n:
    print(kirisute)
else:
    print(":(")



Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

bool comp(pair<int,int> p, pair<int,int> q) {
    if (p.second < q.second)
        return true;
    else if (p.second > q.second)
        return false;
    else if (p.first < q.first)
        return true;
    return false;
}

int main() {
    int n, m;   cin >> n >> m;
    pair<int,int> *island = new pair<int,int>[m];
    for (int i = 0; i < m; i++)
        cin >> island[i].first >> island[i].second;

    sort(island, island+m, comp);

    int ans = 0;
    for (int i = 0; i < m;) {
        int a = island[i].second;
        int j = i;
        while (j < m && island[j].first < a)
            j++;
        ans++;
        i = j;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}


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

  ll N,M;
  cin >> N >> M;
  vector<pair<ll,ll> > E;
  map<ll, vector<ll> > G;
  rep(i,M){
    ll a,b; cin >> a >> b;
    a--,b--;
    E.pb(mp(a,b));
    G[a].pb(b);
    G[b].pb(a);
  }

  ll ans = 0;
  rep(i,M){
    //1番目取り除く
    ll a = E[i].first, b = E[i].second;
    G[a].erase(remove(G[a].begin(), G[a].end(),b),G[a].end());
    G[b].erase(remove(G[b].begin(), G[b].end(),a),G[b].end());

    ll used[51]={0};
    stack<int> sta;
    sta.push(1);
    while(!sta.empty()){
      ll vt = sta.top();
      sta.pop();
      if(used[vt]==1)continue;
      used[vt]=1;
      rep(i,G[vt].size())sta.push(G[vt][i]);
    }


    rep(i,N){
      if(used[i]!=1){
	ans++;
	break;
      }      
    }
    
    G[a].pb(b);G[b].pb(a);
  }
  
  cout << ans << endl;

  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
inp = [int(x) for x in input().split()]
n = inp[0]
k = inp[1]

num = [x for x in range(0, n+1, k)]
ans = (len(num)-1) ** 3

if k % 2 == 0:
    c = 0
    for i in range(1, n+1):
        if i % k == k / 2:
             c += 1
    ans += c ** 3
    

print(ans)

Measured memory_bytes: 11032
import sys,heapq
input=sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AB=[list(map(int,input().strip().split())) for _ in range(N)]
AB.sort()
n=0
sumB=0
q=[]
for m in range(1,M+1):
    while n<N and AB[n][0]<=m:
        heapq.heappush(q,-AB[n][1])
        n+=1
    if len(q)!=0:
        sumB+=heapq.heappop(q)

print(-sumB)

Measured memory_bytes: 31584
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 32);
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for (ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i, r, n) for (ll i = (ll)(n - 1); i >= r; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll>> vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
template <class T>
T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T>
T &chmax(T &a, const T &b) { return a = max(a, b); }

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
    cin >> n;
    ans = INF;
    REP(i, sqrt(n) + 1)
    {
        if (n % (i + 1) == 0)
        {
            s = to_string(n / (i + 1));
            m = s.size();
            chmin(ans, m);
        }
    }
    cout << ans << endl;
}

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

using namespace std;

typedef pair<int, int> Pii;

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

  long long int N, A, B;
  cin >> N >> A >> B;
  vector<long long int> X;
  for (int i = 0; i < N; i++) {
    long long int buf;
    cin >> buf;
    X.push_back(buf);
  }

  long long int fatigue = 0;
  for(int i = 0; i < N-1; i++) {
    if ((X[i+1] - X[i]) * A < B) fatigue += (X[i+1] - X[i]) * A;
    else fatigue += B;
  }

  cout << fatigue << endl;
  return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;


int main()
{
	string s;
	int a=0, b=0;
	cin >> s;
	for(int i=0; i<3; i++)
	{
		if(s[i] == 'R')
		{
			a++;
			b=a;
		}
		else if(s[i] != 'R')
		{
			a=0;
		}
	}
	cout << b;
}



Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <queue>
#include <sstream>

using namespace std;

typedef long long ll;

const ll INF=1e9+7;

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

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

ll dp[110][100100]={0};
ll weight[110],value[110];
ll N,W;

int main(){
    cin>>N>>W;
    rep(i,N)cin>>weight[i]>>value[i];

    rep(i,N){
        rep(j,W+1){
            if(j-weight[i]>=0){
                chmax(dp[i+1][j],dp[i][j-weight[i]]+value[i]);
            }
            chmax(dp[i+1][j],dp[i][j]);
        }
    }

    cout<<dp[N][W]<<endl;
    return 0;
}
//自力を目指したがhttps://qiita.com/drken/items/dc53c683d6de8aeacf5a#d-問題---knapsack-1を写経

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;





int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	a[i]=(s[i]=='R');
    }
    int z = std::count(a.begin(), a.end(), 0);
    
    vector<int> g = a;
    sort(g.rbegin(), g.rend());

    
    int diffs=0;
    for (int i=0; i<n; i++) {
	diffs += (a[i]!=g[i]);
    }

    assert(diffs%2==0);
    int ans1 = diffs/2;
    int ans2 = min(z, n-z);
    //assert(ans1<=ans2);

    cout<<min(ans1,ans2)<<endl;    
    
    return 0;
}


Measured memory_bytes: 5088
#include <iostream>
using namespace std;
int main(){
    int W,H;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0){
            break;
        }
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3088
#coding:utf-8
import sys, itertools
N=input()

P={}
primes=[]
def is_prime(x):
    if x==1:return False
    if x==2:return True        
    if x%2==0:return False
    if x==3:return True
    i=3
    while i*i<=x:
        if x%i==0:return False
        i+=2
    return True

def is_ok(seq):
    for s in itertools.combinations(seq,5):
        if P[sum(s)]: return False
    return True


for i in range(1, 55556*6):
    P[i] = is_prime(i)
primes=[x for x,f in P.iteritems() if f and x<=55555]

cand=[]
for p in primes:
    if p%10==1:cand.append(p)
ans=cand[:N]
print(" ".join(map(str,ans)))




Measured memory_bytes: 31800
#include<cstdio>
#include<math.h>

using namespace std;

const int MAX_N = 200000;

int N;
long long d;
long long X[MAX_N], Y[MAX_N];

void solve();

int main(){

    scanf("%d %ld", &N, &d);
    for(int i=0;i<N; i++){
        scanf("%ld %ld", &X[i], &Y[i]);
    }

    solve();

    return 0;
}

void solve(){

    int ans=0;
    for(int i =0;i<N; i++){
        if(X[i]*X[i] + Y[i]*Y[i]<= d*d) {
            ans++;
        }
    }

    printf("%d\n", ans);
}

Measured memory_bytes: 4852
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int sX = int.Parse(s[0]);
            int sY = int.Parse(s[1]);
            int eX = int.Parse(s[2]);
            int eY = int.Parse(s[3]);

            for (int i = sX; i < eX; i++)
            {
                Console.Write("R");
            }
            for (int i = sY; i < eY; i++)
            {
                Console.Write("U");
            }
            for (int i = sX; i < eX; i++)
            {
                Console.Write("L");
            }
            for (int i = sY; i < eY; i++)
            {
                Console.Write("D");
            }

            Console.Write("D");
            Console.Write("R");
            for (int i = sX; i < eX; i++)
            {
                Console.Write("R");
            }
            for (int i = sY; i < eY; i++)
            {
                Console.Write("U");
            }
            Console.Write("U");
            Console.Write("L");

            Console.Write("U");
            Console.Write("L");
            for (int i = sX; i < eX; i++)
            {
                Console.Write("L");
            }
            for (int i = sY; i < eY; i++)
            {
                Console.Write("D");
            }
            Console.Write("D");
            Console.Write("R");

            Console.WriteLine();
        }
    }
}


Measured memory_bytes: 13140
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n = int(input())
    H = list(map(int, input().split()))
    D = {v : i for i, v in enumerate(sorted(H))}
    for i in range(n):
        H[i] = D[H[i]]
    A = list(map(int, input().split()))

    tree = SegmentTree([0] * (n + 1), max, 0)
    res = 0
    for h, a in zip(H, A):
        score = tree.sum(0, h) + a
        tree.update(h, score)

    print(tree.sum(0, n))
resolve()

Measured memory_bytes: 125972
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N, K;
	cin >> N >> K;
	int nax = (N-1)*(N-2)/2;
	if(!(K <= nax)){
		cout << -1 << endl;
		return 0;
	}
	int now = nax;
	vector<P> ans;
	bool end = false;
	for(int i = 2; i <= N; ++i)ans.push_back(make_pair(1, i));
	for(int i = 2; i <= N && !end; ++i){
		for(int j = i + 1; j <= N && !end; ++j){
			if(now == K){end = true; break;}
			ans.push_back(make_pair(i,j));
			--now;
		}
	}
	cout << ans.size() << endl;
	for(auto x:ans)cout << x.first << ' ' << x.second << endl;
	return 0;
}


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

using namespace std;

#define INF 0x3f3f3f3f

int N,M;

int cost[1001]; //custo de cada chave
int key_treasure[1001]; // baus que cada chave abre
int memo[1001][9000];
int total; // bits de baus

int dp(int key, int treasures){

    if (key == M){
        if(treasures == total) return 0;
        else return INF;
    }
    
    if(memo[key][treasures] != -1) return memo[key][treasures];

    int a = dp(key+1, treasures | key_treasure[key]) + cost[key];
    
    int b = dp(key+1, treasures);
    
    int ans = min(a,b);
    memo[key][treasures] = ans;
    
    return ans;
}


int main(){

    cin >> N >> M;
    memset(memo, -1, sizeof(memo));
    
    for(int i=0; i<N; i++){
        total |= 1 << i;
    }
    
    for(int i=0; i< M; i++){
        int key_cost, q;
        
        cin >> key_cost >> q;
        cost[i] = key_cost;

        int treasure;
        for(int x=0; x < q; x++){
            cin >> treasure;
            key_treasure[i] |= 1 << (treasure - 1);
        }
    
    }

    int ans = dp(0,0);
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;

}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define repll(i,n) for(ll i = 0; i < n; i++)
#define REPll(i,n) for(ll i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n") 
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  int cnt = 0;
  rep(i,h)rep(j,w){
    if(s[i][j] == '#') cnt++;
  }
  vii seen(h,vi(w, -1));
  queue<P> que;
  que.push(make_pair(0,0));
  seen[0][0] = 0;
  while(!que.empty()){
    P now = que.front(); que.pop();
    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(s[ny][nx] == '#' || seen[ny][nx] != -1) continue;
      que.push(make_pair(ny, nx));
      seen[ny][nx] = seen[now.first][now.second] + 1;
    } 
  }
  if(seen[h-1][w-1] == -1){
    cout << -1 << endl;
    return 0;
  }
  int ans = h*w - seen[h-1][w-1] - cnt - 1;
  cout << ans << endl;

}

Measured memory_bytes: 256