akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define maxn 300
#define maxm 100100
using namespace std;
struct edge{
    int r,nxt,w;
}e[maxm];
int head[maxn],esz=1,S,T,dep[maxn],q[maxn],ql,qr,cur[maxn];
void addedge(int u,int v,int w){
//	printf("[%d->%d]\n",u,v);
    e[++esz].r=v;
    e[esz].nxt=head[u];
    e[esz].w=w;
    head[u]=esz;
    e[++esz].r=u;
    e[esz].nxt=head[v];
    e[esz].w=0;
    head[v]=esz;
}
bool bfs(){
    ql=qr=0;
    q[qr++]=S;
//	printf("[ok,%d,%d]",S,T);
    for(int i=S;i<=T;++i)dep[i]=0,cur[i]=head[i];
    dep[S]=1;
    while(ql<qr){
        int x=q[ql++];
        for(int t=head[x];t;t=e[t].nxt)if(!dep[e[t].r]&&e[t].w)
            dep[e[t].r]=dep[x]+1,q[qr++]=e[t].r;
    }
    return dep[T]!=0;
}
int find(int u,int flow){
    if(u==T)return flow;
    int a=0,used=0;
    for(int& t=cur[u];t;t=e[t].nxt)if(e[t].w&&dep[e[t].r]==dep[u]+1&&(a=find(e[t].r,min(flow-used,e[t].w)))){
        e[t].w-=a;e[t^1].w+=a,used+=a;
        if(used==flow)return used;
    }
    if(!used)dep[u]=0;
    return used;
}
int dinic(){
	int ans=0,a=0;
	while(bfs())
		while(a=find(S,1<<30))ans+=a;
	return ans;
}
const int lim=10000010;
int pri[lim],psz,n,a[maxn],tp,d[2];
bool vis[lim],c[lim];
int main(){
	for(int i=2;i<lim;++i){
		if(!vis[i])pri[++psz]=i;
		for(int j=1;j<=psz&&pri[j]*i<lim;++j){
			vis[i*pri[j]]=1;if(i%pri[j]==0)break;
		}
	}
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i)scanf("%d",&x),c[x]^=1,c[x+1]^=1;
	for(int i=1;i<lim;++i)if(c[i])a[++tp]=i;
	S=0,T=tp+3,vis[1]=vis[2]=1;
	for(int i=1;i<=tp;++i)
		for(int j=i+1;j<=tp;++j)if((a[i]&1)!=(a[j]&1)){
//			printf("{%d,%d}",a[i],a[j]);
			if(!vis[a[j]-a[i]]){
				if(a[i]&1)addedge(i,j,1);
				else addedge(j,i,1);
			}
		}
	for(int i=1;i<=tp;++i)
		if(a[i]&1)addedge(S,i,1);
		else addedge(i,T,1);
	int ans=dinic();
	for(int i=1;i<=tp;++i)d[a[i]&1]++;
	d[0]-=ans,d[1]-=ans;
//	printf("[%d,%d,%d]",d[0],d[1],ans);
	if(d[0]%2)ans+=3,d[0]--,d[1]--;
	ans+=d[0]+d[1];
	printf("%d",ans);
}

Measured memory_bytes: 22912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, n) for (int i = (a); i < (n); i++)
#define repb(i, n) for (int i = (n - 1); i >= 0; i--)
#define repb2(i, a, n) for (int i = (n - 1); i >= (a); i--)
#define all(x) x.begin(), x.end()
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
inline void fastio() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
const int INF = 2e9 + 7;

struct arr {
    int x, y, h;
};

void coelem(vector<int> &A, int N) {
    rep(i, N) {
        if (i < N - 1) {
            cosp(A[i]);
        } else {
            co(A[i]);
        }
    }
}

void insertionSort(vector<int> &A, int N) {
    rep2(i, 0, N) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        coelem(A, N);
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) { cin >> A[i]; }
    insertionSort(A, N);
    return 0;
}


Measured memory_bytes: 3084
# coding: utf-8

import math

N = int(input())

xy = []
for i in range(N):
	xy.append([int(p) for p in input().split()])

def dist(a, b):
	return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

def max_dist(a):
	max_d = 0
	for b in xy:
		max_d = max(max_d, dist(a, b))
	return max_d

def g(a):
	ly = 0
	ry = 1000
	for j in range(100):
		#print("    ly = " + str(ly) + " ry = " + str(ry))
		c1 = (ly*2+ry)/3
		c2 = (ly+ry*2)/3
		if max_dist([a,c1]) > max_dist([a,c2]):
			ly = c1
		else:
			ry = c2
	return max_dist([a,ly])

lx = 0
rx = 1000
for i in range(100):
	#print("lx = " + str(lx) + " rx = " + str(rx))
	c1 = (lx*2+rx)/3
	c2 = (lx+rx*2)/3
	if g(c1) > g(c2):
		lx = c1
	else:
		rx = c2

print(g(lx))

Measured memory_bytes: 3064
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <cmath>

using namespace std;

const long long bigNum = 1000000007;

int gcd(int a, int b)
{
	int buffer = a;
	if (b > a)
	{
		a = b;
		b = buffer;
	}

	int remainder = a%b;
	while (remainder != 0)
	{
		a = b;
		b = remainder;
		remainder = a%b;
	}
	return b;
}

long long comb(int n, int k)
{
	vector<int> setofNums;
	long long ret = 1;
	for (int i = 1; i <= k; i++)
	{
		setofNums.push_back(i);
	}
	for (int i = 0; i < k; i++)
	{
		ret = ret * (n - i);
		for (auto it : setofNums)
		{
			if (ret % it == 0)
			{
				ret /= it;
				it = bigNum;
			}
		}
		if (ret > bigNum)
			ret %= bigNum;
	}
	return ret;
}

map<long long, long long> factors;

int main()
{
	string in;
  	cin >> in;
  	int output = 0;
  	for(int i = 0; i < in.size(); i++)
    {
      if(in[i]=='2')
        output++;
    }
  	cout << output << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int num=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n),b;
    for(ll i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end(),greater<ll>());
    ll cnt=1;
    bool flag=false;
    for(ll i=0; i<n-1; i++){
        if(a[i]==a[i+1])cnt++;
        else cnt=1;
        if(cnt%2==0)b.push_back(a[i]);
        if(b.size()>=2){
            flag=true;
            break;
        }
    }
    if(flag){
        ll ans=b[1]*b[0];
        cout << ans << endl;
    }
    else cout << 0 << endl;
}


Measured memory_bytes: 1024
n = int(input())

pw =[]
no  = False
for i in range(n):
    if i == 0:
        wi = input()
        pw.append(wi)
    else:
        w = input()
        if wi[-1]!=w[0] or (w in pw):
            no = True
        pw.append(w)
        wi = w

if no:
    print("No")
else:
    print("Yes")

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

int main(){
	int n, m;
	while(cin >> n){
		int f = 0;
		for(int i = 1; i <= 9; i++){
			if(n / i >= 1 && n / i <= 9 && (n / i * i == n)){
				f = 1;
				printf("Yes\n");
				break;
			}
				
		}
		if(f == 0)
			printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = {}
    c = set()
    for i in a:
        if i not in b:
            b[i] = 1
        else:
            b[i] += 1
            c.add(i)
    d = 0
    for i in c:
        d += (b[i] * (b[i] - 1)) // 2
    for i in range(n):
        e = d - ((b[a[i]] * (b[a[i]] - 1)) // 2) + (((b[a[i]] - 1) * (b[a[i]] - 2)) // 2)
        print(e)

main()

Measured memory_bytes: 26140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
typedef long long ll ;
int main() {
  int N ;
  cin >> N  ;
  int M ;
  double ans = 0 ;
  rep(i,N) {
    cin >> M ;
    ans += (double) 1/M ;
  }
  ans = (double) 1/ans ;
cout << ans <<endl ;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>

using namespace std;

typedef pair<int,int> P;

int main(void){
	int dx[2] = {1,0}, dy[2] = {0,1}, h, w, m[50][50], x, y, i, j, num[10] = {0,1,2,3,4,5,6,7,8,9};
	char s[50][51];
	queue<P> que;
	scanf("%d%d%*c",&h,&w);
	for(i = 0;i < h;i++){
		for(j = 0;j < w;j++)
			s[i][j] = getchar();
		getchar();
	}
	que.push(P(0,0));
	memset(m,-1,sizeof(m));
	m[0][0] = 0;
	while(que.size()){
		x = que.front().first, y = que.front().second;
		que.pop();
		for(i = 0;i < 2;i++){
			if(x + dx[i] < w && y + dy[i] < h && (m[y + dy[i]][x + dx[i]] == -1 || m[y + dy[i]][x + dx[i]] > m[y][x] + num[s[y + dy[i]][x + dx[i]] - '0'])){
				que.push(P(x + dx[i],y + dy[i]));
				m[y + dy[i]][x + dx[i]] = m[y][x] + num[s[y + dy[i]][x + dx[i]] - '0'];
			}
		}
	}
	printf("%d\n",m[h - 1][w - 1]);
	return 0;
}

Measured memory_bytes: 1068
n = int(input())
dict = {}
for _ in range(n):
    ss = ""
    s = sorted(list(input()))
    ss = ss.join(s)
    if dict.get(ss) != None:
        dict[ss] = dict[ss] + 1
    else:
        dict[ss] = 1


ans = 0
for key, val in dict.items():
    ans += val * (val-1) // 2
print(ans)

Measured memory_bytes: 17932
#!/usr/bin/env python3

def main():
    A, B, C, K = map(int, open(0).read().split())

    if abs(A - B) > 10**18:
        print('Unfair')
    else:
        if K % 2:
            print(B - A)
        else:
            print(A - B)


main()

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

bool is_all_nine(string s) {
    bool res = true;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != '9') {
            res = false;
            break;
        }
    }
    return res;
}

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

    int ans;
    if (n.size() == 1) {
        ans = n[0] - '0';
    } else if (is_all_nine(n)) {
        ans = (n[0] - '0') + 9 * ((int)n.size() - 1);
    } else {
        ans = (n[0] - '0') - 1 + 9 * ((int)n.size() - 1);
    }

    cout << ans << endl;

    return 0;
}

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

#define MAX_N 31

int main() {
	int N, M;
	int num[MAX_N] = {0};
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int K;
		cin >> K;
		for (int j = 0; j < K; j++) {
			int a;
			cin >> a;
			num[a]++;
		}
	}
	int sum = 0;
	for (int i = 1; i <= M; i++) {
		if (num[i] == N)
			sum++;
	}
	cout << sum << endl;
}


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

int comp (const void* a, const void* b) {
	return *(int*)a > *(int*)b;
}

int findNumberOfTriangles (int arr[], int n) {
	qsort (arr, n, sizeof (arr[0]), comp);

	int count = 0;

	for (int i = 0; i < n - 2; ++i) {
		int k = i + 2;
		for (int j = i + 1; j < n; ++j) {
			while (k < n && arr[i] + arr[j] > arr[k])
				++k;

			if (k > j) count += k - j - 1;
		}
	}

	return count;
}


int main () {
	int n;
	cin >> n;
	int arr[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	cout << findNumberOfTriangles (arr, n) << "\n";

	return 0;
}


Measured memory_bytes: 256
//kalyanchirla
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
using namespace std;
#define int long long
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define csl ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007

int32_t main()
{ 
    csl;

    int n;
    cin >> n;

    int arr[n];
    for(int i=0;i<n;i++) cin >> arr[i];
    sort(arr,arr+n);

    cout << arr[n-1]-arr[0] << "\n";
}

Measured memory_bytes: 3648
#include<iostream>
using namespace std;
int main()
{
    int a,b,c,k,sum=0;
    cin>>a>>b>>c>>k;
    if(k<=a) sum=k;
    else if(k<=a+b) sum=a;
    else sum=a-(k-a-b);
    cout<<sum;
}

Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;

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

int main() {

    ll A,B,C,D;
    cin >> A >> B >> C >> D;
    ll G = C*D;
    ll E = C;
    ll F = D;
    for(int i=2;i<=sqrt(C);i++){
        while(E%i==0){
            if(F%i==0){
                E /= i;
                F /= i;
                G /= i;
            }else break;
        }
    }
    ll H = A-1;
    ll out = B-(B/C + B/D - B/G);
    if(A!=1) out -= H-(H/C + H/D - H/G);
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,tot,Next[200010],head[100010],tree[200010],In[100010],a[100010],cnt,num[100010];
bool vis[100010];
void add(int x,int y)
{
	tot++;
	Next[tot]=head[x];
	head[x]=tot;
	tree[tot]=y;
}
void dfs(int u,bool flag)
{
	vis[u]=1;
	a[++cnt]=u;
	int U=0,Son=0;
	for (int i=head[u];i;i=Next[i])
	{
		int v=tree[i];
		if (vis[v]) continue;
		Son=v;
		if (In[v]!=1)
		{
			if (U) { puts("-1");exit(0);}
				else U=v;
		}else vis[v]=1,num[u]++;
	}
	if (flag&&!U) dfs(Son,0),num[u]--;
		else if (U) dfs(U,1);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
		In[x]++;In[y]++;
	}
	for (int i=1;i<=n;i++)
	if (In[i]==1)
	{
		int v=tree[head[i]],NUM=0;
		for (int j=head[v];j;j=Next[j])
			if (In[tree[j]]>=2) NUM++;
		if (NUM<2) { dfs(i,(n!=1));break;}
	}
	if (!cnt) { puts("-1");return 0;}
	bool flag=0;
	for (int i=1;i<=cnt/2;i++)
	{
		if (num[a[i]]>num[a[cnt-i+1]]) { flag=1;break;}
		if (num[a[i]]<num[a[cnt-i+1]]) break;
	}
	if (flag)
	{
		for (int i=1;i<=cnt/2;i++) swap(a[i],a[cnt-i+1]);
	}
	int now=0;
	for (int i=1;i<=cnt;i++)
	{
		int x=++now;
		for (int j=1;j<=num[a[i]];j++) printf("%d ",++now);
		printf("%d%c",x," \n"[i==cnt]);
	}
	return 0;
}


Measured memory_bytes: 3968
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

lli dp_keta[100001] = {};
lli dp[100001][14] = {};

int main(void) {

	string str;
	cin >> str;

	lli N = str.size();

	dp[0][0] = 1;
	{
		lli keta = 1;
		for (int k = 0; k < N; k++) {
			dp_keta[N - (k + 1)] = keta;
			keta *= 10;
			keta %= 13LL;
		}
	}

	for (int i = 0; i < N; i++) {

		lli keta = dp_keta[i];

		if (str[i] == '?') {

			for (int k = 0; k < 10; k++) {

				lli a = k;

				for (int j = 0; j < 13; j++) {
					dp[i + 1][(j + a * keta) % 13] += dp[i][j];
					dp[i + 1][(j + a * keta) % 13] %= mod197;
				}
			}

		}
		else {

			lli a = (str[i] - '0');


			for (int j = 0; j < 13; j++) {
				dp[i + 1][(j + a * keta) % 13] += dp[i][j];
				dp[i + 1][(j + a * keta) % 13] %= mod197;
			}

		}
	}

	COUT(dp[N][5] % mod197);

	return 0;
}

Measured memory_bytes: 12160
getnum = gets.chomp.split("").map{|s| s.to_i}
ans = Array.new(getnum.size)

all9_flg = 0

getnum.size.times do |keta|
    if getnum[keta] == 9 && keta > 0
        all9_flg += 1
    end
end

getnum.size.times do |keta|
    #最大桁以外が全て９の場合,１桁の数の時は最大桁をそのまま加算する
    if keta == getnum.size - 1
        if getnum.size == 1 || all9_flg >= getnum.size - 1 
            ans[getnum.size - keta - 1] = getnum[getnum.size - keta - 1]
        else
            ans[getnum.size - keta - 1] = getnum[getnum.size - keta - 1] - 1
        end
    else
        ans[getnum.size - keta - 1] = 9
    end
end

puts ans.inject(:+)

Measured memory_bytes: 1788
def main():
  n = int(input())
  a = list(map(int, input().split()))
  tallest = a[0]
  ans = 0
  for i in range(1, n):
    ans +=  max(0, tallest-a[i])
    tallest = max(tallest, a[i])
  print(ans)
  
if __name__ == "__main__":
  main()

Measured memory_bytes: 32232
package main

import (
  "fmt"
  "os"
  "bufio"
  "strconv"
  "math"
)

func main() {
  sc := bufio.NewScanner(os.Stdin)
  sc.Split(bufio.ScanWords)

  sc.Scan()
  n, _ := strconv.Atoi(sc.Text())
  sc.Scan()
  d, _ := strconv.Atoi(sc.Text())

  var x [10][10]int

  for i := 0; i < n; i++ {
    for j := 0; j < d; j++ {
      sc.Scan()
      x[i][j], _ = strconv.Atoi(sc.Text())
    }
  }

  out := 0
  for i := 0; i < n - 1; i++ {
    for j := i + 1; j < n; j++ {
      l := 0
      for k := 0; k < d; k++ {
        l += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k])
      }
      m := int(math.Sqrt(float64(l)))
      m *= m
      if m == l {
        out++
      }
    }
  }
  fmt.Println(out)
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
void solve(int m,int n){
    vector<bool> v(7368791-2,true);
    int j,t=m;
    for(int i=0;i<n;i++){
        for(j=t;1;j++){
            if(v[j-2])break;
        }
        for(t=j;t<7368791;t+=j){
            v[t-2]=false;
        }
        t=j;
    }
    for(int i=t;i<=7368791;i++){
        if(v[i-2]){
            cout<<i<<endl;
            return ;
        }
    }
}
 
int main(void){
    int m,n;
    while(cin>>m>>n,m){
        solve(m,n);
    }
     
}

Measured memory_bytes: 3992
_ = int(input())
ns = [int(e) for e in input().split()]
_ = int(input())
qs = [int(e) for e in input().split()]


def binary_search(q, ns):
    left  = 0
    right = len(ns)
    while left < right:
        mid = (left + right) // 2
        if q == ns[mid]:
            return True
        elif ns[mid] < q:
            left = mid + 1
        else:
            right = mid
    return False


def main(ns, qs):
    total = 0
    for q in qs:
        if binary_search(q, ns):
            total += 1
    return total


print(main(ns, qs))

Measured memory_bytes: 18928
#include <iostream>
using namespace std;
 
int A[100001];
 
int partition( int p, int r ) {
  int x;
  int tmp;
  x = A[r]; //基準となるA[r]をxとする
 
  //基準となるx以下の要素がpからiまでの範囲に
  //xより大きい要素がi+1からjまでの範囲になるように
  //Aの要素を移動していく
  int i = p - 1;
  for ( int j = p; j < r; j++ ) {
    if ( A[j] <= x ) {
      i++;
       
      tmp = A[i]; //交換
      A[i] = A[j];
      A[j] = tmp;
       
    }
  }
   
  tmp = A[i+1]; //交換
  A[i+1] = A[r];
  A[r] = tmp;
   
  return i + 1;
}
 
int main() {
  int n; cin >> n;
 
  for ( int i = 0; i < n; i++ ) cin >> A[i];
  int q = partition( 0, n-1 );//基準となる値を決定
   
  for ( int i = 0; i < n; i++ ) { //出力
    if ( i == q ) cout << "[";
    cout << A[i];
    if ( i == q ) cout << "]";
    if ( i != n-1 )cout << " ";
  }
  cout << endl;
   
  return 0;
}

Measured memory_bytes: 1548
/////package CodeChef;

import java.util.*;
import java.io.*;
public class Main {
	public static boolean[] b;
	static int[] FF;
	static int[] A;
	public static void main(String[] ard)  throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(System.out);
		String s=br.readLine().trim();
		int a=Integer.valueOf(s);
		if(palin(s))pw.println("Yes");
		else pw.println("No");
		//pw.println(palin(s));
		
	pw.close();
		
	}
	 static long solve(int[] A, int k){
	       //int[] sum=new int[A.length+k+1];
	     ///  for(int i=1;i<=A.length;i++)
		 int n=A.length-1;
	       long ans=0;
	      /// Arrays.sort(A);
	       for(int i=1;i<=n-k+1;i++)
	       {
	           ans=Math.max(ans,Math.abs(A[i]-A[i+k-1]));
	       }
	       
	       return ans;
	    }
	public static boolean palin(String s)
	{
	   int i=0;
	   int j=s.length()-1;
	   while(i<j)
	   {
		   if(s.charAt(i)==s.charAt(j))
		   {
			   i++;
			   j--;
		   }
		   else return false;     
	   }
	   return true;
	}
	
}



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

bool endswith(const string& s, const string& suffix) {
   if(s.size() < suffix.size())
     return false;
   return equal(suffix.rbegin(), suffix.rend(), s.rbegin());
}

int main()
{
  vector<string> keywords;
  keywords.push_back("dream");
  keywords.push_back("dreamer");
  keywords.push_back("erase");
  keywords.push_back("eraser");

  string S; cin >> S;

  while(!S.empty()) {
    for(int i = 0; i < keywords.size(); i++) {
      if(endswith(S, keywords[i])) {
        S = S.substr(0, S.size() - keywords[i].size());
        break;
      }
      if(i == keywords.size() - 1) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }

  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
  int h[10];
  for (int i = 0; i < 10; i++){
    scanf("%d", &h[i]);
  }
  for (int i = 0; i < 3; i++){
    for (int j = 9; j > i; j--){
      if (h[j] > h[j - 1]){
        int temp = h[j];
        h[j] = h[j - 1];
        h[j - 1] = temp;
      }
    }
  }
  for (int i = 0; i < 3; i++){
    printf("%d\n", h[i]);
  }
  return 0;
}


Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    int X,Y,Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second



int main() {
	int a, b, c, n;
	string s, t;
	cin >> a >> b;
	if (a <= 8 && b <= 8)cout << "Yay!" << endl;
	else cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>

#define for0(i, N)    for (int i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (int i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (int i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (int i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (int i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (int i = (x), a = 0; a < (N);  \
                              i = (i + 1) % (N), ++a)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;

struct hu{
    int size;
    map<int, bool> x;
};

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

    ll n;

    cin >> n;

    vector<hu> h(n);

    for0(i, n){
        cin >> h[i].size;

        for0(j, h[i].size){
            int x, y;
            cin >> x >> y;
            h[i].x[x - 1] = y;
        }

    }

    int result = 0;

    for (int i = 0; i < (1 << n); ++i) {
        int now1 = i;
        bool flag = false;

        for0(j, n) {
            if (now1 & 1) {
                for(auto &q : h[j].x){
                    if (((i >> q.first) & 1) ^ q.second) {
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            now1 >>= 1;
        }

        if (flag) continue;

        int c = 0, now = i;
        for0(j, n) {
            if(now & 1)
                ++c;
            now >>= 1;
        }
        result = max(result, c);
    }

    cout << result;

    return 0;
}


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

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);
    vector<int> in_deg(n);
    for (int i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        adj[x - 1].push_back(y - 1);
        ++in_deg[y - 1];
    }

    vector<int> len(n);
    int max_len = 0;
    stack<int> st;
    for (int v = 0; v < n; ++v)
        if (in_deg[v] == 0) st.push(v);

    while (!st.empty()) {
        const int v = st.top(); st.pop();
        max_len = max(max_len, len[v]);
        for (int u : adj[v]) {
            len[u] = max(len[u], len[v] + 1);
            --in_deg[u];
            if (in_deg[u] == 0) st.push(u);
        }
    }

    cout << max_len << endl;

    return 0;
}


Measured memory_bytes: 6528
fun Int.isPalindromic(): Boolean {
    val s = toString()
    var p = 0
    var q = s.length - 1
    while (p < q) {
        if (s[p++] != s[q--]) return false
    }
    return true
}

fun main(args: Array<String>) {
    val (a, b) = readLine()!!.split(' ').map(String::toInt)
    println((a..b).count(Int::isPalindromic))
}


Measured memory_bytes: 39164
mt = [[0, 0, 0] for i in range(3)]
bf = [[0, 0, 0] for i in range(3)]
res = 'No'
for i in range(3):
    mt[i] = list(map(int, input().split(' ')))
n = int(input())
b = []
for i in range(n):
    b.append(int(input()))
for i in b:
    for j in range(3):
        if i in mt[j]:
            bcol = mt[j].index(i)
            bf[j][bcol] = 1
            if sum(bf[j]) == 3 or bf[0][bcol] == 1 and bf[1][bcol] == 1 and bf[2][bcol] == 1:
                res = 'Yes'
            if bf[0][0] == 1 and bf[1][1] == 1 and bf[2][2] == 1 or bf[0][2] == 1 and bf[1][1] == 1 and bf[0][2] == 1:
                res = 'Yes'
print(res)

Measured memory_bytes: 3064
from sys import stdin
N=int(stdin.readline().rstrip())
data_V=[int(x) for x in stdin.readline().rstrip().split()]
data_C=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
for ind, i in enumerate(data_V):
    if i - data_C[ind] > 0:
        ans+=(i - data_C[ind])
print(ans)

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

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
// #define INF 1e9
const ll INF = 1LL << 60;

int n;
vector<int> w;
int dp[305][305];

int rec(int l, int r){
  if(dp[l][r] != -1){
    return dp[l][r];
  }
  if(r-l <= 1){
    return dp[l][r] = 0;
  }
  if(abs(w[l]-w[r-1]) <=1 && rec(l+1, r-1) == r-l-2){
    return dp[l][r] = r-l;
  }
  int ans = 0;
  FOR(i, l+1, r){
    ans = max(ans, rec(l,i)+rec(i, r));
  }
  return dp[l][r] = ans;
}
int main(){
  while(true){
    cin >> n;
    if(n==0) break;
    REP(i, n+1){
      REP(j, n+1){
        dp[i][j] = -1;
      }
    }
    w.resize(n);
    REP(i, n){
      cin >> w[i];
    }
    cout << rec(0, n) << endl;
  }

  return 0;
}




Measured memory_bytes: 3424
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	s = sum(a)
	L = [0]
	for i in a:
		L += [i+j for j in L if j < s/2]
	print min(abs(s-2*i) for i in L)

Measured memory_bytes: 25716
from sys import exit
N,A,B = map(int,input().split())
if A == 0:
    print(0)
    exit(0)
else:
    q = N // (A+B)
    r = N %  (A+B)
    
    ans = A * q
    if r >= A:
        ans += A
    else:
        ans += r

print(ans)

Measured memory_bytes: 9092
#include<bits/stdc++.h>
using namespace std;
#define M_PI  3.1415926535
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define Summon_Tourist ios::sync_with_stdio(false);cin.tie(0);
ll gcd(ll a , ll b) { return b==0?a: gcd( b, a%b); }
ll lcm(ll a , ll b) { return a/gcd(a,b) * b ; }
ll inf = 1e9 + 7;
ll modexp( ll base ,ll power)
 {
     if( power == 0  ) return 1;
     if( power & 1) return base*modexp( base , power-1 )%inf;
     return modexp(base*base%inf,power/2);
 }
// -----------------------------------------------CKMKB-----------------------------------------------------------
// -----------------------------------------------PKMKB-----------------------------------------------------------
 int main()
{
  Summon_Tourist
  //freopen("input.txt" , "r" , stdin ) ;
  ll t = 1;
  //cin>>t;
  while(t--)
  {
    vector<ll> a(10001,0);
    for( ll i = 1 ; i<=100 ; i++ ){
        for( ll j = 1 ; j<=100 ; j++ ){
            for( ll k = 1 ; k<=100 ; k++ ){
                 ll y = (i*i + j*j + k*k) + (i*j + j*k + k*i ) ;
                 if( y<=10000 ) a[y]++;
            }
        }
    }
    ll n;
    cin>>n;
    for( ll i = 1 ; i<=n ; i++ ){
        cout<<a[i]<<endl;
    }


  }
  return 0;

}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define Rep(i,n) for(int i=1;i<=(n);++i)
using LL = long long;
using ULL = unsigned long long;

int main()
{
	double r;
	cin >> r;
	printf("%.6lf\n", acos(-1.0) * r * 2);
	return 0;
}



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

int n,a,b;

int main()
{
	scanf("%d %d",&a,&b);
	for (int i=1;i<=20;i++)
		if (a*i==b) return printf("%d\n",a+b),0;
	printf("%d\n",b-a);
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[333][333],b[333][333],n;
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++){
			scanf("%d",&a[i][j]);
			b[i][j] = a[i][j];
		}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				b[i][j] = min(b[i][j],b[i][k]+b[k][j]);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(a[i][j] != b[i][j]){
				puts("-1");
				return 0;
			}
	long long int res = 0;
	for(int i=1; i<=n; i++)for(int j=i+1; j<=n; j++){
		res += a[i][j];
		for(int k=1; k<=n; k++)if(k!=i && k!=j && a[i][k] + a[k][j] == a[i][j]){
			res -= a[i][j];
			break;
		}
	}
	cout << res <<endl;
	return 0;
}

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

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 1005;

int N, M;
char grid[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			cin >> grid[i][j];
		}
	}

	dp[1][1] = 1;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			if (grid[i][j] != '#') dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i][j]) % MOD;
		}
	}

	cout << dp[N][M] << '\n';

	return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define ture ture
#define flase false
#define falg flag

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;//llの最大9*10^18
const int INF = pow(2, 30) - 1;

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

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

    ll N;
    string S;
    cin >> S;

    if(S=="ABC"){
        cout << "ARC" << endl;
    }
    else{
        cout << "ABC" << endl;
    }
}


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

int main() {
  long int N;
  cin >>N;
  vector<long long int>num(N);
  for(int i=0;i<N;i++){
  num[i]=i;
  }
  vector<long long int>x(N);
  vector<long long int>y(N);
  for(int i=0;i<N;i++){
  cin >>x[i] >>y[i];
  }
  double sum;
  do{
  	for(int j=0;j<N-1;j++){
  	  sum+=sqrt((x[num[j]]-x[num[j+1]])*(x[num[j]]-x[num[j+1]])
              + (y[num[j]]-y[num[j+1]])*(y[num[j]]-y[num[j+1]]));   
    }
  }while(next_permutation(num.begin(),num.end()));
   for(int i=1;i<=N;i++){
  sum/=i;
  } 
  cout << fixed << setprecision(10) << sum << endl;


}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int num=0;
    scanf("%d",&num);
    int x[num];
    int max,min;
    scanf(" %d",&x[0]);
    scanf(" %d",&x[1]);
    max=x[1]-x[0];
    if(x[1]<x[0]){
        min=x[1];
    }else{
        min=x[0];
    }
    
    for(int i=2;i<num;i++){
        scanf(" %d",&x[i]);
        
        if(x[i]-min>max){
            max=x[i]-min;
        }
        if(x[i]<min){
            min=x[i];
        }

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


Measured memory_bytes: 3460
/*                                                  Alpha_The_Coder
                                                  Created on 20/08/2020                                                     */

#include <bits/stdc++.h>
using namespace std;
#define iamalpha ios_base::sync_with_stdio(false);cin.tie(NULL);
#define loop(a,n) for(int i=a;i<n;i++)
#define nloop(a,n) for(int j=a;j<n;j++)
#define lli long long int
void solve();
int main()
{
    iamalpha;
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}
void solve()
{
  string n;
  cin>>n;
  lli sum=0;
  if(n.size()==1 && n[0]=='0')
    cout<<"Yes\n";
  else{
  loop(0,n.size())
  {
      sum+=(long long int)(n[i]-'0');
  }
  if(sum%9==0)cout<<"Yes\n";
  else cout<<"No\n";
}
}

// Solely contributed by Subhojeet Sahoo aka Alpha


Measured memory_bytes: 3660
#include <stdio.h>
#include <math.h>
int main(void){
    // Your code here!
    long int N,sqN;
    
    scanf("%ld\n",&N);
    sqN = (int)sqrt(N);
    
    long int i,a,b;
    a=1;b=sqN;
    for(i=sqN;i>=1;i--){
        if(N%i==0){
            a = i;
            b = N/i;
            break;
        }
    }
    //printf("%ld %ld\n",a,b);
    printf("%ld\n",a+b-2);
    return 0;
}


Measured memory_bytes: 128
/*
map : count()返回被查找元素的个数 有返回1 无返回0  注意map中不存在相同元素 (下标，即first)
		find()返回位置 若没有则返回map.end()
拆点
*/
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
#define MAXN 100005
#define INF 1000000000
int N,M,cnt;
map<int,int> id[2*MAXN];//id[u][c]:u属性为c的虚点编号
vector< pair<int,int> > G[5*MAXN];
int dist[5*MAXN];
bool vis[5*MAXN];
void mg()
{
	for(int i=0;i<M;i++)
	{
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		if(!id[u].count(c)) 
		{
			id[u][c]=++cnt;
			G[u].push_back(make_pair(cnt,1));
			G[cnt].push_back(make_pair(u,1));
		}
		if(!id[v].count(c)) 
		{
			id[v][c]=++cnt;
			G[v].push_back(make_pair(cnt,1));
			G[cnt].push_back(make_pair(v,1));
		}
		/*if(!id[u].count(c)) 
			id[u][c]=cnt++;
		if(!id[v].count(c)) 
			id[v][c]=cnt++;*/
		G[id[u][c]].push_back(make_pair(id[v][c],0));
		G[id[v][c]].push_back(make_pair(id[u][c],0));
	}
	/*for(int i=1;i<=N;i++)
		for(map<int,int>::iterator it=id[i].begin();it!=id[i].end();it++)
		{
			int idd=it->second;
			G[i].push_back(make_pair(idd,1));
			G[idd].push_back(make_pair(i,1));
		}*/
}
void sp()
{
	fill(dist,dist+5*MAXN,INF);
	dist[1]=0;
	vis[1]=1;
	queue<int> que;
	que.push(1);
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i].first,l=G[u][i].second;
			if(dist[v]>dist[u]+l)
			{
				dist[v]=dist[u]+l;
				if(!vis[v])
				{
					vis[v]=1;
					que.push(v);
				}
			}
		}
		vis[u]=0;
	}
}
int main()
{
	scanf("%d %d",&N,&M);
	cnt=N;
	mg();
	sp();
	if(dist[N]==INF) printf("-1\n");
	else printf("%d\n",dist[N]/2);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    unordered_set<string> kind;
    while(n--){
		string lottery;
		cin >> lottery;
		kind.insert(lottery);
	}
	cout << (int)kind.size();
	return 0;
}



Measured memory_bytes: 17688
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>

using namespace std;

int main()
{
    int N,D,X;
    cin >> N >> D >> X;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    int ans=0;
    for(int i=0; i<N; i++){
        ans+=(D-1)/A[i]+1;
    }
    cout << ans+X;


    return 0;
}

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

int main(){
    string s, t, u;
    cin >> s >> t >> u;
    cout << (char)(s[0] - 'a' + 'A');
    cout << (char)(t[0] - 'a' + 'A');
    cout << (char)(u[0] - 'a' + 'A');
	cout << endl;
    return 0;
}

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

int main(){
    int n,v[50],c[50],ans;
  	cin >> n;
  	ans = 0;
	for (int i=0; i < n; i++){
    	cin >> v[i];
    }
	for (int i=0; i < n; i++){
    	cin >> c[i];
    }
	for (int i=0; i < n; i++){
      	if(v[i]>=c[i]){
      		ans += v[i]-c[i];
    	} 
    }
    cout << ans <<endl;
}

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

long long MOD=1000000007;

long long fac[200005],two[200005];

long long expo(long long a,long long b){
	if(b==0)return 1;
	long long temp=expo(a,b/2)%MOD;
	if(b%2==0)return (temp*temp)%MOD;
	return (((temp*temp)%MOD)*a)%MOD;
}

long long inv(long long x){
	return expo(x%MOD,MOD-2)%MOD;
}

long long func(long long k){
	long long ans=fac[2*k];
	ans*=inv(fac[k]);ans%=MOD;
	ans*=inv(fac[k]);ans%=MOD;
	return ans;
}

int main(){
	int n;
	scanf("%d",&n);
	long long c[n];
	for(int i=0;i<n;i++)scanf("%lld",&c[i]);
	sort(c,c+n);
	fac[0]=1;two[0]=1;
	for(long long i=1;i<200005;i++){
		fac[i]=fac[i-1]*i;
		fac[i]%=MOD;
		two[i]=two[i-1]*2;
		two[i]%=MOD;
	}
	long long ans=0;
	for(int i=0;i<n;i++){
		/*
		ans+=(c[i]*two[n-i-1])%MOD;
		ans%=MOD;
		*/
		long long j=n-i-1;
		long long cur=0;
		/*if(j==0)cur=1;
		else if(j%2==0){
			cur=(((((two[j]+func(j/2))%MOD)*inv(2))%MOD)*(j+2))%MOD;
		}else{*/
			cur=(two[j]*(j+2))%MOD;
			cur*=inv(2);cur%=MOD;
		//}
		cur*=two[i];
		cur%=MOD;
		ans+=(cur*c[i])%MOD;
		ans%=MOD;
		/*
		long long cur=k;
		cur*=two[k-1];cur%=MOD;
		if(k%2==0){
			long long x=(two[k-1]+func(k/2));
			x%=MOD;
			cur*=x;
		}else{
			long long x=two[k-1];
			x%=MOD;
			cur*=x;
		}
		cur*=inv(2);
		cur%=MOD;
		cur*=c[i];
		cur%=MOD;
		ans+=cur;
		ans%=MOD;*/
		//printf("%lld\n",ans);
		//*/
	}
	printf("%lld",(ans*two[n])%MOD);
}

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

int main() {
	int n,k;cin>>n>>k;
	vector<int> h(n);
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>h[i];
		if(h[i]>=k)ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

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

    int M = 1_000_000_007;
    int N = scanner.nextInt();
    long[] a = new long[N];
    long[] numOnes = new long[60];
    for (int i = 0; i < N; i++) {
      long aa = scanner.nextLong();
      a[i] = aa;
      int j = 0;
      while (aa > 0) {
        if (aa % 2 != 0) numOnes[j]++;
        j++;
        aa /= 2;
      }
    }

    long[] b = new long[60];
    for (int i = 0; i < 60; i++) {
      b[i] = modpow(2, i, M);
    }

    long res = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < 60; j++) {
        if (a[i] % 2 == 0) {
          res += numOnes[j] * b[j] % M;
        } else {
          res += (N - numOnes[j]) * b[j] % M;
        }
        if (res >= M) res -= M;
        a[i] /= 2;
      }
    }
    res *= inverse(2, M);
    res %= M;
    System.out.println(res);
  }

  private static long inverse(long a, long mod) {
    return modpow(a, mod - 2, mod);
  }

  private static long modpow(long a, long n, long mod) {
    long res = 1;
    while (n > 0) {
      if (n % 2 == 1) res = (res * a) % mod;
      a = (a * a) % mod;
      n >>= 1;
    }
    return res % mod;
  }
}


Measured memory_bytes: 98356
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll Q=1000000007;
const double PI=3.14159265358979323846;

int main(){
  vector<ll> T(2,0);
  vector<ll> V(2,0);
  ll x;
  cin >> T[0] >> T[1] >> V[0] >> V[1] >> x;
  V[0] -= x;
  cin >> x;
  V[1] -= x;
  V[0] = V[0] * T[0];
  V[1] = V[1] * T[1];
  if(V[0]<0){
    V[0] = V[0]*(-1);
    V[1] = V[1]*(-1);
  }
  ll Z = V[0] + V[1];
  if(Z>0){
    cout << 0 << endl;
    return 0;
  }else if(Z==0){
    cout << "infinity" << endl;
    return 0;
  }
  Z = -Z;
  ll ans = 0;
  ans += (V[0]/Z)*2 + 1;
  if(V[0]%Z==0){
    ans --;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
 
int n, m;
string s, t;
int dp[3030][3030];
bool vis[3030][3030];
 
int solve(int a, int b) {
    if (a == n || b == m) return 0;
    if (vis[a][b]) return dp[a][b];
    vis[a][b] = true;
    int ans1=0, ans2=0;
    if(s[a] == t[b]) ans1 = 1+ solve(a+1, b+1);
    else ans2= max(solve(a+1,b), solve(a, b+1) );
    // int ans = max(solve(a+1, b), solve(a, b+1));
    // if (s[a] == t[b]) ans = max(ans, 1 + solve(a+1, b+1));
    return dp[a][b] = max(ans1, ans2);
}
 
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    cin >> s >> t;
    n = int(s.size());//4
    m = int(t.size());//5
    int u = solve(0, 0);//3
    int a = 0, b = 0;
    string ans;
    while (u) 
    {// u ==3;
        if (a < n && dp[a+1][b] == u) {// a < 4 && solve() ==3
            a++;
            continue;
        }
        if (b < m && dp[a][b+1] == u) {
            b++;
            continue;
        }
        ans += s[a];
        u--; a++; b++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 48232
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

int main(){
    int x,n;
    cin >> x >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    if(n == 0){
        cout << x << endl;
        return 0;
    }

    sort(p.begin(), p.end());
    int df = 1000;
    int ans = 0;
    int cnt = 0;
    for(int i = 0; i < 102; i++){
        while(p[cnt] < i){
            cnt++;
        }
        if(i == p[cnt]) continue;
        int tmp = df;
        df = min(df, abs(x-i));
        if(df < tmp){
            ans = i;
        }
    }

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

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

int main() {
	int n,ans=0;
	string s;
	cin >> n;
	cin >> s;
	for (int i = 0; i < n - 2;i++) {
		if (s[i] != 'A') continue;
		if (s[i+1] != 'B') continue;
		if (s[i+2] != 'C') continue;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll x)
{
    return x*x*x*x*x;
}
int main()
{
    ll x;
    cin >>x;
    for(ll i=-500;i<=500;i++)
    {
        int flag=0;
        for(ll j=-500;j<=500;j++)
        {
            if(get(i)-get(j)==x)
            {
                flag=1;
                cout <<i<<" "<<j<<endl;
                break;
            }
        }
        if(flag) break;
    }
}

Measured memory_bytes: 3620
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
int nmax=200000;
vvec g(nmax);

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n,k,q;
    cin>>n>>k>>q;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int ans=INF;
    for(int mi:a){
        vec c;
        multiset<int> s;
        for(int i=0;i<=n;i++){
            if(i==n||a[i]<mi){
                sort(all(c));
                rep(j,(int)c.size()-k+1){
                    s.insert(c[j]);
                }
                c.clear();
            }
            else{
                c.pb(a[i]);
            }
        }
        auto it=s.begin();
        if((int)s.size()<q) continue;
        rep(i,q-1) it++;
        chmin(ans,*it-mi);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;

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

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

int main()
{
  int k;
  int a, b;
  cin >> k >> a >> b;
  for (int i = a; i <= b; i++)
  {
    if (i % k == 0)
    {
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define MAX (ll)(2e1)
#define INF (ll)(1e18)
#define MOD (ll)(1e9)

using namespace std;
using ll = long long;
using cd = complex<double>;

ll cc[20][20];
ll gc (ll a, ll b) {
	if (!a || !b) {
		return max (a, b);
	}
	ll r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

ll ch (string st) {
	int cc = 0, fl = 0;
	int n = st.size ();
	for (int i = 0; i < n; i++) {
		if (fl) {
			cc++;
		}
		if (st[i] == '.') {
			fl = 1;
		}
	}
	int x = 9 - cc;
	for (int i = 0; i < x; i++) {
		st.push_back ('0');
	}
	ll s = 0;
	for (int i = 0; i < st.size (); i++) {
		if (st[i] == '.') {
			continue;
		}
		int x = st[i] - '0';
		s *= 10;
		s += x;
	}
	return s;
}

int main () {
	ll n;
	cin >> n;
	ll ar[n];
	vector<pair<ll, ll>> vp;
	for (ll i = 0; i < n; i++) {
		string st;
		cin >> st;
		ll xx = gc (ch (st), INF);
		ll pt = 0, pf = 0;
		while (xx % 2 == 0) {
			xx /= 2;
			pt++;
		}
		while (xx % 5 == 0) {
			xx /= 5;
			pf++;
		}
		cc[pt][pf]++;
		vp.push_back (make_pair (pt, pf));
	}
	ll ans = 0;
	for (auto v : vp) {
		ll x = 18 - v.first, y = 18 - v.second;
		for (ll i = x; i <= 18; i++)  {
			for (ll j = y; j <= 18; j++) {
				ans += cc[i][j];
			}
		}
		if (18 <= v.first * 2 && 18 <= v.second * 2) {
			ans--;
		}
	}
	cout << ans / 2 << "\n";
}


Measured memory_bytes: 7460
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int H, W, K;
vector<vector<char>> field;

int main() {
	cin >> H >> W >> K;
	field.resize(H);
	for (int i = 0; i < H; i++) {
		field[i].resize(W);
		for (int j = 0; j < W; j++) {
			cin >> field[i][j];
		}
	}

	int ans = 0;

	for (int bitH = 0; bitH < (1 << H); bitH++) {
		for(int bitW = 0; bitW < (1 << W); bitW++) {
			auto work = field;
			for (int i = 0; i < H; i++) {
				if ((bitH >> i) & 1) {
					for (int j = 0; j < W; j++) {
						work[i][j] = 'X';
					}
				}
			}
			for (int i = 0; i < W; i++) {
				if ((bitW >> i) & 1) {
					for (int j = 0; j < H; j++) {
						work[j][i] = 'X';
					}
				}
			}
			
			int cnt = 0;
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++)
					if (work[i][j] == '#')cnt++;
			}
			if (K == cnt)ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628