akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())

k=[]
s=[]
for i in range(m):
    templist=[int(x)-1 for x in input().split()]
    k.append(templist[0]+1)
    s.append(templist[1:])

p=[int(x) for x in input().split()]

b=[] #全部の可能性
for i in range(2**n):
    temp=[]
    for j in range(n):
        if (i>>j)&1==1:
            temp.append(1)
        else:
            temp.append(0)
    b.append(temp)

ans=0
for x in b:
    cnt=0
    for i in range(m):
        temp=0
        for j in range(len(s[i])):
            temp+=x[s[i][j]]
        if temp%2 != p[i]:
            continue
        else:
            cnt+=1
            if cnt==m:
                ans+=1
print(ans)


Measured memory_bytes: 42992
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using _TYPE = int;
typedef tree< _TYPE, null_type, less< _TYPE >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int main() {
    IO;
    int n, m, k;
    vector<int> cost;
    cin >> n >> m >> k;
    int arr[n][m];
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cost.push_back(a);
        for(int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    ll ans = INT_MAX;
    ll s = 0;
    vector<int> aux(m), curron;
    for(int i = 0; i < (1 << n); i++) {
        aux.clear();
        aux.resize(m);
        curron.clear();
        s = 0;
        for(int j = 0; j <= 30; j++) {
            if((1 << j) & i) {
                curron.push_back(j);
                s += cost[j];
            }
        }
        for(int k = 0; k < (int) curron.size(); k++) {
            int e = curron[k];
            for(int j = 0; j < m; j++)
                aux[j] += arr[e][j];
        }
        bool bad = false;
        for(int j = 0; j < m; j++) {
            if(aux[j] < k) {
                bad = true;
                break;
            }
        }
        if(!bad)
            ans = min(ans, s);
    }
    if(ans == INT_MAX)
        ans = -1;
    cout << ans;
    return 0;
}


Measured memory_bytes: 3664
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int a[N], x[N], n, m, mx = -INF, mi = INF, sum;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)scanf("%d", &x[i]);
    if (n >= m) {puts("0"); return 0;}
    sort(x + 1, x + 1 + m);
    for (int i = 1; i < m; ++i)a[i] = x[i + 1] - x[i];
    sort(a + 1, a + m);
    for (int i = m - 1; i >= m - n + 1; --i)sum += a[i];
    printf("%d\n", x[m] - x[1] - sum);
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
 
#define  ff     first
#define  ss     second
#define  pb     push_back
#define  all(x) (x).begin(), (x).end()
#define  rep(i,a,b) for(int i=a ; i<b ; ++i)
#define  deb(x) cout << #x << " - " << x << "\n";
#define  IOS    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  D2(x)  cout << "[" << #x << ": "; for(auto it:x) cout << it << " "; cout << "]\n"; 
#define  D2p(x)	cout << #x << " ~ [ "; for(auto n: x) cout << n.first << "-" << n.second << " / "; cout << "]" << "\n";
#define  ps(x,y) fixed<<setprecision(y)<<x
 
#define PI 3.141592653589793238462643383279502884L
const ll MOD = 1e9 + 7;
const ll INF = 1000000000;
const ll MAX_N = 1e5 + 2;

int main() {
    IOS;
    ll n,m,sum,res=0; cin >> n >> m >> sum;
    vll v1(n),v2(m);
    rep(i,0,n) cin >> v1[i];
    rep(i,0,m) cin >> v2[i];
    
    rep(i,1,n) v1[i] += v1[i-1];
    rep(i,1,m) v2[i] += v2[i-1];
    
    ll cnt = 0;
    for(ll i=n-1;i>=0;i--){
        ll remain = sum - v1[i];
        if(remain<0) continue;
        auto it = upper_bound(all(v2),remain) - v2.begin();
        cnt = i + it + 1;
        res = max(res,cnt);
    }
    
    auto last1 = upper_bound(all(v2),sum) - v2.begin();
    auto last2 = upper_bound(all(v1),sum) - v1.begin();
    res = max(res,(ll)last1);
    res = max(res,(ll)last2);
    cout << res ;
}

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

int main(void) {
	int N;
	int ans = 0;
	int cnt = 1;
	int col, a;
	cin >> N;
	cin >> a;
	col = a;
	for (int i = 1; i < N; ++i) {
		cin >> a;
		if (a != col) {
			ans += cnt / 2;
			col = a;
			cnt = 1;
		}
		else
			++cnt;
	}
	ans += cnt / 2;

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


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

// 箱根駅伝DPというらしい
// ペアを組んでいく問題で使う。保留したものを区別しなくてよい。
// 上からi段目
// j個保留
// スコアがk
// iが1進むとスコアkが j * 2増える。交換なので2倍。

long long dp[55][55][2605];
int mod = 1000000007;
int main(void)
{
    int n, score;
    cin >> n >> score;
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i+1; j++)
        {
            for (int k = 0; k < score +1; k++)
            {
                {// i番目の数字は入れ替わりなし 〇-------〇
                    dp[i + 1][j][k + j * 2] += dp[i][j][k];
                    dp[i + 1][j][k + j * 2] %= mod;
                }
                {// i番目の数字をともに保留 〇・ ・〇
                    dp[i + 1][j + 1][k + j * 2 + 2] += dp[i][j][k];
                    dp[i + 1][j + 1][k + j * 2 + 2] %= mod;
                }
                {// i番目の数字を過去に保留しているものと交換 〇---/ ・〇
                    dp[i + 1][j][k + j * 2] += dp[i][j][k] * j * 2; // 左右両方あるので2倍
                    dp[i + 1][j][k + j * 2] %= mod;
                }
                {// i番目の数字を過去に保留しているものと交換 〇--/ \-〇
                    if(0 <= (j - 1) ){
                        dp[i + 1][j - 1][k + j * 2 - 2] += dp[i][j][k] * j * j;
                        dp[i + 1][j - 1][k + j * 2 - 2] %= mod;
                    }
                }
            }
            
        }
        
    }
    cout << dp[n][0][score] << endl;
    return 0;
}

Measured memory_bytes: 55552
n,k=list(map(int,input().split()))
s=[]
b=[0]*k
for x in range(k):
    
    l,r=list(map(int,input().split()))
    s.append((l,r))
    
d=[0]*n
d[0]=1
for i in range(1,n):
    j=0
    for l,r in s:
        if i-l>=0:
            b[j]+=d[i-l]
        if i-r-1>=0:
            b[j]-=d[i-r-1]
        
        d[i]+=b[j]
        j+=1
    d[i]%=998244353
print(d[-1])

Measured memory_bytes: 69592
#!/usr/bin/env python


def read():
    return map(int, raw_input().split())


def work((a, b)):
    group = [[1, 3, 5, 7, 8, 10, 12],
             [4, 6, 9, 11],
             [2]]
    
    for vList in group:
        if a in vList and b in vList:
            print "Yes"
            return

    print "No"


if __name__ == "__main__":
    work(read())


Measured memory_bytes: 2568
import java.util.*;

public class Main {
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String atcoder  = sc.next();
    String name = sc.next();
    String contest = sc.next();
    char s = name.charAt(0);
    System.out.println("A" + s + "C");
  }
}

Measured memory_bytes: 21844
n = int(input())
m, a, r, c, h = 0, 0, 0, 0, 0
for _ in range(n):
    i = input()
    i = i[0]
    if i == 'M':
        m += 1
    elif i == 'A':
        a += 1
    elif i == 'R':
        r += 1
    elif i == 'C':
        c += 1
    elif i == 'H':
        h += 1

ans = 0
from itertools import combinations
for i in combinations([m, a, r, c, h], 3):
    i, j, k = i
    ans += i * j * k
print(ans)

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

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)


using namespace std;
ll INF = LONG_LONG_MAX;
ll mod = 1000000000 + 7;

template <typename T, typename L>
void read(vector<T> & _data, L & _size, bool _shift) {
    _data.resize(_size + (ll)_shift);
    for (ll i = (ll)_shift; i < _size + (ll)_shift; i++)
        cin >> _data[i];
}

template <typename T, typename L>
void read(vector<vector<T>> & _data, L & _rows, L & _cols, bool _shiftRows, bool _shiftCols) {
    _data.resize(_rows + (ll)_shiftRows);
    for (ll i = 0; i < _rows + (ll)_shiftRows; i++)
        _data[i].resize(_cols + (ll)_shiftCols);
    for (ll i = (ll)_shiftRows; i < _rows + (ll)_shiftRows; i++)
        for (ll j = (ll)_shiftCols; j < _cols + (ll)_shiftCols; j++)
            cin >> _data[i][j];
}

template <typename T>
void write(vector<T> & _data, bool _shift) {
    for (ll i = (ll)_shift; i < _data.size(); i++)
        cout << _data[i] << " ";
    cout << endl;
}


//TODO: SOLUTION

ll n;
vpll e;

void solve() {
    cin >> n;
    e.resize(n - 1);

    rep(i, 0, n - 1) {
        ll u, v; cin >> u >> v;
        e[i] = {u, v};
    }

    ll ans = 0;

    repi(x, 1, n) {
        ans += x * (n - x + 1);
    }
    rep(x, 0, n - 1) {
        ll u = min(e[x].fi, e[x].se);
        ll v = max(e[x].fi, e[x].se);
        ans -= u * (n - v + 1);
    }

    cout << ans << endl;
}


int main() {

    // TODO: Set value of this variable manually
    bool _multipleTestCases = false;

    if (_multipleTestCases) {
        ll t; cin >> t;
        while (t--)
            solve();
    }
    else {
        solve();
    }

    return 0;
}

Measured memory_bytes: 6284
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (register int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 1e2 + 5 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T = int> T read()
{
	T f = 1, a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	return a * f ;
}

ll power(ll a, ll b)
{
	ll ret = 1;
	for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod;
	return ret;
}

ll n, ans;

ll h[maxn];

ll f[maxn][maxn], g[maxn][maxn];

void solve(ll l, ll r, ll d)
{
	// printf("%lld %lld\n", l, r);
	if(l > r) return ;
	ll pos, maxx = linf;
	rep(i, l, r) if(h[i] < maxx) maxx = h[i], pos = i;
	g[l][r] += h[pos] - d;
	solve(l, pos - 1, h[pos]), solve(pos + 1, r, h[pos]);
}

signed main()
{
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld", &h[i]);
	solve(1, n, 1);
	// rep(i, 1, n) rep(j, i, n) printf("%lld %lld : %lld\n", i, j, g[i][j]);
	rep(i, 1, n) per(j, i - 1, 1) (g[j][i] += g[j + 1][i]) %= (mod - 1);
	// rep(i, 1, n) rep(j, i, n) printf("%lld %lld : %lld\n", i, j, g[i][j]);
	f[1][1] = (2 * power(2, g[1][1])) % mod;
	rep(i, 1, n - 1) rep(j, 1, i)
	{
		(f[i + 1][j + 1] += f[i][j] * power(2, g[i - j + 1][i + 1]) % mod) %= mod;
		(f[i + 1][1] += f[i][j] * power(2, g[i + 1][i + 1]) % mod) %= mod;
	}
	rep(i, 1, n) (ans += f[n][i]) %= mod;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 384
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.20 20:55:26
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

void dfs(int v, int p, vector< vector< int > > &g, vector< int > &color, vector< int > &cnt) {
    for (int u : g[v]) {
        if (p == u) continue;
        color[u] = 1 - color[v];
        cnt[color[u]]++;
        dfs(u, v, g, color, cnt);
    }
}
int main() {
    int n;
    cin >> n;
    vector< vector< int > > g(n);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector< int > color(n, -1);
    vector< int > cnt(2, 0);
    color[0] = 0;
    cnt[0]++;
    dfs(0, -1, g, color, cnt);
    vector< int > ans(n);
    
    if (min(cnt[0], cnt[1]) <= n / 3) {
        int c;
        if (cnt[0] <= n / 3) c = 0;
        else c = 1;
        int now_3 = 3, now_normal = 1;
        for (int i = 0; i < n; i++) {
            if (color[i] == c) {
                ans[i] = now_3;
                now_3+=3;
            } else {
                ans[i] = now_normal;
                if ((now_normal + 1) % 3 != 0 || now_normal + 1 > cnt[c] * 3) {
                    now_normal++;
                } else {
                    now_normal += 2;
                }
            }
        }
    }
    else {
        int now_one = 1, now_two = 2, now_three = 3;
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                if (now_one <= n) {
                    ans[i] = now_one;
                    now_one += 3;
                }
                else {
                    ans[i] = now_three;
                    now_three += 3;
                }
            }
            else {
                if (now_two <= n) {
                    ans[i] = now_two;
                    now_two += 3;
                }
                else {
                    ans[i] = now_three;
                    now_three += 3;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 24804
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pqgreater(x) x, vector<x>, greater<x>
#define abs(x) (x>0?x:-x)
#define decimal(x) cout<<fixed<<setprecision(x)
#define gc getchar//_unlocked
#define pc putchar//_unlocked
const ll mod=998244353;
int solve(); void precomp();
 
#define multitest 0
#define usecase 0
int main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
	if(multitest) cin>>t;
	precomp();
	for(int tc=1; tc<=t; tc++){
		if(multitest && usecase)
			cout<<"Case #"<<tc<<": ";
		solve();
	}
}
void precomp(){	
	return;
}
int a[5005], n, k, sm;
bitset<5005>dp;
int solve(){
	cin>>n>>k; sm=0;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		a[i]=min(a[i], k);
		sm+=a[i];
	}
	sort(a+1, a+n+1);
	dp[0]=1;
	for(int i=n; i>=0; i--){
		bool rs=0;
		for(int j=k-1; j>=max(k-sm,0); j--){
			if(dp[j]){rs=1; break;}
		}
		if(!rs){
			cout<<i<<endl; return 0;
		}
		for(int j=k; j>=a[i]; j--) if(dp[j-a[i]]) dp[j]=1;;
		sm-=a[i];
	}
	return 0;
}

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

int main(void) {
    int a[4], b[4];
    int hit, blow;
    
    while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {
        hit = 0;
        blow = 0;
        
        for(int i = 0; i < 4; ++i) {
            for(int j = 0; j < 4; ++j) {
                if(a[i] == b[j]) {
                    if(i == j) {
                        ++hit;
                    } else {
                        ++blow;
                    }
                }
            }
        }
        cout << hit << ' ' << blow << endl;
    }
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
int n, W;
long long w[110];
long long v[110];
long long dp[110][100010];

int main() {
    cin >> n >> W;
    for(int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }
    for(int j = 0; j <= W; ++j) {
        dp[0][j] = 0;
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= W; ++j) {
            if(j+w[i] <= W) {
                dp[i+1][j+w[i]] = dp[i][j] + v[i];
            }

            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
        }
    }

    cout << dp[n][W] << endl;
}

Measured memory_bytes: 80128
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=False):
    if mina:
        return list(map(mina1, read().split()))
    else:
        return list(map(int, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')


Measured memory_bytes: 232364
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N,i;
cin>>N;
vector<int>a(N);
vector<int>b(N);
for(i=0;i<N;i++){
cin>>a[i];
b[i]=a[i];}

sort(b.begin(),b.end());
if(b[N/2-1]==b[N/2]){
for(i=0;i<N;i++){
printf("%d\n",b[N/2]);}}
else{
for(i=0;i<N;i++){
if(a[i]<=b[N/2-1])printf("%d\n",b[N/2]);
else printf("%d\n",b[N/2-1]);
}}
return 0;
}

Measured memory_bytes: 3712
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int main(){
    int n,t,a;
    scanf("%d%d%d",&n,&t,&a);
    int h[n];
    for(int i = 0;i < n;i++){
        scanf("%d",&h[i]);
    }
    float b,c;

    int place = 1;
    b = (t - a) / 0.006;
    c = abs(b - h[0]);
    for(int i = 1;i < n;i++){
        if(c > abs(b - h[i])){
            c = abs(b - h[i]);
            place = i + 1;
        }
    }
    printf("%d\n",place);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
const int nAlpha = 26;

int k, n, en[N], cnt[N][nAlpha][nAlpha];
string s[N], t;

struct TNode {
    TNode* c[nAlpha];
    int cnt, id;
} *root;
typedef TNode* PNode;

PNode Add() {
    PNode ptr = new TNode();
    for(int i = 0; i < nAlpha; ++i) ptr -> c[i] = NULL;
    ptr -> cnt = ptr -> id = 0;
    return ptr;
}

void Insert(int id) {
    PNode ptr = root;
    for(int i = 0; i < int(s[id].size()); ++i) {
       s[id][i] -= 'a';
       if(ptr -> c[s[id][i]] == NULL) ptr -> c[s[id][i]] = Add();
       ptr = ptr -> c[s[id][i]], ++ptr -> cnt;
    }
    ptr -> id = id;
}

void Count(int id) {
    PNode ptr = root;
    for(int i = 0; i < int(s[id].size()); ++i) {
       for(int j = 0; j < nAlpha; ++j) {
          if(j != s[id][i] && ptr -> c[j])
            cnt[id][s[id][i]][j] += ptr -> c[j] -> cnt;
       }
       ptr = ptr -> c[s[id][i]];
       if(ptr -> id) ++en[id];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n; root = Add();
    for(int i = 1; i <= n; ++i) {
        cin >> s[i]; Insert(i);
    }
    for(int i = 1; i <= n; ++i) {
        Count(i);
    }
    int q; cin >> q;
    while(q --) {
       cin >> k >> t;
       int res = en[k];
       for(int i = 0; i < nAlpha; ++i) {
          for(int j = 0; j < i; ++j) {
             res += cnt[k][t[i] - 'a'][t[j] - 'a'];
          }
       }
       cout << res << '\n';
    }
}


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

typedef struct node {
  int next;
  vector<int> befs;
  int cost;
  int tail;
} node;

int ans;

int checkcost(node *a[],int i){
  int ma = 0;
  vector<int>::iterator it;
  for(it = a[i]->befs.begin(); it != a[i]->befs.end(); ++it){
    a[*it]->cost = a[i]->cost + 1;
    a[*it]->tail = checkcost(a, *it);
    ma = max(ma,a[*it]->tail);
  }
  return ma + 1;
}

int cuttail(node *a[],int i,int K){
  int t = -1;
  int ma = 0;
  vector<int>::iterator it;
  for(it = a[i]->befs.begin(); it != a[i]->befs.end(); ++it){
    if(a[*it]->tail > K){
      a[*it]->tail = cuttail(a, *it, K);
    }
    if(i != 0 && a[*it]->tail == K){
      ++ans;
      a[*it]->tail = 0;
    }
    ma = max(ma,a[*it]->tail);
  }
  return ma + 1;
}

int main(int argc, char* argv[]){
  ans = 0;
  int N, K;
  cin >> N >> K;
  node *a[N];
  int i;
  int l;
  for(i=0; i<N; ++i){
    a[i] = new node();
  }
  for(i=0; i<N; ++i){
    cin >> l;
    if(i==0){
      if(l!=1){
        l = 1;
        ++ans;
      }
    }else{
      a[l-1]->befs.push_back(i);
    }
    a[i]->next = l-1;
    //a[i].cost = -1;
  }
  a[0]->cost = 0;
  a[0]->tail = checkcost(a,0);
  a[0]->tail = cuttail(a,0,K);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 16640
import time
def main():
    S = input()
    h = time.strptime("2019/04/30", "%Y/%m/%d")
    target = time.strptime(S, "%Y/%m/%d")
    if target <= h:
        print("Heisei")
    else:
        print("TBD")
if __name__ == "__main__":
    main()

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

string changeAsterisk(string inputString,int position,int stringLength){
//    cout << inputString << " " << position << " " << stringLength << endl;
    char remainChar=inputString[position-1];
    int scanPosition;
    for(scanPosition = 0;scanPosition < stringLength;scanPosition++){
        if(inputString[scanPosition] != remainChar){
            inputString[scanPosition] = '*';
        }
    }
    return inputString;
}

int main(void){
    string S,outputString;
    int N,K;
    cin >> N;
    cin >> S;
    cin >> K;
    outputString = changeAsterisk(S,K,N);
    cout << outputString << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define eb              emplace_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mpii            map<int,int>
#define mpsi            map<string,int>
#define mpss            map<string,string>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int>>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define all(v)          v.begin(),v.end()
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x

#define deb(x)          cout<<"("<<#x<<")"<<"----->"<<x<<"\n"
#define clr(ar)         memset(ar,0,sizeof(ar))
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define sz 100009
#define si(x) scanf("%lld",&x)
#define sii(x,y) scanf("%lld %lld",&x,&y)
#define out(x) printf("%lld\n",x)
#define spc  printf(" ")
#define line printf("\n")
#define mod 1000000007
#define pf printf
int a[sz];
int32_t main()
{
	int i,j,n,m,cs,test,k,l;
	si(n);
	for(i=1;i<=n;i++)
		si(a[i]);
	int dp[n+1];
	clr(dp);
	dp[1] = 0;

	dp[2] = abs(a[1] - a[2]);

	for(i=3;i<=n;i++)
	{
		dp[i] = min((abs(a[i] - a[i-1]) + dp[i-1]),(abs(a[i] - a[i-2])+dp[i-2]));
	}
	out(dp[n]);

return 0;
}







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


int main(){
  
 int N,K,d,e;
  cin >> N >> K;
  
  vector<int> s(N,0);
  
  rep(i,K){
    cin >>  d;
    rep(j,d){
      cin >> e;
      s.at(e-1)++;
    }
  }
  int c=0;
  rep(i,N){
    if(s.at(i)==0)
      c++;
    
  }
  cout << c << endl;
}

Measured memory_bytes: 3600
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int,int> pii;
typedef pair <db,db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e18;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int N=200005;


void solve()
{
    int n,k;
    cin>>n>>k;
    int cnt[10]={0};
    int d;
    for(int i=0;i<k;i++)
    {
        cin>>d;cnt[d]=1;
    }
    for(int x=n;x<=100*n;x++)
    {
        int z=x;int pos=1;
        while(z>0)
        {
            d=z%10;
            z=z/10;
            if(cnt[d])
            {
                pos=0;break;
            }
        }
        if(pos)
        {
            cout<<x<<endl;
            return;
        }
    }
    
    
}


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




Measured memory_bytes: 3608
# ＤＦＳ, パターン列挙_全探索用

n = int(input())

# DFS_start
stack = [0] # 初期化_ここでは'0'を設置
pre_ans = [] # パターン候補の器_初期化

while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if tmp <= n: # パターンとしての条件を確認
        pre_ans.append(tmp) # 条件に合えば append
        x = tmp * 10 + 3 # パターンの候補を作成して...
        y = tmp * 10 + 5 # 〃
        z = tmp * 10 + 7 # 〃
        stack += [x, y, z]  # 積む
# DFS_end

ans = 0
for i in pre_ans: # 列挙したパターンを全探索
    if len(set(str(i))) == 3:
        ans += 1

print(ans)

Measured memory_bytes: 4468
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

const int N = 301;

int dp[N][N];

int findmax(int n,int lim,vector<int> &cost,vector<int>& abil){
  rep(i,N)rep(j,N)dp[i][j]=0;
  dp[0][0]=0;
  for(int i=cost[0];i<=lim;i+=cost[0]){
    dp[0][i]=dp[0][i-cost[0]]+abil[0];
  }

  
  REP(i,1,n){
    rep(j,lim+1){
      dp[i][j]=dp[i-1][j];
      if (j-cost[i] >= 0)dp[i][j]=max(dp[i][j],dp[i][j-cost[i]]+abil[i]);
    }
  }


  int ret=0;
  for(int i=0;i<=lim;i++){
    ret=max(ret,dp[n-1][i]);
  }
  return ret;
}

main(){
  int n,lim;
  while(cin>>n>>lim){
    vector<int> cost(n),v(n),d(n),l(n);
    string tmp;getline(cin,tmp);
    rep(i,n){
      getline(cin,tmp);
      cin>>cost[i]>>v[i]>>d[i]>>l[i];
      //      cout << tmp << endl;
      //      cout << cost[i] <<" " << v[i] <<" " << d[i] <<" " << l[i] << endl;
      getline(cin,tmp);
    }
    int ahoge=max(findmax(n,lim,cost,v),findmax(n,lim,cost,d));
    ahoge=max(ahoge,findmax(n,lim,cost,l));
    cout << ahoge << endl;
  }
}

Measured memory_bytes: 1288
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    int A,B; cin>>A>>B;
    string ans = "No";
    if (A%2==1 && B%2==1) ans = "Yes";
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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 gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N,H;
    cin >> N >> H;
    vector<P> katana(N);
    ll a,b;
    ll cut = 0;
    rep(i,N){
        cin >> a >> b;
        cut = max(cut,a);
        katana[i] = P(b,a);
    }
    sort(all(katana));//throw,cut
    ll cnt = 0;
    ll ans = 0;
    for(ll i = N - 1;i >= 0;i--){
        if(cut <= katana[i].first){
            cnt += katana[i].first;
            ans++;
        }
        if(cnt >= H){
            cout << ans << endl;
            return 0;
        }
    }
    ll remain = H - cnt;
    if(remain % cut == 0){
        cout << ans + remain / cut << endl;
    }
    else{
        cout << ans + remain / cut + 1 << endl;
    }
}

Measured memory_bytes: 4728
#include <iostream>

using namespace std;

int n,ans;
int sum(int nr){
  int ansa=0;
  while(nr)ansa+=nr%10,nr/=10;
  return ansa;
}

int main()
{
    cin>>n;
    ans=1000000000;
    for(int i=1;i<n;i++)ans=min(ans,sum(i)+sum(n-i));
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std;
#define max 70


class Node{
public:
	int cost;
	int x;
	int y;
	Node(int c,int _x,int _y){
		cost=c;
		x=_x;
		y=_y;
	}
};

typedef queue <Node> bq;
int map[max][max];
bool visited[max][max];
int dx[]={ 0, 1, 0,-1};
int dy[]={ 1, 0,-1, 0};
int w,h;

void init(){
	int i,j;
	for(i=0;i<max;i++){
		for(j=0;j<max;j++){
			map[i][j]=0;
			visited[i][j]=false;
		}
	}
}
void print(){
	int i,j;
	for(i=0;i<2*h-1;i++){
		if(i%2==0)cout<<"|";
		else cout<<" ";
		for(j=0;j<2*w;j++){
			if(i%2==0)printf("%s",map[i][j]?"|":" ");
			else printf("%s",map[i][j]?"_":" ");
		}
		if(i%2==0)cout<<"|";
		printf("\n");
	}
}
int bfs(){
	bq q;
	q.push(Node(1,0,0));


	while(!q.empty()){
		Node cur = q.front();q.pop();
		if(cur.x==2*(w-1) && cur.y==2*(h-1)){
			return cur.cost;
		}

		if(visited[cur.y][cur.x])continue;
		visited[cur.y][cur.x]=true;
		for(int i=0;i<4;i++){
			if(cur.y+dy[i]<0 || cur.y+dy[i]>2*(h-1) || cur.x+dx[i]<0 || cur.x+dx[i]>2*(w-1)
					|| map[cur.y+dy[i]][cur.x+dx[i]]==1)continue;
			q.push(Node(cur.cost+1, cur.x+2*dx[i], cur.y+2*dy[i]));
		}

	}
	return 0;
}
int main(){
	int i,j;
	while(cin>>w>>h&&(w||h)){
		init();
		for(i=0;i<2*h-1;i++){
			int k;
			if(i%2==0){
				for(j=0,k=1;j<w-1;j++){
					cin>>map[i][k];
					k+=2;
				}
			}
			else{
				for(j=0,k=0;j<w;j++){
					cin>>map[i][k];
					k+=2;
				}
			}
		}
		//print();
		cout<<bfs()<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

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

    final int N = sc.nextInt();
    final int A = sc.nextInt();
    final int B = sc.nextInt();
    System.out.println(maxDubleReader(A,B) + " " + minDubleReader(N, A, B));
    
    sc.close();
  }

  public static int maxDubleReader(int A, int B)
  { 
    return Math.min(A, B);
  }
  
  public static int minDubleReader(int N, int A, int B)
  { 
    return Math.max(0, (A + B) - N );
  }
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

int main()
{
    int s, w;
    cin >> s >> w;
    string ans;
    if (s <= w)
    {
        ans = "unsafe";
    }
    else
    {
        ans = "safe";
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 1000000007
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};

int ans;
int n;
int dp[114][4][4][4];//i番目は決まってて、i-2,i-1,iの文字
signed main(){
	
	cin>>n;
	//ACGT
	//GAC, ACG, A?GC, AG?C
	dp[0][3][3][3]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					rep(m,4){
						if(k==0&&l==2&&m==1)continue;
						if(k==2&&l==0&&m==1)continue;
						if(k==0&&l==1&&m==2)continue;
						if(j==0&&l==2&&m==1)continue;
						if(j==0&&k==2&&m==1)continue;
						dp[i+1][k][l][m]+=dp[i][j][k][l];
						dp[i+1][k][l][m]%=MOD;
					}
				}
			}
		}
	}
	rep(i,4)rep(j,4)rep(k,4){
		ans+=dp[n][i][j][k];
		ans%=MOD;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans=0
y = []

for i in range(n):
  a = map(int, input().split())
  A = list(a)
  for j in range(m):
    x = A[j] * b[j]
    y.append(int(x))
  if sum(y) + c <= 0:
    ans += 0
  else:
    ans += 1
  y.clear()
print(ans)

Measured memory_bytes: 9208
#include <iostream>
using namespace std;
int main(){
	int n;
	int max;
	int min;
	int y[20] = { 0 };

	n = 1;
		int j = 0;
		while (1){
			
			cin >> n;
			if (n == 0) break;
			max = 0;
			min = 1000;
			for (int i = 0; i < n; i++){
				int x[1000] = { 0 };
				cin >> x[i];

				if (max < x[i]) max = x[i];
				if (min > x[i]) min = x[i];
				y[j] += x[i];
			}
			y[j] = y[j]-max - min;
			y[j] = y[j] / (n - 2);
			j++;
		}
	for (int k = 0; k < j; k++){
		cout << y[k]<< endl ;
	}
	return 0;
}

Measured memory_bytes: 1160
I=lambda:[int(i) for i in input().split()]

ans=0
inf=1<<65
n,m=I()
X=set([0,inf,-inf])
Y=set([0,inf,-inf])
V=[]
H=[]
for i in range(n):
    a,b,c=I()
    V.append(((a,b),c))
    Y.add(c)
    X.add(a)
    X.add(b)
 
n+=2
V.append(((-inf,inf),inf))
V.append(((-inf,inf),-inf))
 
for i in range(m):
    a,b,c=I()
    H.append((a,(b,c)))
    X.add(a)
    Y.add(b)
    Y.add(c)
 
m+=2
H.append((inf,(-inf,inf)))
H.append((-inf,(-inf,inf)))

xdc={}
c=1
for j in sorted(X):
    xdc[c]=j
    c+=1
nx=c-1
 
ydc={}
c=1
for j in sorted(Y):
    ydc[c]=j
    c+=1
ny=c-1
 
xdcr=dict(zip(xdc.values(),xdc.keys()))
ydcr=dict(zip(ydc.values(),ydc.keys()))
 
mpy=[[0]*(nx+1+1) for i in range(ny+1+1)]
mpx=[i[:]for i in mpy]

for (a,b),c in V:
    mpx[ydcr[c]][xdcr[a]]+=1
    mpx[ydcr[c]][xdcr[b]]+=-1
for i in range(ny+1):
    for j in range(nx):
        mpx[i][j+1]+=mpx[i][j]
        
for d,(e,f) in H:
    mpy[ydcr[e]][xdcr[d]]+=1
    mpy[ydcr[f]][xdcr[d]]+=-1
for j in range(nx+1):
    for i in range(ny):
        mpy[i+1][j]+=mpy[i][j]

v=[[0]*(nx+1) for i in range(ny+1)]
q=[(xdcr[0],ydcr[0])]
v[ydcr[0]][xdcr[0]]=1

while q:
    cx,cy=q.pop()
    ans+=(xdc[cx]-xdc[cx+1])*(ydc[cy]-ydc[cy+1])
    for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
        nbx=cx+dx
        nby=cy+dy
        if (0>nbx>=nx)or(0>nby>=ny)or v[nby][nbx]==1:
            continue
        if dy!=0:
            if mpx[-~dy//2+cy][cx]==0:
                q.append((nbx,nby))
                v[nby][nbx]=1
        else:
            if mpy[cy][-~dx//2+cx]==0:
                q.append((nbx,nby))
                v[nby][nbx]=1
if ans>=inf:
    ans='INF'
print(ans)


Measured memory_bytes: 541708
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N, M;
  while (cin >> N >> M) {
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    int sum = accumulate(A.begin(), A.end(), 0);
    int cnt = 0;
    for (int x : A) {
      if (x * 4 * M >= sum) ++cnt;
    }
    cout << (cnt >= M ? "Yes" : "No") << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int exsearch(int*, int, int);
main()
{
        int i, n, q, m, *a;
        scanf("%d", &n);
        a = (int*)malloc(sizeof(int) * n);
        for(i = 0; i < n; i++){
        scanf("%d%*c", &a[i]);
        }
        scanf("%d", &q);
        for(i = 0; i < q; i++){
                scanf("%d%*c", &m);
                if(exsearch(a, m, n)){
                        printf("yes\n");
                }else{
                        printf("no\n");
                }
        }
        free(a);
}
int exsearch(int *a, int m, int n)
{
        int result = 0;
        if(!m){
                result = 1;
        return result;
        }else if(!n || m < 0 ){
                result = 0;
                return result;
        }else{
                result |= exsearch(a, m - a[n - 1], n - 1);
                result |= exsearch(a, m, n - 1);
        }
        return result;
}

Measured memory_bytes: 1816
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=(1ull<<60);
const int MOD=1000000007;
struct Nums{
    long long n;
    vector<long long> kaijo;
    long myPow(long x, long n, long m){
        if(n == 0)
            return 1;
        if(n % 2 == 0)
            return myPow(x * x % m, n / 2, m);
        else
            return x * myPow(x, n - 1, m) % m;
    }
    long long modinv(long long a, long long m) {
        long long b = m, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }
    long long comb(long long N,long long K,long long rest){
        long long res=kaijo[N]*modinv(kaijo[K],rest)%rest;
        res*=modinv(kaijo[N-K],rest);
        res%=rest;
        return res;
    }
};
Nums nums;
int f(int n,int x){
  if(n==0){
    return 1;
  }
  if(x==1)return 0;
  int num=nums.myPow(2,n+2,inf)-3;
  int all=0;
  all=nums.myPow(2,n,inf)-1;
  if(x==num/2+1){
    return all+1;
  }
  if(x<num/2+1){
    return f(n-1,x-1);
  }
  if(x==num){
    return 2*f(n-1,num/2)+1;
  }
  else{
    return all+1+f(n-1,x-num/2-1);
  }
}
signed main(){
  int n,x;cin>>n>>x;
  cout<<f(n,x)<<"\n";
  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  201910
//
//  Created by Hajime Sakamoto on 2019/10/09.
//  Copyright © 2019 Hajime Sakamoto. All rights reserved.
//

#include <iostream>
#include <stdio.h>

using namespace std;

int N;

int count_n=0;

void candy(int n){
    for(int i=0; i<n; i++){
        count_n = count_n+i+1;
    }
}


int main(){
    cin >> N;
    candy(N);
    
    cout << count_n;
}


Measured memory_bytes: 256
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

ll memo[100010];
int a[100010];
int n, m;

ll calc(int x) {
	if (a[x] == 1) return 0;
	if (x > n) return 0;
	if (x == n) return 1;
	ll& res = memo[x];
	if (~res) return res;
	res = 0;
	res += calc(x + 1);
	res %= INF;
	res += calc(x + 2);
	res %= INF;
	return res;
}

int buttle(ll a,ll b,ll aa,ll bb){
	ll ab = max(1LL,a / bb);
	ll aab = max(1LL,aa / b);
	if (ab == aab) {
		ll ar = a - ab * bb;
		ll aar = aa - aab * b;
		if (ar > 0 && aar > 0) return 0;
		if (ar <= 0 && aar <= 0) return 0;
		if (ar <= 0) return -1;
		if (aar <= 0) return 1;
	}

	if (ab > aab) {
		return 1;
	}
	else if (ab < aab)
		return -1;
	else return 0;

}
void solv() {
	int n;
	cin >> n;
	ll a[100010];
	ll kind = 0;
	map<ll, int>mp;
	bool inzero = false;
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
		mp[a[i]]++;
		if (mp[a[i]] == 1) {
			kind++;
		}
		if (a[i] == 0) {
			inzero = true;
		}
	}
	if (!inzero) {

		if (n % 3 != 0 || kind > 3) {
			cout << "No" << endl;
			return;
		}
		int c = -1;
		int t = 0;
		for (auto v:mp)
		{
			if (c == -1) c = v.second;
			else if (c != v.second) {
				cout << "No" << endl;
				return;
			}
			t ^= v.first;
		}
		if (t == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	else {
		if(kind > 2){
			cout << "No" << endl;
			return;
		}
		int zc = 0;
		int oc = 0;
		for (auto v :mp)
		{
			if (v.first == 0) zc = v.second;
			else oc = v.second;
		}

		
		if (oc == 0 || (n % 3 == 0 && zc * 2 == oc)) {
			cout << "Yes" << endl;
		}
		else
			cout << "No" << endl;
	}
}

int main() {
	//COMinit();
	solv();

	return 0;
}
 

Measured memory_bytes: 5632
#include <iostream>

using namespace std;

int main(void){
    
    int A, B;
    bool flag = 0;
    cin >> A >> B;
    if(A % 3 == 0 ) flag = 1;
    if(B % 3 == 0 ) flag = 1;
    if((A+B)%3 == 0 )flag = 1;
   
    if(flag == 1) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    
    return 0;
}



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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// head

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

    ll x;
    cin >> x;

    if(x == 1) {
        cout << 0 << endl;
    } else {

        ll cnt = 0;

        for(ll i = 2; i * i <= x; i++) {
            ll y = i;
            if(x % i == 0) {
                while(x % y == 0) {
                    cnt++;
                    x /= y;
                    y *= i;
                }
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) cnt++;
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 3628