akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

#define INF ((int)1e9)

typedef pair<int, int> Pii;
typedef pair<int, Pii> Piii; // cost, cnum, node

vector<Pii> G[100];
int memo[100][10];

int dijkstra(int src, int dst, int cnum) {
  
  fill(memo[0], memo[0]+1000, INF);
  
  priority_queue<Piii> pq;
  memo[src][cnum] = 0;
  pq.push(Piii(0, Pii(-cnum, src)));
  while(!pq.empty()) {
    const Piii get = pq.top(); pq.pop();
    int cost = get.first;
    int cn = -get.second.first;
    int now = get.second.second;
    
    for(int i=0; i<G[now].size(); i++) {
      int next = G[now][i].first;
      int add_c = G[now][i].second;
      if(memo[next][cn] > cost + add_c) {
	pq.push(Piii(cost+add_c, Pii(-cn, next)));
	memo[next][cn] = cost + add_c;
      }
      
      add_c /= 2;
      if(cn-1>=0 && memo[next][cn-1] > cost + add_c) {
	pq.push(Piii(cost+add_c, Pii(1-cn, next)));
	memo[next][cn-1] = cost + add_c;
      }
    }
  }
  
  return *min_element(memo[dst], memo[dst]+10);
}

int main() {
  int C, N, M, S, D;
  while(cin >> C >> N >> M >> S >> D && (N|M)) {
    for(int i=0; i<N; i++) {
      G[i].clear();
    }
    for(int i=0; i<M; i++) {
      int a, b, c; cin >> a >> b >> c; a--, b--;
      G[a].push_back(make_pair(b, c));
      G[b].push_back(make_pair(a, c));
    }
    
    S --, D --;
    cout << dijkstra(S, D, C) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1e5 + 43;

vector <int> v;
bool dp[SIZE];
int n, k, a;

    void input(){
        cin >> n >> k;
        for(int i = 0; i < n; i++){
            cin >> a;
            v.push_back(a);
        }
    }

int main(){

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

    input();

    for(int i = 0; i < SIZE; i++)
        if(dp[i] == false)
            for(auto it : v)
                if(i + it < SIZE)
                    dp[i + it] = true;

    if(dp[k] == true) cout << "First";
    else cout << "Second";
    return 0;
}

Measured memory_bytes: 384
while 1:
    try:
        n = input()
        x = 0
        if n < 50:
            for a in range(10):
                for b in range(10):
                    for c in range(10):
                        for d in range(10):
                            if a + b + c + d == n:
                                    x += 1
        print x
    except EOFError:
        break

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

int main() {
  
  int N, M; cin >> N >> M;
  
  vector<int> vecS(M); vector<int> vecC(M);
  
  for (int i = 0; i < M; i++) {
    int s, c; cin >> s >> c;
    vecS[i] = s; vecC[i] = c;
  }
  
  for (int i = 0; i < 1000; i++) {
    
    bool flag = true; string number = to_string(i);
    
    if (number.size() != N) continue;
    
    for (int i = 0; i < M; i++) {
      
      int digit = vecS[i] - 1;
      
      int tmp = stoi(number.substr(digit, 1));
      
      if (tmp != vecC[i]) flag = false;
      
    }
    
    if (flag) {
      cout << i << endl;
      return 0;
    }
    
  }
  
  cout << -1 << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define per(i,n) for(int i=(n)-1; i>=0; i--)
#define chmin(a,b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;
const int MOD = 1000000007;

int main(){
    int n,k; cin>>n>>k;
    string s;cin>>s;
    
    int m = 0;
    
    for(int i=0; i<n; i++){
        if(!i)m++;
        else{
            if(s[i]!=s[i-1])m++;
        }
    }
    
    cout << min(n-m+2*k, n-1) << endl;
    return 0;
}

Measured memory_bytes: 3740
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
  int a [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
int x , y ; 
cin >> x >> y ;
cout << ( a [ x ] == a [ y ] ? " Yes " : " No ") << endl ;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

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

  int b[n+2]={},c[n+2]={};
  for(int i=0;i<n;i++){
    if(s[i]=='.') c[i+1]++;
    else b[i+1]++;
  }

  for(int i=1;i<=n;i++){
    b[i]+=b[i-1];
  }
  for(int i=n-1;i>=0;i--){
    c[i]+=c[i+1];
  }

  int ans=n;
  for(int i=1;i<=n+1;i++){
    ans=min(ans,b[i-1]+c[i]);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 2180
N,K = map(int,input().split())

A = list(map(int,input().split()))

def check(x):
  k = 0
  for a in A:
    k += ((a-1) // x)
  return k <= K

ng,ok = 0, 10**9+1

while ok-ng > 1:
  x = (ok+ng)//2

  if check(x):
    ok = x
  else:
    ng = x

print(ok)

Measured memory_bytes: 104052
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
int n, k;
bool d[10];
si s;
bool ok(int a){
  while(a > 0){
    if(d[a%10]) return false;
    a /= 10;
  }
  return true;
}

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, k){
    int _d;
    cin >> _d;
    d[_d] = true;
  }
  while(true){
    if(ok(n)){
      cout << n << endl;
      return 0;
    }
    n++;
  }
  return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 1000001;

int gcd(int a, int b) {
  return b ? gcd(b, a%b) : a;
} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll x;
	cin >> x;


	cout << 1LL* (x / 500) * 1000 + (x%500 / 5) *5;

    return 0;
}

Measured memory_bytes: 256
import sys


def input():
    return sys.stdin.readline().strip()


def solve():
    def distribute(fm, to):
        count[fm] -= 1
        count[to] += 1
        ans.append(to)

    n, a, b, c = map(int, input().split())
    queries = [input() for _ in range(n)]

    count = {'A': a, 'B': b, 'C': c}
    ans = ['Yes']

    for i in range(n):
        x, y = queries[i]
        if count[x] == count[y] == 0:
            return 'No'
        elif count[x] == count[y] == 1:
            if i == n - 1:
                distribute(x, y)
            else:
                if x in queries[i + 1]:
                    distribute(y, x)
                else:
                    distribute(x, y)
        elif count[y] > count[x]:
            distribute(y, x)
        else:
            distribute(x, y)
    return '\n'.join(ans)


print(solve())


Measured memory_bytes: 17308
import java.util.Scanner;

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

        while (true) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if ((n | m) == 0)
                break;
            int[] taro = new int[n];
            int[] hanako = new int[m];
            int taro_sum = 0;
            int hanako_sum = 0;
            for (int i = 0; i < n; i++)
                taro_sum += (taro[i] = sc.nextInt());
            for (int i = 0; i < m; i++)
                hanako_sum += (hanako[i] = sc.nextInt());
            int diff = taro_sum - hanako_sum;
            if (diff % 2 != 0)
                System.out.println(-1);

            else {
                int min = 201;
                String ans = new String();
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (diff / 2 == (taro[i] - hanako[j])) {
                            if (min > taro[i] + hanako[j]) {
                                min = taro[i] + hanako[j];
                                ans = taro[i] + " " + hanako[j];
                            }
                        }

                    }
                }
                if (min == 201)
                    ans = "-1";
                System.out.println(ans);
            }
        }
    }
}

Measured memory_bytes: 12000
n,k=map(int, input().split())
l1=map(int,input().split())
l2=[0,1,2,3,4,5,6,7,8,9]
l3=set(l1)^set(l2)
m=str(n)
l4=map(int,set(m))
l4=set(l4)
def check(a,b):
    if (a|b)==a:
        return True
    else:
        return False
while check(l3,l4) is False:
    n=n+1
    m=str(n)
    l4=map(int,set(m))
    l4=set(l4)
print(n)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main() {
  INIT;
  VAR(int, p,q,r);

  OUT(min(p+q,min(q+r,r+p)))BR;
  
  return 0;
}


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

int main() {
  int N; cin >> N;
  if (N > 81) {
    cout << "No" << endl; exit(0);
  }
  for (int i=1; i <= 9; i++) {
    for (int k=1; k <= 9; k++) {
      if (N == i*k) {
        cout << "Yes" << endl;
        exit(0);
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main(){
	int n;
	char c;
	int x,now=0;
	cin>>n;
	rep(i,0,n){
		cin>>c>>x;
		if(c=='(') now+=x;
		else now-=x;
		if(now<0){
			now=-10000000000;
		}
	}
	o((now==0?"YES":"NO"));
}

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

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    ll cur_max = 0;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (cur_max < a) {
            cur_max = a;
        } else {
            ans += cur_max - a;
        }
    }
    cout << ans;
    return 0;
}


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

int main(){
    int64_t n, x, d;
    cin >> n >> x >> d;

    if(d == 0){
        if(x == 0) cout << 1 << endl;
        else cout << n+1 << endl;
        return 0;
    }
    if(x == 0){
        cout << n*(n-1)/2 + 1 << endl;
        return 0;
    }
    
    map<int64_t, vector<pair<int64_t, int64_t>>> mp;

    for(int64_t k=0;k<=n;++k){
        int64_t rem = k*x % d;
        int64_t offset = (k * x - rem) / d;

        //if(mp.count(rem) == 0) mp[rem] = {};
        mp[rem].emplace_back(offset + k*(k-1)/2, offset + n*(n-1)/2 - (n-k-1)*(n-k)/2);
        //cerr << k*x / d + k*(k-1)/2 << " " << k*x / d + n*(n-1)/2 - (n-k-1)*(n-k)/2 << endl;
    }

    int64_t ans = 0;
    for(auto p: mp){
        sort(p.second.begin(), p.second.end());
        int64_t right = INT64_MIN;
        for(auto r: p.second){
            if(r.first > right){
                ans += r.second - r.first + 1;
                right = r.second;
            }else if(r.second > right){
                ans += r.second - right;
                right = r.second;
            }
        }
    }

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

Measured memory_bytes: 22144
#include <iostream>
#include <cmath>
#include <string>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    long N;

    cin >> N;

    long m = 1000000000002;

    for (long i = 1; i <= sqrt(N); i++)
    {
        long low = 1, high = m;
        while (low < high)
        {
            long mid = (low + high) / 2;
            if (i * mid > N)
            {
                high = mid;
            }
            else if (i * mid < N)
            {
                low = mid + 1;
            }
            else
            {
                long mv = i + mid - 2;
                m = min(m, mv);
                break;
            }
        }
    }

    cout << m << endl;

    return 0;
}

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

using lint = int64_t;
#define bit(n) ((lint)1 << n);
const int INF = 1e9;
const lint LINF = 1e18;

const lint MOD = 1e9 + 7;
// const lint MOD = 998244353;

class IoSetup {
    public:
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
        cerr << fixed << setprecision(12);
    }
} iosetup;

template <lint mod>
class ModInt {
    lint val;
    public:
    ModInt(): val(0) {}
    ModInt(lint init_val):
        val((init_val % mod + mod) % mod) {}

    ModInt operator -() {return ModInt(-val);}
    bool operator !() {return val == 0;}
    ModInt& operator ++() {this->val = (this->val + 1) % mod; return *this;}
    ModInt operator ++(int) {ModInt temp = *this; this->val = (this->val + 1) % mod; return temp;}
    ModInt& operator --() {
        this->val = ((this->val - 1) % mod + mod) % mod; return *this;}
    ModInt operator --(int) {
        ModInt temp = *this; this->val = ((this->val - 1) % mod + mod) % mod; return temp;}
    
    ModInt& operator += (const ModInt that) {val = (val + that.val) % mod; return *this;}
    ModInt& operator -= (const ModInt that) {val = ((val - that.val) % mod + mod) % mod; return *this;}
    ModInt& operator *= (const ModInt that) {val = (val * that.val) % mod; return *this;}
    ModInt& operator /= (const ModInt that) {
        lint res = 1, n = that.val, p = mod - 2;
        while (p > 0) {
            if (p % 2 == 1) res = res * n % mod;
            n = n * n % mod; p /= 2;
        }
        val = val * res % mod; return *this;
    }

    bool operator == (const ModInt& that) {return val == that.val;}
    bool operator != (const ModInt& that) {return val != that.val;}
    ModInt operator + (const ModInt& that) {return ModInt(*this) += that;}
    ModInt operator - (const ModInt& that) {return ModInt(*this) -= that;}
    ModInt operator * (const ModInt& that) {return ModInt(*this) *= that;}
    ModInt operator / (const ModInt& that) {return ModInt(*this) /= that;}

    friend istream& operator >> (istream& is, ModInt& a) {
        lint val; cin >> val; a = ModInt(val); return is;}
    friend ostream& operator << (ostream& os, const ModInt& a) {
        return os << a.val;}
};
using mint = ModInt<MOD>;
// using mint = double;

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> s(m + 1), t(n + 1);
    for (int i = 1; i <= m; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    vector<mint> a(m + 1), b(n + 1);
    mint ans = 1;
    for (int i = 1; i <= m; i++) {
        mint ad = 0, w = 0;
        for (int j = 1; j <= n; j++) {
            if (s[i] != t[j]) {
                ad += b[j];
            } else if (s[i] == t[j]) {
                mint temp = b[j];
                b[j] += ad + 1;
                w += ad + 1;
                ad += temp;
            }
        }
        ans += w;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  scanf("%d",&n);
  vector<int> dp(3);
  for(int day=0;day<n;++day){
    vector<int> new_dp(3,0);
    vector<int> c(3);
    for(int i=0;i<3;++i){
    	scanf("%d",&c[i]);
    }
    for(int i=0;i<3;++i){
      for(int j=0;j<3;++j){
        if(i!=j){
          new_dp[j] = max(new_dp[j],dp[i]+c[j]);
        }
      }
    }
    dp = new_dp;
  }
  printf("%d\n",max({dp[0],dp[1],dp[2]}));
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;


int main() {
	ios::sync_with_stdio(false);
	cin >> N >> K;
	if (N == K) {
		cout << N + 1 << endl;
		return 0;
	}
	if (N < K) {
		cout << "-1\n";
		return 0;
	}
	for (long long int i = 2; i <= sqrt(N); i++) {
		long long int box = N;
		long long int bag = 0;
		while (box) {
			bag += box%i;
			box /= i;
		}
		if (bag == K) {
			cout << i << endl;
			return 0;
		}
	}
	for (long long int i = sqrt(N); i >= 1; i--) {
		if (i*i == N)continue;
		if ((N + i - K) % i == 0){
			long long int box = (N + i - K) / i;
			if (box >= sqrt(N)) {
				if (N%box + N / box == K) {
					cout << box << endl;
					return 0;
				}
			}
		}
	}
	cout << "-1\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int A, B, C, D, in;

	cin >> in;
	D = in % 10;
	C = (int)(in / 10) % 10;
	B = (int)(in / 100) % 10;
	A = (int)(in / 1000);
	int sum;
	char op[3];

	for (int i = 0; i < 8; i++)
	{
		sum = 0;
		if ((i & 4) >> 2 == 1)
		{
			sum = A + B;
			op[2] = '+';
		}
		else
		{
			sum = A - B;
			op[2] = '-';
		}

		if ((i & 2) >> 1 == 1)
		{
			sum += C;
			op[1] = '+';
		}
		else
		{
			sum -= C;
			op[1] = '-';
		}
		if ((i & 1) == 1)
		{
			sum += D;
			op[0] = '+';
		}
		else
		{
			sum -= D;
			op[0] = '-';
		}

		if (sum == 7)
		{
			cout << A << op[2] << B << op[1] << C << op[0] << D << "=7" << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  int N, M; cin >> N >> M;
  double A[N], sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i]; sum += A[i];
  }
  sort(A, A + N, greater<double>());

  double m = M;
  if (A[M - 1] >= sum / (4 * m)) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


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

using namespace std;

string s;

int n, m;

int dp[int(2e5)];

deque <int> d;

bool is (int pos) {
	return s[pos] == '0';
}

int main () { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	for (int i = 0 ; i <= n ; ++ i) {
		if (is (i)) {
			d.push_back(i);
		}
	}
	int cur = n;
	for (int i = n ; i >= 0 ;) {
		while (!d.empty() && i <= d.back())
			d.pop_back();
		while (!d.empty() && i - d.back() <= m) {
			dp[d.back()] = dp[i] + 1;
			cur = d.back();
			d.pop_back();
		}
		if (i <= cur) {
			break;
		}
		i = cur;
	}
	if (!dp[0]) cout << -1, exit(0);
	d.clear();
	for (int i = n ; i >= 0 ; -- i) {
		if (is (i)) {
			d.push_back(i);
		}
	}
	cur = 0;
	for (int i = 0 ; i < n ;) {
		while (!d.empty() && i >= d.back())
			d.pop_back();
		while (!d.empty() && d.back() - i <= m) {
			if (dp[i] == dp[d.back()] + 1) {
				cur = d.back();
				d.pop_back();
				break;
			}
			d.pop_back();
		}
		cout << cur - i << " ";
		i = cur;
	}
}


Measured memory_bytes: 1268
// https://atcoder.jp/contests/abc167/tasks/abc167_a

use proconio::input;

fn main() {
    input! {
      s: String, t: String,
    }
    println!(
        "{}",
        if s[..] == t[..t.len() - 1] {
            "Yes"
        } else {
            "No"
        }
    );
}


Measured memory_bytes: 2084
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 11000



vector<int> G[MAX];
int ans[MAX];
int used[MAX];

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	int a, b;
	int max_ = 0, sum = 0, now = 0;
	
	vector<pair<int,int>> vec;
	vector<int> c;
	queue<int> Q;
	
	cin>>N;
	
	c.resize(N+10);
	
	for(int i = 0; i < N-1; i++){
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	for(int j = 1; j <= N; j++){
		cin>>c[j];
		sum += c[j];
		max_ = max(max_, c[j]);
	}
	
	sort(c.begin(), c.end(), greater<int>());
	
	Q.push(1);
	
	while(!Q.empty())
	{
		int x = Q.front() ; Q.pop();
		if(used[x]) continue;
		used[x] = true;
		ans[x] = c[now++];
		
		for(int i = 0; i < G[x].size(); i++){
			if(used[G[x][i]] == true) continue;
			Q.push(G[x][i]);
		}
	}
	
	cout<<sum - max_<<endl;
	
	for(int i = 0; i < N; i++){
		if(i) cout<<" ";
		cout<<ans[i+1];
	}
	cout<<endl;
	
	return 0;
}

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

typedef struct {
	int D,P;
} kukan_t;

/* kouzyun ni sooto suru */
int cmp(const void *x,const void *y) {
	int a=((kukan_t*)x)->P;
	int b=((kukan_t*)y)->P;
	if(a<b)return 1;
	if(a>b)return -1;
	return 0;
}

int main(void) {
	int N,M;
	while(scanf("%d%d",&N,&M)==2 && (N!=0 || M!=0)) {
		static kukan_t kukan[10000];
		int i;
		int ret=0;
		for(i=0;i<N;i++) {
			if(scanf("%d%d",&kukan[i].D,&kukan[i].P)!=2)return 1;
		}
		qsort(kukan,N,sizeof(kukan[0]),cmp);
		for(i=0;i<N;i++) {
			if(M>=kukan[i].D) {
				M-=kukan[i].D;
			} else {
				ret+=kukan[i].P*(kukan[i].D-M);
				M=0;
			}
		}
		printf("%d\n",ret);
	}
	return 0;
}

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

int main()
{
	int n, ans = 0;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 0; i < n - 2; i++)
	{
		if ((p[i] < p[i + 1] && p[i + 1] <= p[i + 2]) || (p[i] >= p[i + 1] && p[i + 1] > p[i + 2]))
			ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
	int N;
	scanf("%d", &N);
	
	
	if(N%2==0)
	{
		printf("%d", N/2);
	}	
	if(N%2!=0)
	{
		printf("%d", N/2 + 1);
	}
	return 0;
}

Measured memory_bytes: 1728
[n, m] = [int(x) for x in raw_input().split()]
A = [[0] * m for x in range(n)]
B = [0] * m
counter = 0
while counter < n:
    A[counter] = [int(x) for x in raw_input().split()]
    counter += 1

counter = 0
while counter < m:
    B[counter] = int(raw_input())
    counter += 1

counter = 0
while counter < n:
    result = 0
    for j in range(m):
        result += A[counter][j] * B[j]
    print(result)
    counter += 1

Measured memory_bytes: 6520
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> z_algorithm(const string& s)
{
	vector<int> prefix(s.size());
	for (int i = 1, j = 0; i < s.size(); i++) {
		if (i + prefix[i - j] < j + prefix[j]) {
			prefix[i] = prefix[i - j];
		}
		else {
			int k = max(0, j + prefix[j] - i);
			while (i + k < s.size() && s[k] == s[i + k]) ++k;
			prefix[i] = k;
			j = i;
		}
	}
	prefix[0] = (int)s.size();
	return prefix;
}

int main()
{
	int N;
	string S;
	cin >> N >> S;

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		auto v = z_algorithm(S.substr(i));
		for (int j = 0; j < N - i; ++j) {
			if (v[j] <= j) {
				ans = max(ans, v[j]);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
/*

 ** Author : Sudipta Banik Trisha
 ** Problem: E - Knapsack 2

*/



#include<bits/stdc++.h>
#define ll long long int 
using namespace std;
const ll INF = 1e10;

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

	ll n,w,sum=0;
	cin >> n >> w;

	vector<ll> weight(n), value(n);

	for(ll i=0; i<n; i++){
		cin >> weight[i] >> value[i];
		sum = sum + value[i];
	}
	
	vector<ll>dp(sum+10 , INF);
	dp[0] = 0;

	for(ll i=0; i<n; i++){
	//	cout << "i = " << i << " ";
		for(ll v = sum - value[i]; v >= 0; v--){
			dp[v + value[i]] = min(dp[v]+weight[i] , dp[v+value[i]]);
		//	cout << v+value[i] << " = "<< dp[v+value[i]] << " ";
		}	
		
	}

	for(ll i=sum ; i>=0; i--){
		if(dp[i] <= w){
			cout << i << endl;
			break;
		}
	}

	return 0;
}


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

int main(){
  vector<int> data;
  int a,b,c;
  cin>>a>>b;
  for(int i=0;i<a;i++){
    cin>>c;
    data.push_back(c);
  }
  c=0;
  sort(data.begin(),data.end());
  a=data.size();
  for(int i=data.size()-1;i>a-b-1;i--){

    c+=data[i];
  }
  cout<<c<<endl;
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
count = 0
for i in range(2, n):
  if (p[i-2] < p[i-1] and p[i-1] < p[i]):
  	count += 1
  elif (p[i-2] > p[i-1] and p[i-1] > p[i]):
    count += 1
print (count)
         

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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) for(long i=0;i<(a);++i)
#define RREP(i,a) for(long i=(a);i>=0;--i)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) std::sort((a).begin(), (a).end())
#define UNIQUE(a) std::sort((a).begin(), a.end()), a.erase(std::unique((a).begin(), a.end()), a.end());
#define SUM(a) std::accumulate((a).begin(), (a).end(), 0);

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector<int>  VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;

typedef std::vector< VC > VC2;
typedef std::vector< VI > VI2;
typedef std::vector< VL > VL2;
typedef std::vector< VLL > VLL2;

typedef std::pair<int,int> PII;

std::string S;
int main() {
    std::cin >> S;
    long ans, len = S.length();
    ans = len;

    REP(i, len - 1) {
        if(S[i] != S[i+1]) {
            ans = std::min(ans, std::max(i+1, len - i - 1));
        }
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>

// ===============================================================

using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
using pii = pair<int, int>;
using psi = pair<string, int>;
using ld = long double;
using ull = unsigned long long;

// ===============================================================

ll gcd(ll a, ll b) //最大公約数
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}

ll lcm(ll a, ll b) //最小公倍数
{
	return a * b / gcd(a, b);
}

ll box(double a) //doubleの切り捨て
{
	ll b = a;
	return b;
}

ll fff(double a) //doubleの四捨五入
{
	ll b = a + 0.5;
	return b;
}

ll sum(ll n) { //整数sまでの合計
	if (n == 0) {
		return 0;
	}

	int s = sum(n - 1);
	return s + n;
}

bool prime(ll num)//素数判定、primeならtrue,違うならfalse
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	// 素数である
	return true;
}

// ===============================================================

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	ll ans = 0;
	if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
		cout << 0 << endl;
	}
	else {
		ans = a * b;
		ans = min(ans, a * c);
		ans = min(ans, b * c);
		cout << ans << endl;
	}
}

Measured memory_bytes: 3676
#include <iostream>

using namespace std;

int H, W;
char c[55][55];
bool used[55][55];
int dj[] = {1, 0, -1, 0}, di[] = {0, -1, 0, 1};

int dfs(int i, int j)
{
	used[i][j] = true;
	
	int ret = 1;
	for(int d = 0; d < 4; d++){
		int ni = i + di[d], nj = j + dj[d];
		if(ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
		if(c[ni][nj] == '.') continue;
		if(used[ni][nj]) continue;
		ret += dfs(ni, nj);
	}
	return ret;
}

int main(void)
{
	cin >> H >> W;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cin >> c[i][j];
		}
	}
	
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(c[i][j] == '.') continue;
			if(used[i][j]) continue;
			if(dfs(i, j) == 1){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 384
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        String s = scanner.next();
        String t = scanner.next();
        int ans = 0;
        for (int i = 0; i < 3; ++i) {
            if (s.charAt(i) == t.charAt(i))
                ++ans;
        }
        writer.println(ans);
        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        private void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        private char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        private String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

        private int nextInt() {
            return Integer.valueOf(next());
        }

        private long nextLong() {
            return Long.valueOf(next());
        }

        private double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

Measured memory_bytes: 22996
#include "bits/stdc++.h"
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
 
//-----------------------------------------------------------------------------------
 
    int N;

    cin >> N;

    if (0 <= log10(N) && log10(N) < 1)
    {
        cout << N << "\n";        
    }
    else if (1 <= log10(N) && log10(N) < 2)
    {
        cout << 9 << "\n";        
    }
    else if (2 <= log10(N) && log10(N) < 3)
    {
        cout << N-99+9 << "\n";        
    }
    else if (3 <= log10(N) && log10(N) < 4)
    {
        cout << 909 << "\n";        
    }
    else if (4 <= log10(N) && log10(N) < 5)
    {
        cout << N-9999+909 << "\n";
    }
    else if (N == 100000){
        cout << 90909 << "\n";
    }
    
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;


#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
ll done = 0, k, flag = 0;
void find(ll digit, ll c, ll num, ll depth) {
	num = num * 10 + digit;
	// cout<<num<<"\n";
	// flag = 1;
	// return;
	if(c == depth) {
		done++;
		if(done == k) {
			cout<<num<<"\n";
			flag = 1;
		}
		return;
	}
	if(digit == 0) {
		find(0, c + 1, num, depth);
		find(1, c + 1, num, depth);
	} else if(digit == 9) {
		find(8, c + 1, num, depth);
		find(9, c + 1, num, depth);
	} else {
		find(digit - 1, c + 1, num, depth);
		find(digit, c + 1, num, depth);
		find(digit + 1, c + 1, num, depth);
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>k;
    ll d = 1, i;
    for(; ; d++) {
    	for(i = 1; i <= 9; i++) {
    		find(i, 1, 0, d);
    		if(flag) {
    			return 0;
    		}
    	}
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r_0 return 0;
#define ll long long
#define pb push_back
#define TIME ios_base::sync_with_stdio(0)
using namespace std;
vector<ll>V,B;
set<int>S;
ll n, a, c, l, r,ans,b,m;
string p,s;
int main()
{
    TIME;
    cin>>n>>m>>a;
    for (int i =n; i <=m; i ++ )
        if (i%a==0)
            ans++;
    cout<<ans;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
#define SP << " " <<
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    string S; cin>>S;
    string mae,ato;

    ll ok=0;
    ll Q; cin>>Q;
    while(Q--){
        ll x; cin>>x;
        if(x==1) {
            ok=1-ok;
            continue;
        }
        ll f; string c; cin>>f>>c;
        if(f==1 xor ok){
            mae+=c;
        }
        else {
            ato+=c;
        }
    }
    if(!ok){
        reverse(ALL(mae));
        cout<< mae;
        cout<< S;
        cout<< ato;
    }
    else{
        reverse(ALL(S));
        reverse(ALL(ato));
        cout<< ato;
        cout<< S;
        cout<< mae;
    }
    cout<<"\n";




}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];
#define int long long

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

signed main(){
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    rep(i,N) cin >> A[i] >> B[i];
    
    const int width = 20000;
    vector<vector<int>> dp(N+1,vector<int>(width+1,INT_MAX));
    dp[0][0] = 0;
    int ans = INT_MAX;
    
    rep(i,N){
        dp[i+1] = dp[i];
        rep(h,width){
            if(A[i] <= h){
                chmin(dp[i+1][h], dp[i+1][h-A[i]]+B[i]);
            }
        }
    }
    reps(i,H,width){
        chmin(ans, dp[N][i]);
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 160640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
const int A = 2e5 + 2;
const int mod = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
  cin >> n;
  cout << (n + 1) / 2;
    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll k, x;
    cin >> k >> x;
    for(ll i = x - k + 1; i < x + k; i++)
        cout << i << ' ';
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int N=4005,mu=998244353;
int a[N],c[N],tmp[N],ans[N],x[N],lx,mx,n;
char s[N],sx[N];
int deg(int *a){
	for (int i=mx;i>=0;i--) 
		if (a[i]) return i;
	return 0; 
}
void del(int *a,int *b,int t){
	for (int i=mx;i>=t;i--)
		a[i]^=b[i-t];
}
void gcd(int *a,int *b,int *c){
	int l1=deg(a),l2=deg(b);
	if (l1<l2) std::swap(a,b),std::swap(l1,l2);
	if (l2==0 && b[0]==0){
		for (int i=0;i<mx;i++) c[i]=a[i];
		return;
	}
	for(int i=l1;i>=l2;i--)
		if (a[i]) del(a,b,i-l2);
	gcd(b,a,c);
}
int main(){
	scanf("%d",&n);
	scanf("%s",sx);
	int lx=strlen(sx);
	for (int i=lx-1,j=0;i>=0;i--,j++) x[i]=sx[j]-'0';
	for (int i=1;i<=n;i++){
		scanf("%s",s);
		int t=strlen(s);
		memset(a,0,sizeof(a));
		for (int i=t-1,j=0;i>=0;i--,j++) a[i]=s[j]-'0';
		mx=std::max(mx,t);
		for (int i=0;i<mx;i++) tmp[i]=ans[i];
		gcd(a,tmp,ans);
	}
	int len=deg(ans);
	memset(a,0,sizeof(a));
	mx=std::max(mx,lx); 
	for(int i=lx-1;i>=len;i--)
		if (a[i]!=x[i]) del(a,ans,i-len);
	int Ans=0;
	for (int i=lx-1;i>=len;i--)
		Ans=(Ans*2ll+x[i])%mu;
	for (int i=len-1;i>=0;i--){
		if (a[i]<x[i]) break;
		if (a[i]>x[i]){
			Ans--;
			break;
		}
	}
	printf("%d\n",(Ans+1)%mu);
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<math.h>
#include<queue>
using namespace std;

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

	if (a > 0)cout << "Positive" << endl;
	else if (a <= 0 && b >= 0)cout << "Zero" << endl;
	else {
		if ((b - a) % 2 == 0) { cout << "Negative" << endl; }
		else cout << "Positive" << endl;

	}
	return 0;
	
}

Measured memory_bytes: 3652
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(55555)

N=int(input())
ans=[]
count=0
i=0
while count<N:
    if primelist[i]%5==1:
        ans.append(primelist[i])
        count+=1
    i+=1
print(*ans)


Measured memory_bytes: 5528
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

char s[200200];
int cnt[333];
int main() {
	scanf("%s", s);
	int n;
	for (n=0; s[n]; n++) ;
	FOR(i,n) cnt[s[i]]++;
	ll res = 1LL*n*(n+1)/2+1;
	for (int i='a'; i<='z'; i++) res -= 1LL * cnt[i] * (cnt[i]+1) / 2;
	printf("%lld\n", res);
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void)
{
	int a=0,i=0;
	char c[10];
	scanf("%s",c);
	while(1){
		if(c[i]=='\0'){
			break;
		}
		if(c[i]=='+'){
			a++;
		}
		else{
			a--;
		}
		i++;
	}
	printf("%d\n",a);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int a[100005];
int main() {
  int n;
  cin >> n;
  ll sum = 0;
  rep(i,n) {
    ll b;
    cin >> b;
    sum+=b;
    a[b]++;
  }
  int q;
  cin >> q;
  rep(i,q) {
    ll c,d;
    cin >> c >> d;
    ll t = a[c];
    sum -= t*c;
    a[c] = 0;
    a[d] += t;
    sum += t*d;
    cout << sum << endl;
  }



  return 0;
}


Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
string s[N] ;
int n;
int f[N];
int main() {
    cin >> n;
    string res = "";
    int num_a = 0, num_b = 0;
    for(int i = 1; i <= n; i++) cin >> s[i] ;
    int cnta = 0, cntb = 0;
    for(int i = 1; i <= n; i++) {
        int l = s[i].length();
        if(s[i][0] == 'B' && s[i][l - 1] == 'A') f[i] = 1;
        else if(s[i][l - 1] == 'A') f[i] = 2, cnta++;
        else if(s[i][0] == 'B') f[i] = 3, cntb++;
    }
    for(int i = 1; i <= n; i++) if(f[i] == 2) {
        res += s[i] ;
        f[i] = 4;
        cnta--;
        break ;
    }
    for(int i = 1; i <= n; i++) if(f[i] == 1) res += s[i] ;
    for(int i = 1; i <= n; i++) if(f[i] == 3){
        res += s[i] ;
        f[i] = 4;
        cntb--;
        break ;
    }
    int cur = 0;
    while(cnta && cntb) {
        if(cur == 0) {
            for(int i = 1; i <= n; i++) {
                if(f[i] == 2) {
                    res += s[i];
                    f[i] = 4;
                    cnta--;
                    break ;
                }
            }
        } else {
            for(int i = 1; i <= n; i++) {
                if(f[i] == 3) {
                    res += s[i];
                    f[i] = 4;
                    cntb--;
                    break ;
                }
            }
        }
        cur ^= 1;
    }
    for(int i = 1; i <= n; i++)
        if(f[i] == 2) res += s[i];
    for(int i = 1; i <= n; i++)
        if(f[i] == 3) res += s[i];
    for(int i = 1; i <= n; i++) if(f[i] == 0) res += s[i] ;
    int ans = 0;
    int L = res.length() ;
    for(int i = 1; i < L; i++) {
        if(res[i] == 'B' && res[i - 1] == 'A') ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 2432