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

using namespace std;

int n, d1, d2;
vector<pair<int, int> > v[2], a[2];

int main(){
	scanf("%d%d%d", &n, &d1, &d2);
	int x = 0, y;
	while(d1 / (1 << (2 * x)) % 4 == 0) x++;
	y = d1 / (1 << (2 * x)) % 4;
	x = 1 << x;
	for(int i = 0;i < n * 2;i++){
		for(int j = 0;j < n * 2;j++){
			int ii = i / x, jj = j / x;
			if(y == 1){
				v[(ii + jj) & 1].push_back({i, j});
			}else if(y == 2){
				v[ii & 1].push_back({i, j});
			}else{
				v[0].push_back({i, j});
			}
		}
	}
	if(v[0].size() < v[1].size()) swap(v[0], v[1]);
	x = 0;
	while(d2 / (1 << (2 * x)) % 4 == 0) x++;
	y = d2 / (1 << (2 * x)) % 4;
	x = 1 << x;
	for(int k = 0;k < v[0].size();k++){
		int i = v[0][k].first, j = v[0][k].second;
		int ii = i / x, jj = j / x;
		if(y == 1){
			a[(ii + jj) & 1].push_back({i, j});
		}else if(y == 2){
			a[ii & 1].push_back({i, j});
		}else{
			a[0].push_back({i, j});
		}
	}
	if(a[0].size() < a[1].size()) swap(a[0], a[1]);
	for(int i = 1;i <= n * n;i++) printf("%d %d\n", a[0].back().first, a[0].back().second), a[0].pop_back();
}


Measured memory_bytes: 9228
#include<iostream>
#include<vector>
using namespace std;
const long long int mod = 1e9 + 7;

long long int dfs(int K, const vector<vector<int>>&graph, int now, int from) {
	int can_use_color_num;
	if (from == -1) {
		can_use_color_num = K - 1;
	}
	else {
		can_use_color_num = K - 2;
	}
	if (K < graph[now].size()) {
		return 0;
	}
	else {
		long long int case_num = 1;
		for (auto e : graph[now]) {
			if (e == from)continue;
			
			case_num *= can_use_color_num;
			can_use_color_num--;
			case_num %= mod;

		}
		for (auto e : graph[now]) {
			if (e == from)continue;
			
			case_num *= dfs(K, graph, e, now);
			case_num %= mod;	
		}
		return case_num;
	}
}

int main() {
	int N, K; cin >> N >> K;
	vector<vector<int>>graph(N);
	for (int i = 0; i < N - 1; ++i) {
		int a, b; cin >> a >> b; a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	long long int answer = K * dfs(K, graph, 0, -1);
	answer %= mod;
	cout << answer << endl;
	return 0;
}


Measured memory_bytes: 11520
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>

typedef long long ll;

const double EPS = 1e-10;
const double PI  = acos(-1);
const ll     INF = 1 << 30;

int main(int argc, char* argv[])
{
  ll N, C, K;
  ll tmp = 0;
  std::vector< ll> vi;
  std::cin >> N >> C >> K;
  
  for (ll i = 0; i < N; i++) {
    std::cin >> tmp;
    vi.push_back(tmp);
  }

  std::sort(vi.begin(), vi.end());
  
  ll human_count      = INF;
  ll first_human_time = INF * -1;
  ll bus_count        = 0;
  std::vector< ll >::iterator it = vi.begin();
  for (it = vi.begin(); it != vi.end(); it++) {
    if (human_count < C && *it <= first_human_time+K) {
      human_count++;
      //std::cout << *it << " " << human_count << " " << first_human_time << " " << bus_count << std::endl;
    } else {
      human_count = 1;
      first_human_time = *it;
      bus_count++;
      //std::cout << *it << " " << human_count << " " << first_human_time << " " << bus_count << "*" << std::endl;
    }
  }

  std::cout << bus_count << std::endl;
  
  return 0;
}


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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
template <class V> class BIT {
public:
	vector <V> bit;
	int M;
	BIT( int M ) :
		bit( vector <int>( M + 1, 0 )), M( M ) {
	}
	V sum( int e ) {
		if(e < 0) return 0;
		V s = 0;
		e++;
		while(e)
			s += bit[ e - 1 ], e -= e & -e;
		return s;
	}
	void add( int e, V v ) {
		e++;
		while(e <= M)
			bit[ e - 1 ] += v, e += e & -e;
	}
};

int main( void ){
	// initialize();
	int N;
	cin >> N;
	vector <BIT<int>> vec( 26, BIT<int>( N ));
	string str; cin >> str;
	rep( i, 0, N ){
		vec[ ( int )( str[ i ] - 'a' ) ].add( i, 1 );
	}
	int Q; cin >> Q;
	rep( i, 0, Q ){
		int a;
		cin >> a;
		if (a == 1){
			int b;
			char c; cin >> b >> c;
			b--;
			vec[ ( int )(( char )str[ b ] - 'a' ) ].add( b, -1 );
			str[ b ] = c;
			vec[ ( int )( c - 'a' ) ].add( b, 1 );

		}
		else {
			int b, c; cin >> b >> c;
			b--; c--;
			int ans = 0;
			rep( i, 0, 26 ){
				if (vec[ i ].sum( c ) - vec[ i ].sum( b - 1 ) > 0)
					ans++;
			}
			printf("%d\n", ans);
		}
	}


}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
	cin.tie( 0 );
	ios::sync_with_stdio( false );
}


Measured memory_bytes: 52992
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace SolutionCS
{
    class Program
    {
        class Node
        {
            public Node(int connect, int dist)
            {
                connectTo = connect;
                distance = dist % 2;
            }

            public int connectTo;
            public int distance;
        }

        static void SetDist(int node, int distance, List<Node>[] nodeList, int[] result)
        {
            if (result[node] >= 0)
            {
                return;
            }

            result[node] = distance % 2;

            foreach(Node n in nodeList[node])
            {
                SetDist(n.connectTo, distance + n.distance, nodeList, result);
            }
        }


        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            List<Node>[] allNode = new List<Node>[N];
            for (int i = 0; i < N; i++)
            {
                allNode[i] = new List<Node>();
            }

            for (int i = 0; i < N - 1; i++)
            {
                string[] inStr = Console.ReadLine().Split(' ');

                int node0 = int.Parse(inStr[0]) - 1;
                int node1 = int.Parse(inStr[1]) - 1;
                int distance = int.Parse(inStr[2]);

                allNode[node0].Add(new Node(node1, distance));
                allNode[node1].Add(new Node(node0, distance));
            }

            int[] color = new int[N];
            for (int i = 0; i < N; i++)
            {
                color[i] = -1;
            }

            // 頭のノードから再起処理
            SetDist(0, 0, allNode, color);

            for (int i = 0; i < N; i++)
            {
                Console.WriteLine("{0}", color[i]);

            }
        }
    }
}


Measured memory_bytes: 36168
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索する過程で親を更新
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        if UnionFind.same_check(self,x,y):
            return
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
ans = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ans[a] -= 1
    ans[b] -= 1
    u.union(a,b)
#print(*ans)
for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*[u.size(i)+x for i,x in enumerate(ans)])

Measured memory_bytes: 113184
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in c:
    cbits = (1 << j-1) 
    abc[i][2] |= cbits

dp = [0 if i == 0 else float("inf") for i in range(2**N)]
for i in range(M):
  for j in range(2**N):
    if dp[j|abc[i][2]] > dp[j]+abc[i][0]:
      dp[j|abc[i][2]] = dp[j]+abc[i][0]
print(dp[-1] if dp[-1] != float("inf") else -1)

Measured memory_bytes: 3428
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int nx[100010];
vector<int> ans;

int main() {
	int N, M;
	cin >> N >> M;
	string S;
	cin >> S;
	int left=0, right=1;
	while(right<=N){
		if(S[right]=='0'){
			while(S[left]!='0' || left+M<right) ++left;
			if(left==right){
				cout << -1 << endl;
				return 0;
			}
			nx[right]=left;
		}
		++right;
	}
	int now=N;
	while(now>0){
		ans.emplace_back(now-nx[now]);
		now=nx[now];
	}
	reverse(ans.begin(), ans.end());
	cout << ans[0];
	for(int i=1; i<ans.size(); ++i) cout << ' ' << ans[i];
	cout << endl;
	return 0;
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

//===


const int INF = int(1e9 + 7);

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	vector<Vi> to(N);
	for (int i = 0; i < M; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		to[u].push_back(v);
	}
	int S, T;
	cin >> S >> T;
	--S; --T;

	int (*dist)[3] = new int[N][3];
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			dist[i][j] = INF;
		}
	}

	queue<Pii> q;
	q.emplace(S,0);
	dist[S][0] = 0;
	while (!q.empty()) {
		int v = q.front().first;
		int l = q.front().second;
		q.pop();
		for (const auto& u : to[v]) {
			int nl = (l + 1) % 3;
			if (dist[u][nl] != INF) continue;
			dist[u][nl] = dist[v][l] + 1;
			q.emplace(u, nl);
		}
	}

	int ans = dist[T][0];
	delete[] dist;

	if (ans == INF) ans = -1;
	else ans /= 3;
	cout << ans << endl;
}


Measured memory_bytes: 6912
#include <stdio.h>

int main(void) {

  double five,ten;


  while(scanf("%lf %lf",&five,&ten)!=EOF) {

    if(five<35.50 && ten<71.00) printf("AAA\n");

    else if(five<37.50 && ten<77.00) printf("AA\n");

    else if(five<40.00 && ten<83.00) printf("A\n");

    else if(five<43.00 && ten<89.00) printf("B\n");

    else if(five<50.00 && ten<105.00) printf("C\n");

    else if(five<55.00 && ten<116.00) printf("D\n");

    else if(five<70.00 && ten<148.00) printf("E\n");

    else printf("NA\n");

  }

  return 0;

}

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

int main()
{
  int A,B;
  int count=0;
  
  cin >> A >> B;
  
  for(int i=A;i<=B;i++)
  {
    if(i/10000==i%10 && i/1000%10==i%100/10)
      count += 1;
  }

  cout << count;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

int main() {
    int N ;cin >> N;
    vector<int> a(N),b(N);
    REP(i,N) cin >> a[i];
    REP(i,N) cin >> b[i];

    ll sum_a=0,sum_b=0;

    ll ad_a=0;
    REP(i,N){
        sum_a += a[i];
        sum_b += b[i];

        if(b[i] > a[i])ad_a += (b[i]-a[i]+1)/2;
    }

    ll gap_sum = sum_b-sum_a;
    if(gap_sum >= ad_a ){
        pl("Yes")
    } else {
        pl("No")
    }

    return 0;
}

Measured memory_bytes: 384
N = int(input())

div = []
for i in range(1, int(N ** 0.5) + 1):
    if N % i == 0:
        div.append([i, N // i])
#print(div)

l = len(div)
flist = []
for i in range(l):
    fx = max([len(str(div[i][0])), len(str(div[i][1]))])
    flist.append(fx)

print(min(flist))


Measured memory_bytes: 9424
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

static void print_uint(i32 n){if(n==0){putchar('0');return;}int s[20],len=0;while(n>0){s[len++]=n%10+'0';n/=10;}while(len>0){putchar(s[--len]);}}
static i32 read_uint(void){int c=getchar();while(!('0'<=c && c<='9')){c=getchar();}i32 res=0;while('0'<=c && c<='9'){res=10*res+c-'0';c=getchar();}return res;}

#define POS(i, j) ((i) * (m + 1) + (j))

i32 find (i32 a, i32 b, i32 c, i32 d, i32 *dp, i32 m) {
  return dp[POS(c, d)] - dp[POS(c, b - 1)] - dp[POS(a - 1, d)] + dp[POS(a - 1, b - 1)];
}

void run (void) {
  i32 n = read_uint();
  i32 m = read_uint();
  i32 q = read_uint();
  i32 *v = (i32 *) calloc ((n + 1) * (m + 1), sizeof (i32));
  i32 *ex = (i32 *) calloc ((n + 1) * (m + 1), sizeof (i32));
  i32 *ey = (i32 *) calloc ((n + 1) * (m + 1), sizeof (i32));
  for (i32 i = 1; i <= n; ++i) {
    for (i32 j = 1; j <= m; ++j) {
      v[POS(i, j)] = getchar() - '0';
      ex[POS(i, j)] = v[POS(i, j)] & v[POS(i - 1, j)];
      ey[POS(i, j)] = v[POS(i, j)] & v[POS(i, j - 1)];
    }
    getchar();
  }
  for (i32 i = 1; i <= n; ++i) {
    for (i32 j = 1; j <= m; ++j) {
      v[POS(i, j)] += v[POS(i - 1, j)] + v[POS(i, j - 1)] - v[POS(i - 1, j - 1)];
      ex[POS(i, j)] += ex[POS(i - 1, j)] + ex[POS(i, j - 1)] - ex[POS(i - 1, j - 1)];
      ey[POS(i, j)] += ey[POS(i - 1, j)] + ey[POS(i, j - 1)] - ey[POS(i - 1, j - 1)];
    }
  }
  while (q--) {
    i32 a = read_uint();
    i32 b = read_uint();
    i32 c = read_uint();
    i32 d = read_uint();
    i32 ans = find (a, b, c, d, v, m) - find (a + 1, b, c, d, ex, m) - find (a, b + 1, c, d, ey, m);
    print_uint (ans);
    putchar ('\n');
  }
}

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


Measured memory_bytes: 48640
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int maxP = 100, result = 0;
    for (int i=0; i<n; i++) {
        int p;
        cin >> p;
        result += p;
        maxP = max(maxP, p);
    }
    cout << result - maxP/2 << endl;
}

Measured memory_bytes: 3564
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var nDic = new Dictionary<string, int>();
            var num1 = int.Parse(Console.ReadLine());
            for (int i = 0; i < num1; i++)
            {
                var txt = Console.ReadLine();
                if (nDic.ContainsKey(txt))
                    nDic[txt] += 1;
                else
                    nDic.Add(txt, 1);
            }
            var mDic = new Dictionary<string, int>();
            var num2 = int.Parse(Console.ReadLine());
            for (int i = 0; i < num2; i++)
            {
                var txt = Console.ReadLine();
                if (mDic.ContainsKey(txt))
                    mDic[txt] += 1;
                else
                    mDic.Add(txt, 1);
            }
            var dic = nDic;
            foreach (var item in mDic)
            {
                if (dic.ContainsKey(item.Key))
                    dic[item.Key] -= item.Value;
            }
            var t = dic.OrderByDescending(x => x.Value).FirstOrDefault().Value;
            if (t >= 0)
                Console.WriteLine(dic.OrderByDescending(x => x.Value).FirstOrDefault().Value);
            else
                Console.WriteLine(0);
            Console.ReadLine();
        }
    }
}


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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    int sum = 0;
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    }
    int ans = 0;
    rep(i,n){
        if(a[i]*4*m>=sum) ans++;
    }
    cout << (ans>=m ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; //10^9

int main(void){
    int A, B, C;
    cin >> A >> B >> C;

    int a = A, b = B, c = C;
    int cnt = 0;

    while(a%2 == 0 and b%2 == 0 and c%2 == 0){
        int a_ = a, b_ = b, c_ = c;
        a = b_ / 2 + c_ / 2;
        b = a_ / 2 + c_ / 2;
        c = a_ / 2 + b_ / 2;
        cnt++;

        if (a == A and b == B and c == C){
            cout << -1 << endl;
            return 0;
        }
    }

    cout << cnt << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

void Aiko ( void ) ;
void Shori ( int ) ;

int jan[4] = {0};
int mem[5];

int main () {
	
	while (cin >> mem[0],mem[0]){
		int hoge = 0;
		for ( int i = 0; i < 4; i++ ) {
			jan[i] = 0;
		}
		
		jan[mem[0]]++;
		for ( int i = 1; i < 5; i++ ) {
			cin >> mem[i];
			jan[mem[i]]++;
		}
		for ( int i = 1; i < 4; i++ ) {
			if ( jan[i] )	{
				hoge++;
			}
		}
		if ( hoge != 2 ){
			Aiko ();
		} else {
			for ( int i = 1; i < 4; i++ ) {
				if ( !jan[i] ) {
					if ( i == 1 ) {
						Shori (2);
					} else if ( i == 2 ) {
						Shori (3);
					} else {
						Shori (1);
					}
					break;
				}
			}
		}
	}
	return 0;
}

void Aiko () {
	for ( int i = 0; i < 5; i++ ) {
		cout << "3" << endl;
	}
}

void Shori (int Win) {
	for ( int i = 0; i < 5; i++ ) {
		if ( mem[i] == Win ) {
			cout << "1" << endl;
		} else {
			cout << "2" << endl;
		}
	}
}

Measured memory_bytes: 1152
/*
author : seryu
title : contest
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;
int INF = 1001001001;

//Segment tree for RMQ
struct SegTreeRMQ
{
	int n = 1;
	vector<int> dat;

	SegTreeRMQ(int N)
	{
		init(N);
	}

	void init(int n_)
	{
		n = 1;
		while (n < n_)n *= 2;
		dat.resize(2 * n - 1);
		for (int i = 0; i < 2 * n - 1; i++)dat[i] = INT_MAX;
	}

	void update(int k, int a) 
	{
		k += n - 1;
		dat[k] = a;
		while (k > 0)
		{
			k = (k - 1) / 2;
			dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
		}
	}

	int query(int a, int b, int k, int l, int r) //[a,b):query,k:今のノードの番号,[l,r):今のノードに対応するsegment
	{
		if (r <= a || b <= l)return INT_MAX;
		if (a <= l && r <= b)return dat[k];
		else
		{
			int val_l = query(a, b, 2 * k + 1, l, (l + r) / 2);
			int val_r = query(a, b, 2 * k + 2, (l + r) / 2, r);
			return min(val_l, val_r);
		}
	}
};

void solve()
{
	int n, q;
	cin >> n >> q;
	SegTreeRMQ st(n);
	vector<int> ans;
	rep(i, q)
	{
		int com, x, y;
		cin >> com >> x >> y;
		if(com == 0)
		{
			st.update(x, y);
		}
		else
		{
			int a = st.query(x, y+1, 0, 0, st.n);
			ans.push_back(a);
		}
	}
	rep(i, sz(ans))cout << ans[i] << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}



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

//defines
#define openin freopen("input.txt","r",stdin)
#define openout freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define int long long
#define mod 1000000007
#define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
#define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
    os << "(" ;
    os << v.first << "," << v.second << ")" ;
    return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
    os << "[" ;
    int sz = v.size() ;
    for(int i = 0 ; i < sz ; ++i) {
        os << v[i] ;
        if(i!=sz-1)os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
    T last = *v.rbegin() ;
    os << "[" ;
    for(auto it : v) {
        os << it  ;
        if(it != last) os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
    for(auto it : v) {
        os << it.first << " : " << it.second << "\n" ;
    }
    return os ;
}
int power(int a , int b)
{
    int res = 1 ;
    while(b)
    {
        if(b%2) {
            res = (res * a) % mod ;
        }
        b/=2 ;
        a = (a*a) % mod ;
    }
    return res ;
}

//debug
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

int32_t main()
{
    fast;
    int n ; cin >> n ; 
    int ans = mod ; 
    rep(i,1,n) {
        int x ; cin >> x ; 
        int cnt = 0 ; 
        while(x % 2 == 0) {
            ++cnt , x /= 2 ; 
        }
        ans = min(ans,cnt) ; 
    }
    cout << ans << endl ;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1e+9;

int main()
{
	int n, m = 0;
	cin >> n >> m;
	map<int, int> num_list;
	for (int i = 0; i < n; i++)
	{
		int k = 0;
		cin >> k;
		for (int j = 0; j < k; j++)
		{
			int input = 0;
			cin >> input;
			num_list[input]++;
		}
	}
	int ans = 0;
	for(auto itr = num_list.begin(); itr != num_list.end(); ++itr)
	{
		if (itr->second == n)
		{
			ans++;
		}
	}


	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  int h,a; cin>>h>>a;
	rep(i,a){
		int b; cin>>b; h-=b;
	}
	if(h<=0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
import sys


while True:
    try:
        line = sys.stdin.readline().strip()
        if line == "":
            break
        nums = list(map(int, line.split()))
        N, A, B = nums[0:3]

        if N <= 0 or A > B or (A < B and N == 1):
            print(0)
            continue
        if(A == B or (A < B and N == 2)):
            print(1)
            continue
        print(B * (N - 2) - A * (N - 2) + 1)

    except:
        break

Measured memory_bytes: 3064
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string op[5]={"","+","-"};
int main()
{
	string p;
	cin>>p;
	int a,b,c,d;
	a=p[0]-'0';b=p[1]-'0';c=p[2]-'0';d=p[3]-'0';
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++){
				int ans=a;
				if(i==1) ans+=b;
				else ans-=b;
				if(j==1) ans+=c;
				else ans-=c;
				if(k==1) ans+=d;
				else ans-=d;
				if(ans==7){
					cout<<a<<op[i]<<b<<op[j]<<c<<op[k]<<d<<"=7"<<endl;
					goto kk;
				}
			}
	kk:;
	return 0;
}

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

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

int n;
ll fact[100005];
int pos1, pos2;

void extgcd(ll a, ll b, ll *x, ll *y) {
    ll xx, yy;
    if (b == 0) {
        *x = 1;
        *y = 0;
    } else {
        ll q = a / b;
        ll r = a % b;
        extgcd(b, r, &xx, &yy);
        *x = yy;
        *y = xx - q * yy;
    }
}

ll inv(ll a) {
    ll x, y;
    extgcd(a, MOD, &x, &y);
    return (x + MOD) % MOD;
}

int main() {
    scanf("%d", &n);
    vector<int> seen(n + 1, -1);
    for (int i = 0; i < n + 1; i ++) {
        int a;
        scanf("%d", &a);
        if (seen[a] >= 0) {
            pos1 = seen[a];
            pos2 = i;
        }
        seen[a] = i;
    }
    int N = n + 1;
    int len_I = pos1;
    int len_III = N - pos2 - 1;
    ll C1 = 1, C2 = 1;
    for (int k = 1; k <= N; k ++) {
        ll sum;
        int l_min = max(k - 1 - len_III, 0);
        int l_max = min(len_I, k - 1);
        if (l_min <= l_max) {
            sum = C1;
        } else {
            sum = 0;
        }
        C2 = C2 * (N - k + 1) % MOD * inv(k) % MOD;
        //printf("%lld %lld\n", C1, C2);
        sum = (C2 - sum + MOD) % MOD;
        printf("%lld\n", sum); 
        C1 = C1 * (len_I + len_III - k + 1) % MOD * inv(k) % MOD;
    }
}

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

int main()
{
    string str, cmd, rstr;
    int n, b, e;
    cin >> str >> n;
    for (int i = 0; i != n; ++i)
    {
        cin >> cmd >> b >> e;
        if (cmd == "replace")
        {
            cin >> rstr;
            for (int j = 0; j != e - b + 1; ++j)
            {
                str[b + j] = rstr[j];
            }
        }
        else if (cmd == "reverse")
        {
            reverse(str.begin()+b, str.begin()+e+1);
        }
        else
        {
            for (int i = b; i <= e; ++i)
            {
                cout << str[i];
            }
            cout << endl;
        }
    }
    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N=in();
	auto P=vecin(N);
	int Q=in();

	REP(i,Q){
		out(binary_search(ALL(P),in())?1:0);
	}
	return 0;
}


Measured memory_bytes: 3356
m,d = [int(i) for i in input().split()]
ans = 0
for i in range(d):
    j = i+1
    if (j%10)>=2 and (j-(j%10))/10>=2 and (j%10)*(j-(j%10))/10<=m:
        ans = ans + 1

print(ans)


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

#define endl "\n"
#define int long long
#define vec(x) vector<x>
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define matrix(x) vector<vector<x>>
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a, b, sizeof a)
#define setBits(n) __builtin_popcountll(n)
#define prec(n) fixed<<setprecision(n)
#define ff first
#define ss second
#define print(x) for(auto it:x) cout<<it<<" ";
#define dbg(x) cerr<<#x<<" :: "<<x<<endl;
#define dbg2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
const int INF = 1e9;
const int MOD = 1e9 + 7; 
const double pi = acos(-1);
int power(int a,int b,int m=MOD)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}
int dir[]={-1, 0, 1, 0, -1};
int dx[]={1,1,0,-1,-1,-1, 0, 1};
int dy[]={0,1,1, 1, 0,-1,-1,-1};

const int N = 3000;

void solve()
{
	int i,j,n;
	double ans=0.0;
	cin>>n;
	double p[n+1];
	for(i=1;i<=n;i++)
	cin>>p[i];
	double dp[n+1][n+1];// dp[i][j] probability of j heads with first i coins
	mem(dp,0.0);
	dp[0][0]=1.0;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=i;j++)
		{
			if(j==0)
			dp[i][j]=dp[i-1][j]*(1.0-p[i]);
			else
			dp[i][j]=dp[i-1][j]*(1.0-p[i])+dp[i-1][j-1]*p[i];
		}
	}
	for(i=(n+1)/2;i<=n;i++)
	ans+=dp[n][i];
	cout<<prec(10)<<ans<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--)
		solve();
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
#define M 100005
#define oo 1000000007
using namespace std;
int n, k;
int a[M];
int dp[M];
int main(){
    //freopen("data.inp", "r", stdin);
    //freopen("data.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i){
        scanf("%d", a + i);
        dp[i] = oo;
    }
    dp[1] = 0;
    for(int i = 2; i <= n; ++i)
        for(int j = i - 1; j >= max(1, i - k); --j)
            dp[i] = min(dp[i], dp[j] + abs(a[i] - a[j]));
    printf("%d", dp[n]);
    return 0;
}

Measured memory_bytes: 4644
n,m=map(int,input().split())
a=[]
for i in range(n):
    p=[int(j) for j in input().split()]
    for j in p[1:]:
        a.append(j)
ans=0
import collections
c=collections.Counter(a)
for i,j in c.most_common():
    if j==n:
        ans+=1
print(ans)



Measured memory_bytes: 3316
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int k = scan.nextInt();
    int[] h = new int[n];
    for (int i = 0; i < n; i++) {
      h[i] = scan.nextInt();
    }
    scan.close();

    System.out.println(minCost(h, k));
  }

  private static int minCost(int[] heights, int k) {
    if (heights.length == 0)
        return 0;

    int[] dp = new int[heights.length];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < heights.length; i++) {
        for (int j = i - 1; j >= Math.max(0, i - k); j--) {
            int currentCost = Math.abs(heights[i] - heights[j]);

            dp[i] = Math.min(dp[i], dp[j] + currentCost);
        }
    }

    return dp[dp.length - 1];
  }
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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

const ll INF=(ll)1e19;
//const int INF=(1<<30);

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

  vector<int> a(26,-1);
  vector<int> b(26,-1);
  REP(i,s.size()){
    int si = s[i]-'a';
    int ti = t[i]-'a';

    if(a[si] != -1 || b[ti] != -1){
      if(a[si] != ti || b[ti] != si){
        cout << "No" << endl;
        return 0;
      }
    }else{
      a[si] = ti;
      b[ti] = si;
    }
  }
  cout << "Yes" << endl;
}



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

const int kN = 1e5 + 5;

int n, a[kN], d[kN];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", a + i), d[i] = a[i];
	std::sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; ++i) a[i] = std::lower_bound(d + 1, d + n + 1, a[i]) - d;
	int ans1 = 0, ans2 = 0;
	for(int i = 1; i <= n; ++i) {
		ans1 += (a[i] % 2 == 1 && i % 2 == 0);
		ans2 += (a[i] % 2 == 0 && i % 2 == 1);
	}
	printf("%d", std::min(ans1, ans2));
	return 0;
}

Measured memory_bytes: 1024
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        a_vec: [i64;n],
    };
    for i in k..n {
        if a_vec[i] - a_vec[i - k] > 0 {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}


Measured memory_bytes: 5548
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

int n;

int main(){

	int m,order;

	scanf("%d",&n);
	int array[2*n];

	for(int i = 0; i < 2*n; i++){
		array[i] = i;
	}

	scanf("%d",&m);

	for(int i=0; i < m; i++){
		scanf("%d",&order);
		if(order == 0){
			int tmp_array[2*n];

			for(int i=0; i < 2*n; i++){
				tmp_array[i] = array[i];
			}

			int p = 0;
			for(int i=0; i < n; i++){
				array[p++] = tmp_array[i];
				array[p++] = tmp_array[n+i];
			}

		}else{
			int tmp_array[2*n];

			for(int i=0; i < 2*n; i++){
				tmp_array[i] = array[i];
			}

			int p = 0;
			for(int i=order; i <= 2*n-1; i++){
				array[p++] = tmp_array[i];
			}
			for(int i=0; i <= order-1; i++){
				array[p++] = tmp_array[i];
			}
		}
	}

	for(int i=0; i < 2*n; i++){
		printf("%d\n",array[i]+1);
	}

    return 0;
}

Measured memory_bytes: 2708
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;
import std.typecons : Tuple;

alias Edge = Tuple!(int, "to", long, "cost");

void main() {
    int n, m, s, t;

    scan(n, m);
    scan(s, t);
    s--, t--;

    auto adj = new Edge[][](n, 0);

    foreach (i ; 0 .. m) {
        int u, v, d;
        scan(u, v, d);
        adj[u-1] ~= Edge(v-1, d);
        adj[v-1] ~= Edge(u-1, d);
    }

    immutable inf = 10L^^17;

    auto dist = new long[](n);
    dist[] = inf;
    dist[s] = 0;

    alias Pair = Tuple!(int, "node", long, "dist");

    import std.container;

    auto h = new BinaryHeap!(Array!Pair, "a.dist > b.dist")();

    h.insert(Pair(s, 0));

    while(!h.empty) {
        auto u = h.front;
        h.removeFront;

        if (u.dist > dist[u.node]) continue;

        foreach (e ; adj[u.node]) {
            if (dist[e.to] > dist[u.node] + e.cost) {
                dist[e.to] = dist[u.node] + e.cost;
                h.insert(Pair(e.to, dist[e.to]));
            }
        }
    }

    debug {
        writeln("dist:", dist);
    }

    auto ord = new Pair[](n);

    foreach (i ; 0 .. n) {
        ord[i] = Pair(i, dist[i]);
    }

    ord.sort!"a.dist < b.dist"();

    immutable long mod = 10^^9 + 7;

    auto dp1 = new long[](n);
    auto dp2 = new long[](n);

    dp1[s] = 1;

    foreach (v ; ord) {
        foreach (e ; adj[v.node]) {
            if (dist[e.to] + e.cost == dist[v.node]) {
                dp1[v.node] += dp1[e.to];
                dp1[v.node] %= mod;
            }
        }
    }

    dp2[t] = 1;

    foreach_reverse (v ; ord) {
        foreach (e ; adj[v.node]) {
            if (dist[e.to] - e.cost == dist[v.node]) {
                dp2[v.node] += dp2[e.to];
                dp2[v.node] %= mod;
            }
        }
    }

    debug {
        writeln(dp1);
        writeln(dp2);
    }

    long ans = dp1[t] * dp1[t] % mod;

    foreach (i ; 0 .. n) {
        if (dist[i]*2 == dist[t]) {
            ans -= dp1[i] * dp1[i] % mod * dp2[i] % mod * dp2[i] % mod;
            if (ans < 0) ans += mod;
        }
        foreach (e ; adj[i]) {
            if (dist[i]*2 < dist[t] && dist[e.to]*2 > dist[t]
                && dist[i] + e.cost == dist[e.to]) {
                ans -= dp1[i] * dp1[i] % mod * dp2[e.to] % mod * dp2[e.to] % mod;
                if (ans < 0) ans += mod;
            }
        }
    }

    writeln(ans);

}




void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

using namespace std;


int main(){

    long long N, P; cin >> N >> P;

    vector <long long> cnt;
    long long num = P;
    for (long long i = 2; i * i <= P; i++){
        while(num % i == 0){
            cnt.push_back(i);
            num = num / i;
        }
    }
    if (num != 1) cnt.push_back(num);
    cnt.push_back(0);

    long long count = 1, ans = 1;
    for (int i = 1; i < cnt.size(); i++){
        if (cnt[i] == cnt[i - 1]){
            count ++;
        }else{
            if (count >= N){
                long long T = count / N;
                for (long long j = 0; j < T; j++){
                    ans = ans * cnt[i - 1];
                }
            }
            count = 1;
        }
    }
    
    cout << ans << endl;

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> w(n), b(n+1);
    w[0] = (s[0] == '.' ? 1 : 0);
    b[n] = 0;
    b[n-1] = (s[n-1] == '#' ? 1 : 0);
    for (int i = 1; i < n; i++) {
        if (s[i] == '.') w[i] = w[i-1] + 1;
        else w[i] = w[i-1];
    }
    for (int i = n-2; i >= 0; i--) {
        if (s[i] == '#') b[i] = b[i+1] + 1;
        else b[i] = b[i+1];
    }
    int ans = n - b[0];
    for (int i = 0; i < n; i++) {
        int t = ((i+1) - w[i]) + ((n-1-i) - b[i+1]);
        ans = min(t, ans);
    }
    cout << ans << endl;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

using namespace std;
const int INF = 1e8;
int main(){
  int N,Ma,Mb;
  cin >> N >> Ma >> Mb;
  int a[N], b[N], c[N];
  rep(i,N){
    cin >> a[i] >> b[i] >> c[i];
  }
  // ret DPtable
  int dp[N+1][500][500];
  rep(i,N+1)rep(j,500)rep(k,500){
    dp[i][j][k] = INF;
  }
  dp[0][0][0] = 0;

  //make DP table
  rep(i,N)rep(j,500)rep(k,500){
    //choice
    if(dp[i][j][k] != INF){
      dp[i+1][j + a[i]][k + b[i]] = min(dp[i][j+a[i]][k+b[i]] , dp[i][j][k] + c[i]);
    }
    //not choice
    dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][k]);
  }


  int ans = INF;
  FOR(j,1,500)FOR(k,1,500){
    if(j % Ma == 0 && k % Mb == 0 && Mb * j == Ma * k )ans = min(ans,dp[N][j][k]);
  }

  if(ans == INF) cout << -1 << endl;
  else  cout << ans << endl;

  return 0;
}


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

int main(void){
  map<char, char> t;
  string sta, stb;
  string res = "Yes";
  cin >> sta >> stb;
  size_t len = sta.length();
  for(auto i = 0;i<len;i++){
    auto itl = t.find(sta.at(i));
    if(itl == t.end()){
      t[sta.at(i)] = stb.at(i);
    }else{
      if(itl->second != stb.at(i)){
        // for(auto itl : t){
        //   cout << itl.first << ":" << itl.second << " ";
        // }
        // cout << endl;
        res = "No";
        break;
      }
    }
  }
  t.clear();
  for(auto i = 0;i<len;i++){
    auto itl = t.find(stb.at(i));
    if(itl == t.end()){
      t[stb.at(i)] = sta.at(i);
    }else{
      if(itl->second != sta.at(i)){
        // for(auto itl : t){
        //   cout << itl.first << ":" << itl.second << " ";
        // }
        // cout << endl;
        res = "No";
        break;
      }
    }
  }

  cout << res << endl;
  return 0;
}

Measured memory_bytes: 776
//ABC84A
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	int m;
	cin >> m;
	cout << 48-m << endl;
	return 0;
}

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

//#define HOST
#ifdef HOST
#include"data_structure.h"
#include"common_algorithm.h"
#endif



ll inf = 1e9+7;


template <typename T>
vector<vector<T> > input_graph(T array_num, T edge_num)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this input_graph function can only be in type \"int\" or \"long long int\"!\n");
    vector<vector<T> > a(array_num, vector<T>());
    for(T i = 0; i < edge_num; i++)
    {
        T d1, d2;
        cin >> d1 >> d2;
        a.at(d1-1).emplace_back(d2-1);
        a.at(d2-1).emplace_back(d1-1);
    }

    return a;
}

template <typename T>
vector<T> input_vector(T array_num)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this input_vector function can only be in type \"int\" or \"long long int\"!\n");
    vector<T> a(array_num, 0);
    for(T i = 0; i < array_num; i++)
    {
        cin >> a.at(i);
    }

    return a;
}


int main() {
    int n, k, d;
    cin >> n;
    char c;
    ll num = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> c;
        if(c == 'B')
        {
            num--;
        }
        else
        {
            num++;
        }
    }

    if(num > 0)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
int main()
 
{
    int X, A, B;
		cin>>X>>A>>B;
 
		if (B-A<=0) {
        cout<<"delicious"<<endl;
		}
		else if (B-A<=X) {
			cout<<"safe"<<endl;;
		}
		else {
			cout<<"dangerous"<<endl;
		}
    
  return 0;
}

Measured memory_bytes: 256
MOD = (10**9) + 7
SIZE = 2000

N, M = gets.chop.split.map(&:to_i)
SS = gets.chop.split.map(&:to_i)
TS = gets.chop.split.map(&:to_i)

dp = Array.new(SIZE + 1, 0)
dp_sum = Array.new(SIZE + 1, 1)
dp[0] = 1

t_num_hash = [*(0..SIZE)].group_by { |i| TS[i] }

SS.each do |num|
  nums = t_num_hash[num]
  next if nums.nil?
  nums.reverse.each do |i|
    dp[i + 1] = (dp[i + 1] + dp_sum[i]) % MOD
  end
  1.upto(SIZE) do |i|
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD
  end
end

puts dp.inject(0, &:+) % MOD


Measured memory_bytes: 18300
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Integer> valueList = new ArrayList(); 
		List<Integer> costList = new ArrayList(); 
		
		for(int i = 0; i < n; i++) {
			int value = sc.nextInt();
			valueList.add(value);
		}
		for(int i = 0; i < n; i++) {
			int cost = sc.nextInt();
			costList.add(cost);
		}
		
		int sum = 0;
		for(int i = 0; i < n; i++) {
			int value = valueList.get(i);
			int cost = costList.get(i);
			if(value > cost) {
				sum+= value - cost;
			}
		}
		
		
		System.out.println(sum);

		
		
	}	

}



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

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int D=1e9+7;
ll mi(ll x,int y)
{
	ll ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}

int n;
namespace Count1
{
ll ans;
void check(int k)
{
	if(k<8)return ;
	ans+=mi(10,k)-mi(10,k-1)-n/k+1;
}
ll main()
{
	int g=sqrt(n);
	rep(i,1,g)
	if(n%i==0)
	{
		check(i);
		if(n/i!=i)check(n/i);
	}
	return ans%D;
}
};

namespace Count2
{
ll f(int i,int n)
{
	ll ans=0;
	while(i<=n)
	{
		int j=n/(n/i);
		ans+=(ll)(n/i)*(j-i+1);
		i=j+1;
	}
	return ans%D;
}
ll main()
{
	return f(8,n-1)-f(9,n);
}
};

int main()
{
	//freopen("1.in","r",stdin);
	cin>>n;
	if(n<=8)
	{
		int l=1,cl=1,wl=10;
		int r=1,cr=1,wr=10;
		int s=0,ans=0;
		while(cl<n)
		{
			while(s<n)
			{
				s+=cr;
				++r;
				if(r==wr){wr*=10;++cr;}
			}
			if(s==n)++ans;
			s-=cl;
			++l;
			if(l==wl){wl*=10;++cl;}
		}
		ans+=wl-wl/10;
		cout<<ans<<endl;
		return 0;
	}
	int l=1,cl=1,wl=10;
	int r=1,cr=1,wr=10;
	int s=0,ans=0;
	while(cl<8)
	{
		while(s<n)
		{
			s+=cr;
			++r;
			if(r==wr){wr*=10;++cr;}
		}
		if(s==n)++ans;
		s-=cl;
		++l;
		if(l==wl){wl*=10;++cl;}
	}
	cout<< ((ans+Count1::main()+Count2::main())%D+D)%D <<endl;
}

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

//#define int long long
typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string s;
    cin >> s;
    int r = 0;
    for (int i=0;i<N;i++){
        if (s[i]=='R') r++;
    }
    int ans = 0;
    for (int i=0;i<r;i++){
        if (s[i]=='W') ans++;
    }
    cout << ans << "\n";
}

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

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

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

   ll N,H,W;
   cin>>N>>H>>W;
   vector<ll>A(N),B(N);
   for(int i=0;i<N;i++)cin>>A[i]>>B[i];
   ll ans = 0;
   for(int i=0;i<N;i++){
      if(A[i]>=H&&B[i]>=W)ans++;
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 256