akhauriyash/Code-Regression huggingface dataset:
// tested by Hightail - https://github.com/dj3500/hightail
import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;
import std.datetime, std.bigint;

int n, a;
int[] x;

void main() {
    scan(n, a);
    x = readln.split.to!(int[]);

    x[] -= a;

    auto dp = new long[][](n + 1, 5000 + 1);

    dp[0][2500] = 1;

    foreach (i ; 0 .. n) {
        foreach (j ; 0 .. 5000 + 1) {
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j + x[i]] += dp[i][j];
        }
    }

    writeln(dp[n][2500] - 1);
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


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

Measured memory_bytes: 3708
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define y1 stupid_cmath
#define left stupid_left
#define right stupid_right
#define vi vector <int>
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))

const int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);

ll read_long() {
    ll ans = 0;
    char c;
    bool started = false;
    bool is_negative = false;
    while (true) {
        c = getchar();
        if ((c < '0' || c > '9') && c != '-' && !started) continue;
        if ((c < '0' || c > '9') && c != '-' && started) break;
        if (started) {
            ans = ans * 10;
        }
        started = true;
        if (c == '-') is_negative = true;
        else ans += c - '0';
    }
    if (is_negative) ans *= -1;
    return ans;
}

int a, b, c;
ll k;

int main(){

    cin >> a >> b >> c >> k;
    k %= 2;
    while (k--) swap(a, b);

    cout << a - b << endl;

    return 0;
}


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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

int n, m;
vector<vector<int>> switchs;
map<tuple<int, unsigned long long>, int> dp;

int dfs(int now, bitset<10> b) {
	if (n == now) return b.count() == m;
	auto status = make_tuple(now, b.to_ullong());
	if (dp.count(status)) return dp[status];
	int res = dfs(now + 1, b);
	for (auto&& i : switchs[now]) {
		b[i].flip();
	}
	return dp[status] = res + dfs(now + 1, b);
}

void hawawa()
{
	cin >> n >> m;
	switchs.resize(n);
	for (int i = 0; i < m; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int point;
			cin >> point;
			switchs[point - 1].push_back(i);
		}
	}
	bitset<10> b;
	for (int i = 0; i < m; i++) {
		int p;
		cin >> p;
		b[i] = !p;
	}
	cout << dfs(0, b) << "\n";
}


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


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
#define forr(i,n) for(ll i=0;i<n;i++)
#define mod 1000000007
#define oo 2000000000000000000LL
using namespace std;


void _sol(){
    ll n,d; cin >> n >> d;
    ll cnt= 0;
    forr(i,n){
        ll x,y; cin >> x >> y;
        if( x*x + y*y <= d*d ) cnt++;
    }
    cout << cnt;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    _sol();
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;
struct UnionFind
{
    vector<int> Parent;
    UnionFind(int n)
    {
        Parent=vector<int>(n,-1);
    }
    
    int root(int a)
    {
        if(Parent[a]<0) return a;
        return root(Parent[a]);
    }
    
    int size(int a)
    {
        return -Parent[root(a)];
    }
    
    bool connect(int a,int b)
    {
        if(root(a)==root(b)) return false;
        if(size(a)<size(b)) swap(a,b);
        Parent[root(a)]-=size(b);
        Parent[root(b)]=root(a);
        return true;
    }
    bool judge_connect(int a,int b)
    {
      return root(a)==root(b);
    }
};
int main()
{
  int n,m,k;
  cin>>n>>m>>k;
  UnionFind friends_all(n);
  vector<vector<int>> friends_direct(n),block(n);
  for (int i = 0; i < m; ++i)
  {
    int a,b;
    cin>>a>>b;
    a--;b--;
    friends_direct[a].push_back(b);
    friends_direct[b].push_back(a);
    friends_all.connect(a,b);
  }
  for (int i = 0; i < k; ++i)
  {
    int c,d;
    cin>>c>>d;
    c--;d--;
    block[c].push_back(d);
    block[d].push_back(c);
  }

  for (int i = 0; i < n; ++i)
  {
    int ans=friends_all.size(i);
    for(const auto& e: block[i]) 
    {
      if(friends_all.judge_connect(i,e)) ans--;
    }
    for(const auto& e: friends_direct[i]) 
    {
      if(friends_all.judge_connect(i,e)) ans--;
    }
    ans--;
    cout<<ans<<" ";
  }
}

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

int main(){
  char c;
  cin >> c;
  
  if (c == 'a'){
    cout << "vowel" << endl;
  }
   else if (c == 'i'){
    cout << "vowel" << endl;
  }
   else if (c == 'u'){
    cout << "vowel" << endl;
  }
   else if (c == 'e'){
    cout << "vowel" << endl;
   }
   else if (c == 'o'){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
  
}


Measured memory_bytes: 3564
// https://atcoder.jp/contests/abc178/tasks/abc178_b
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

void solve() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << max({A * C, B * D, A * D, B * C}) << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>

typedef long long ll;
using namespace std;

int main()
{
    ll N, med, sum = 0;
    cin >> N;
    vector <ll> a(N, 0);

    for (ll i = 0; i < N; i++) {
        cin >> a[i];
        a[i] -= i + 1;
    }

    sort(a.begin(), a.end());

    if (N%2 == 0) med = (a[N/2] + a[N/2-1])/2;
    else med = a[(N - 1)/2];

    for (int i = 0; i < N; i++) {
        sum += abs(a[i] - med);
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
// Convex Hull Trick
/*
 thank you, drken!
 追加クエリの直線の傾きが単調減少の場合
 
 - insert (a, b): add y = ax + b
 - query (x): min_i{a[i]*x + b}
 */
template<class T> struct CHT {
    using Line = pair<T, T>;
    deque<Line> lines;
    
    inline bool check(const Line &a, const Line &b, const Line &c) {
        return (b.first - a.first) * (c.second - b.second)
        >= (b.second - a.second) * (c.first - b.first);
    }
    
    void insert(T a, T b) {
        Line l(a, b);
        while (lines.size() >= 2
               && check(lines[(int)lines.size()-2], lines[(int)lines.size()-1], l))
            lines.pop_back();
        lines.push_back(l);
    }
    
    T query(T x) {
        
    }
    
    // クエリの単調性も成り立つ場合 (x が単調増加)
    T query_monotone(T x) {
        while (lines.size() >= 2
               && lines[0].first * x + lines[0].second >= lines[1].first * x + lines[1].second)
            lines.pop_front();
        return lines[0].first * x + lines[0].second;
    }
};

int main(void) {
	llint i,n,C;cin>>n>>C;
    CHT<llint> cht;
	for(i=0;i<n;i++){
		llint h;cin>>h;
		llint ans;
		if(i==0){ans=0;}
		else{ans=cht.query_monotone(h)+h*h+C;}
		cht.insert(-2*h,ans+h*h);
		if(i==n-1){cout<<ans<<endl;}
	}
}

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

using namespace std;

int main()
{

    int n,i,j,c=0;

    cin>>n;

    int a[n];

    for(i=0;i<n;i++)

    {
        cin>>a[i];

    }
    for(i=1;i<=n-2;i++)
    {
        if((a[i-1]<a[i]&& a[i]<a[i+1]) ||(a[i]<a[i-1]&& a[i+1]<a[i]))
            c++;
    }

    cout<<c;
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(n)]
CD = [tuple(map(int, input().split())) for i in range(m)]
for a, b in AB:
	minv = p = float('inf')
	for i, (c, d) in enumerate(CD):
		dist = abs(a - c) + abs(b - d)
		if dist < minv:
			minv = dist
			p = i + 1
	print(p)

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

using namespace std;

void solve() {
    int x, y, z; cin >> x >> y >> z;
    // swap (x, y) got y x z
    // swap (x, z) got z x y
    cout << z << " " << x << " " << y;
}

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(20);
    solve();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;

char str[10005];

int main(int argc, char* argv[])
{
    int n;
    scanf("%d%s", &n, str);
    int len=strlen(str);
    int i;
    for(i=0; i<len; i++) {
        str[i]='A'+(str[i]-'A'+n)%26;
    }
    printf("%s\n", str);

    return 0;
}


Measured memory_bytes: 128
import math
a,b,h,m = map(int,input().split())
rad = abs(6.0 * m -30 * h -0.5 * m)
rad = min(360-rad,rad)
print(math.sqrt(a**2 + b ** 2 -2 * a * b * math.cos((rad/180) * math.pi)))

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector
#define ll long long

int main(void)
{
	int n;
	cin >> n;
	vec<int> a(n, 0);
	rep(i, n) {
		int get;
		cin >> get;
		a[get / 2]++;
	}
	int flag = 1;
	if (n % 2 == 0) {
		rep(i, n / 2) {
			if (a[i] == 2) continue;
			flag = 0;
			break;
		}
	} else {
		if (a[0] != 1) flag = 0;
		rep(i, n / 2) {
			if (a[i + 1] == 2) continue;
			flag = 0;
			break;
		}
	}
	if (flag) {
		ll ans = 1;
		rep(i, n / 2) {
		   ans *= 2;
	   	   ans %= 1000000007;
		}
		cout << ans << endl;
	} else cout << 0 << endl;
	return 0;
}

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

using namespace std;

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

#define int ll


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

	int sum = 0;
	for(int i=0;i<m;i++) sum += a[i];
	
	printf("%lld\n", n-sum>=0 ? n-sum : -1);


	return 0;
}


Measured memory_bytes: 3764
import sys
input = sys.stdin.readline

N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


M=int(input())
Q=[tuple(map(int,input().split())) for i in range(M)]

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    RET=0
    ANS=[y]
    while y!=x:
        RET+=1<<DICT[tuple(sorted([y,USE[y]]))]
        y=USE[y]

    return RET

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if 1<<i & Q2[k]!=0:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])

Measured memory_bytes: 48876
import sys
input=sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n,x = map(int, input().split())
a = list(map(int, input().split()))

m = 10**9
for i in a:
    m = min(m, abs(i-x))

d = make_divisors(m)
d.reverse()
for i in d:
    b = True
    for j in a:
        if abs(j-x) % i != 0:
            b = False
            break
    if b:
        print(i)
        break
    

Measured memory_bytes: 14168
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 1 << 30

int MOD = 1000000007;

ll f(ll x){
    if(x%2==0){
        return x/2;
    } else {
        return 3*x+1;
    }
}

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

    ll s; cin >>s;
    std::vector<ll> v;
    ll i=1LL;
    v.push_back(s);
    ll x = f(s);
    while(find(v.begin(),v.end(),x)==v.end()){
        v.push_back(x);
        x=f(x);
        i++;
    }

    cout << i+1 << endl;


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] a_asArgs)
        {
			Dictionary<string, int> l_dic = new Dictionary<string, int>();
			int l_iN = int.Parse(Console.ReadLine());
			for (int l_iIndex = 0; l_iIndex < l_iN; l_iIndex++)
			{
				int l_iCount;
				string l_sKey = Console.ReadLine();
				if (!l_dic.TryGetValue(l_sKey, out l_iCount))
				{
					l_iCount = 0;
				}
				l_dic[l_sKey] = l_iCount + 1;

			}
			int l_iM = int.Parse(Console.ReadLine());
			for (int l_iIndex = 0; l_iIndex < l_iM; l_iIndex++)
			{
				int l_iCount;
				string l_sKey = Console.ReadLine();
				if (!l_dic.TryGetValue(l_sKey, out l_iCount))
				{
					l_iCount = 0;
				}
				l_dic[l_sKey] = l_iCount - 1;
			}
			int l_iMax = 0;
			foreach (int l_iCount in l_dic.Values)
			{
				if (l_iMax < l_iCount)
				{
					l_iMax = l_iCount;
				}
			}
			Console.WriteLine(l_iMax);
		}
	}
}


Measured memory_bytes: 13152
#include<bits/stdc++.h>
using namespace std;
#define N 2333
#define mod 1000000007

int n,m,k,f[2*N][N],ans;

void pls(int &x,int y) {x=(x+y)%mod;}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();m=read()-1;k=read()-1;
	f[0][0]=1;
	for (int i=0;i<(n+m)/k;i++)
		for (int j=0;j<n;j++){
			for (int l=0;l<=k;l++)
				if (j+l<n&&(i+1)*k-j-l<=m)
				pls(f[i+1][j+l],f[i][j]);
			pls(ans,f[i][j]);
		}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 37120
#include<iostream>
using namespace std;
int main()
{
    int r,g,b,k;
    cin>>r>>g>>b;
    cin>>k;
    while(g<=r && k>0)
    {
        g*=2;
        k--;
    }
    while(b<=g && k>0)
    {
        b*=2;
        k--;
    }
    if(b>g && g>r)
     cout<<" Yes "<<endl;
    else
    {
        cout<<" No "<<endl;
    }
    
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;
 int N,M;
int D[1500][1500];
vpint G[1500];

bool ng[1500];

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        G[a].pb({b,c});
        G[b].pb({a,c});
    }

    rep(i,N){
        fill_n(D[i],N,INF);
        D[i][i]=0;
        priority_queue<pint,vector<pint>,greater<pint>>que;
        que.push({0,i});
        while(que.size()){
            int c,v;
            tie(c,v)=que.top();
            que.pop();
            if(D[i][v]<c)continue;
            for(auto &e:G[v]){
                if(D[i][e.fi]<=c+e.se)continue;
                D[i][e.fi]=c+e.se;
                que.push({c+e.se,e.fi});
            }
        }
    }

    int len=0;
    rep(i,N)rep(j,N)chmax(len,D[i][j]);


    rep(i,N){
        bool used[1500]={};
        queue<int>que;
        rep(j,N)if(D[i][j]==len){
            used[j]=true;
            que.push(j);
        }
        while(que.size()){
            int v=que.front();
            que.pop();
            for(auto &e:G[v]){
                if(D[i][e.fi]+e.se==D[i][v]&&!used[e.fi]){
                    used[e.fi]=true;
                    que.push(e.fi);
                }
            }
        }
        rep(j,N)ng[j]|=used[j];
    }

    vint ans;
    rep(i,N)if(!ng[i])ans.pb(i);
    cout<<ans.size()<<endl;
    rep(i,ans.size())cout<<ans[i]+1<<endl;
    return 0;
}

Measured memory_bytes: 20912
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

template<typename M, typename N>
constexpr common_type_t<M, N> gcd(M a, N b) {
    return b ? gcd(b, a%b) : abs(a);
}

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> ret;
    for (ll i = 2; i*i <= n; ++i) {
        if (n % i != 0) continue;
        ll cnt = 0;
        while (n % i == 0) {
            ++cnt;
            n /= i;
        }
        ret.emplace_back(i, cnt);
    }
    if (n != 1) ret.emplace_back(n, 1);
    return ret;
}

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

    ll g = gcd(a, b);
    int ans = prime_factorize(g).size()+1;

    cout << ans << endl;

    return 0;
}


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

int main() {

    int A, B, C, D;

    cin >> A >> B >> C >> D;

    int i = 1;
    while (A > 0 && C > 0){

        if(i%2==1) C -= B;
        else A -= D;
        i++;
    }

    cout << ((A > 0)? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 3620
N=int(input())
S=input()


if(N%2 == 1):
    print("No")
else:
    half=N//2
    flag=0
    
    for i in range(0,half):
        if(S[i] != S[half+i]):
            flag=1
            break
    
    if(flag==0):
        print("Yes")
    else:
        print("No")







Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  
  cin >> c;

  if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'){
      cout << "vowel" <<endl;
  }
  else
  {
      cout << "consonant" << endl;
  }
  
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn kmp_table(pattern: &Vec<u8>, m: usize, mut kmp: Vec<usize>) -> Vec<usize> {
    let mut len: usize = 0;
    kmp[0] = 0;
    let mut i: usize = 1;
    while i < m {
        if pattern[i] == pattern[len] {
            len = len + 1;
            kmp[i] = len;
            i = i + 1;
        } else {
            if len != 0 {
                len = kmp[len - 1];
            } else {
                kmp[i] = 0;
                i = i + 1;
            }
        }
    }
    kmp
}

fn kmp(string: &Vec<u8>, pattern: &Vec<u8>) -> () {
    let mut out: String = String::new();
    let n = string.len();
    let m = pattern.len();
    let kmp = kmp_table(&pattern, m, vec![0usize; m]);
    let mut i: usize = 0;
    let mut j: usize = 0;
    while i < n {
        if pattern[j] == string[i] {
            i += 1;
            j += 1;
        }
        if j == m {
            out.push_str(&(i - j).to_string());
            out.push('\n');
            j = kmp[j - 1];
        } else if i < n && pattern[j] != string[i] {
            if j != 0 {
                j = kmp[j - 1];
            } else {
                i += 1;
            }
        }
    }
    print!("{}", out);
}

fn main() {
    let t: String = read();
    let p: String = read();
    let string: Vec<u8> = t.as_bytes().to_vec();
    let pattern: Vec<u8> = p.as_bytes().to_vec();
    kmp(&string, &pattern);
}



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

int main() {
  int n,k;
  string s;
  cin >> n >> s >> k;
  for (int i=0; i<n; i++) {
    if (s.at(k-1) != s.at(i)) s.at(i) = '*';
  }
  cout << s << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

#define modulo 1000000007

using namespace std;

int main(){
	int H, W;
	cin >> H >> W;
	vector<vector<int>> grid(H, vector<int>(W, 0)),
			left(H, vector<int>(W, -1)), right(H, vector<int>(W, -1)),
			up(H, vector<int>(W, -1)), down(H, vector<int>(W, -1));
	vector<pair<int, int>> obs_pos;
	
	string str_tmp;
	for(int i = 0; i < H; i++){
		cin >> str_tmp;
		for(int j = 0; j < W; j++){
			if(str_tmp[j] == '#'){
				grid[i][j] = 1;
				obs_pos.push_back(make_pair(i, j));
			}
		}
	}

	int pt1, pt2, cnt;
	int obs_num = obs_pos.size();
	for(int i = 0; i < obs_num; i++){
		pt1 = obs_pos[i].first;		pt2 = obs_pos[i].second; 

		// leftの走査
		cnt = 0;
		for(int j = pt2 - 1; j >= 0; j--){
			if(grid[pt1][j])
				break;
			right[pt1][j] = cnt;
			cnt++;
		}

		// rightの走査
		cnt = 0;
		for(int j = pt2 + 1; j < W; j++){
			if(grid[pt1][j])
				break;
			left[pt1][j] = cnt;
			cnt++;
		}

		// upの走査
		cnt = 0;
		for(int j = pt1 - 1; j >= 0; j--){
			if(grid[j][pt2])
				break;
			down[j][pt2] = cnt;
			cnt++;
		}

		// downの走査
		cnt = 0;
		for(int j = pt1 + 1; j < H; j++){
			if(grid[j][pt2])
				break;
			up[j][pt2] = cnt;
			cnt++;
		}
	}

	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(!grid[i][j]){
				if(left[i][j] == -1)
					left[i][j] = j;
				if(right[i][j] == -1)
					right[i][j] = W - j - 1;
				if(up[i][j] == -1)
					up[i][j] = i;
				if(down[i][j] == -1)
					down[i][j] = H - i - 1;
			}
		}
	}

	int now_max = -1;
	int pos1, pos2;
	for(int i = 0; i < H; i++)
		for(int j = 0; j < W; j++)
			if(!grid[i][j] && now_max < left[i][j] + right[i][j] + up[i][j] + down[i][j]){
				now_max = left[i][j] + right[i][j] + up[i][j] + down[i][j];
				pos1 = i;	pos2 = j;
			}
	
	cout << now_max+1 << endl;
}

Measured memory_bytes: 113260
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * https://beta.atcoder.jp/contests/abc077/tasks/arc084_b
 */
public class Main {

	static Node nodes[];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int M = Integer.parseInt(sc.next());
		nodes = new Node[N];
		for(int i=0; i<N; i++) {
			nodes[i] = new Node(i);
		}

		for(int i=0; i<M; i++){
			Node x = nodes[Integer.parseInt(sc.next()) - 1];
			Node y = nodes[Integer.parseInt(sc.next()) - 1];
			int z = Integer.parseInt(sc.next());
			x.neighbor.put(y, z);
			y.neighbor.put(x, z);
		}
		sc.close();
		
		int ans = assignColor(nodes);
		System.out.println(ans);
	}
	
	static class Node{
		int id;
		Map<Node,Integer> neighbor = new HashMap<>();
		int color = -1;
		Node(int id){
			this.id = id;
		}
	}
	
	static int assignColor(Node[] nodeList){
		int color = 0;
		for(Node node:nodeList){
			if(node.color==-1){
				List<Node> que = new ArrayList<>();
				node.color = color;
				que.add(node);
				while(que.size()>0){
					for(Node n: que.remove(0).neighbor.keySet()){
						if(n.color==-1){
							n.color = color;
							que.add(n);
						}
					}
				}
				color++;
			}
		}
		return color;
	}


}

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

int main() {
    double w,h;
    int x,y;cin>>w>>h>>x>>y;
    int cc = 0;
    if(w/2==x && h/2==y)cc=1;
    cout<<setprecision(10)<<w*h/2<<" " <<cc<<endl;
	return 0;
}

Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
string s;
main()
{
    int i;
    while(cin>>s)
    {
        int num=0;
        for(i=0;i<s.size();i++) s[i]=='+' ? num++ : num--;
        printf("%d\n",num);
    }
    return 0;
}

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

typedef struct list tree;

struct list{
  int n, ln, rn;
  tree *l, *r;
};

void add_t(tree *t, int n, int l, int r){
    t[n].n = n;
    t[n].ln = l;
    t[n].rn = r;
    t[n].l = NULL;
    t[n].r = NULL;
}

void str_t(int i, tree *t){
  if(t[i].ln != -1){
    t[i].l = &t[t[i].ln];
    str_t(t[i].ln, t);
  }
  if(t[i].rn != -1){
    t[i].r = &t[t[i].rn];
    str_t(t[i].rn, t);
  }
}

void output(tree *t, int mode){
    if(mode == -1) printf(" %d", t->n);
    if(t->ln != -1) output(t->l, mode);
    if(mode == 0) printf(" %d", t->n);
    if(t->rn != -1) output(t->r, mode);
    if(mode == 1) printf(" %d", t->n);
}

int main(){
  int i, num, n, l, r, *f;
  tree *t;

  scanf("%d", &num);

  t = malloc(num * sizeof(tree));
  f = malloc(num * sizeof(int));

  for(i = 0; i < num; i++) f[i] = 1;

  for(i = 0; i < num; i++){
    scanf("%d %d %d", &n, &l, &r);
    add_t(t, n, l, r);
    f[l] = 0;
    f[r] = 0;
  }

  for(i = 0; i < num; i++){
    if(f[i]){
       str_t(i, t);
       break;
     }
  }

  printf("Preorder\n");
  output(&t[i], -1);
  printf("\nInorder\n");
  output(&t[i], 0);
  printf("\nPostorder\n");
  output(&t[i], 1);
  printf("\n");

  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>

using namespace std;


int map[6][6];

int main(){
	for(int i=0;i<6;i++)for(int j=0;j<6;j++)map[i][j]=-1;
	map[0][1]=map[2][4]=0;
	map[3][5]=map[4][3]=0;
	map[5][1]=0;
	map[0][5]=map[1][2]=1;
	map[2][3]=map[3][1]=1;
	map[4][5]=1;
	string str;
	while(cin>>str && str!="#"){
		int now=0;
		for(int i=0;i<str.size();i++){
			int tmp=str[i]-'0';
			for(int j=0;j<6;j++){
				if(map[now][j]==tmp){
					now=j;
					break;
				}
				if(j==5){
					cout<<"No"<<endl;
					goto fail;
				}
			}
		}
		if(now==3)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		fail:;
	}
}

Measured memory_bytes: 1184
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n, d;
vector<vector<i64>> x;
int main() {
  cin >> n >> d;
  init_n(x, n);
  for (i64 i = 0; i < n; ++i) {
    for (i64 j = 0; j < d; ++j) {
      i64 a;
      cin >> a;
      x[i].push_back(a);
    }
  }

  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    for (i64 j = i + 1; j < n; ++j) {
      i64 s = 0;
      for (i64 k = 0; k < d; ++k) {
        i64 a = x[i][k] - x[j][k];
        s += a * a;
      }
      i64 r = sqrt(double(s));
      ans += s == r * r;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
	int a,b;
	cin >> a >> b;
  	int ans = 0;
  	int outlet = 1;
  	//素直に考えると、電源口がB以上になるまでタップを挿し続けるということ。
  	//
	while(outlet < b){
    --outlet;//一個挿すと一個なくなる
    outlet += a;//挿すと電源口がA増える
    ans++;
    }  
  	cout << ans << endl;
  
}

Measured memory_bytes: 256
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

using namespace std;

#define _CRT_SECURE_NO_WARNINGS
#define REP(i, n) for(int i=0; i<(n); i++)
#define LLREP(i,n) for(LL i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define SORT(x) sort(ALL(x))
#define REVE(x) reverse(ALL(x))
#define MP make_pair
#define PB push_back
#define INF INT_MAX

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<bool>> VVB;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef queue<int> QI;
typedef long long LL;

int ch(string a) {
	int size = SZ(a);
	bool flag = true;
	REP(i, size / 2) {
		if (a[i] != a[i + size / 2])flag = false;
		//cout << a[i] << " " << a[i + size / 2] << endl;
	}
	return flag;
}

int main() {
	string s;
	cin >> s;
	int size = SZ(s), ans = 2;

	for (int i = size % 2 == 0 ? size - 2 : size - 1; i != 2; i -= 2) {
		string t;
		REP(j, i) {
			t.PB(s[j]);
		}
		//cout << t << endl;
		if (ch(t)) { ans = i; break; }
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;
using Pii = std::pair<int, int>;
using Pll = std::pair<ll, ll>;
 
int main(int argc, char *argv[])
{
    ll N, M;
    std::cin >> N >> M;
    
    std::vector<Pll> p(N);
    for (ll i = 0; i < N; i++) {
        ll A, B;
        std::cin >> A >> B;
        p[i].first  = A;
        p[i].second = B;
    } 

    std::sort(p.begin(), p.end());

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        if (p[i].second > M) {
            ans += M * p[i].first;
            break;
        } else {
            M -= p[i].second;
            ans += p[i].first * p[i].second;
        }
    }

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


Measured memory_bytes: 1792
# frozen_string_literal: true

n, k, q = gets.split.map(&:to_i)
a = q.times.map { gets.to_i }

s = Array.new(n) { k - q }

a.each do |e|
  s[e - 1] += 1
end

s.each do |e|
  if e.positive?
    puts 'Yes'
  else
    puts 'No'
  end
end


Measured memory_bytes: 3836
N = int(input())
A = input().split()
A = [int(x) for x in A]
Q = int(input())
S = sum(A)
L = [0 for _ in range(10**5)]

for i in range(N):
    L[A[i]-1] +=1

for i in range(Q):
    B,C = map(int,input().split())
    n = L[B-1]
    if n > 0:
        S = S - n*(B-C)
        L[C-1] += n
        L[B-1] = 0
    print(S)

Measured memory_bytes: 20632
from collections import deque
n,m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
stack = deque([0])
dist = [-1]*n
dist[0] = 0

while stack:
  v = stack.popleft()
  for nv in g[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      stack.append(nv)

print("Yes")
print(*dist[1:], sep= "\n")

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

int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    rep(i,n) cin >> vec[i];
    sort(vec.begin(),vec.end());
    int ans=vec[n/2] - vec[n/2-1];
    cout << ans << endl;
}

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

int main() {
    int n;

    cin >> n;

    vector<int> a(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    for (int i = 0; i < n; i++) {
        if (i==n-1) {
            break;
        }
        if (a[i] == a[i + 1]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
//#include <stack>
#include <climits>
#include <map>
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;

int n,m;
map<int,int> mp;

int main() {
    cin >> n >> m;
    vector<int> a(n);
    vector<int> s(n+1);
    s[0]=0;
    Rep(i,n){
        cin >> a[i];
        s[i+1] = (s[i]+a[i])%m;
    }
    Rep(i,n+1){
        auto itr = mp.find(s[i]);
        if(itr!=mp.end()){
            mp[s[i]]++;
        }else{
            mp[s[i]]=1;
        }
        
    }
    ll res = 0;
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        res+=(ll)(itr->second)*(itr->second-1)/2;
    }
    put(res);
    return 0;
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
    using namespace std;
    #define lc "\n"
    #define fast_io ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(0)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define int long long
    #define c(a,n) for(size_t i = 0; i < n; i++) cin >> a[i];
    #define ffor(n) for(size_t i = 0; i < n; i++)
    #define asort(a) sort(a.begin(), a.end())
    #define rsort(a) sort(a.begin(), a.end(), greater<int>())
    
    typedef vector<int> vi;
    typedef vector<float> vf;
    typedef vector<vi> vii;
    typedef vector<string> vs;
    typedef vector<long long> vll;
    typedef map<string,int> msi;
    typedef map<int,int> mii;
    typedef unordered_map<string,int> umsi;
    

    int32_t main()
    {
        fast_io;
        int n;
        cin >> n;
        vii a(n, vi(3));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
                cin >> a[i][j];
        }
        vii dp(n, vi(3));
        dp[0][0] = a[0][0];
        dp[0][1] = a[0][1];
        dp[0][2] = a[0][2];

        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(j == 0)
                {
                    dp[i][j] = a[i][j] + max(dp[i-1][j+1],dp[i-1][j+2]);
                }
                if(j == 1)
                {
                    dp[i][j] = a[i][j] + max(dp[i-1][j-1],dp[i-1][j+1]);
                }
                if(j == 2)
                {
                    dp[i][j] = a[i][j] + max(dp[i-1][j-1],dp[i-1][j-2]);
                }
            }
        }
        cout << max(max(dp[n-1][0],dp[n-1][1]), dp[n-1][2]);
        return 0;
    }

Measured memory_bytes: 14288
#include <bits/stdc++.h>
#define CFS           \
    cin.tie(nullptr); \
    ios::sync_with_stdio(false);
#define CST(x) cout << fixed << setprecision(x);
using namespace std;
constexpr int IINF = numeric_limits<int>::max();
constexpr long LINF = numeric_limits<long>::max();
constexpr int MOD = (int)1e9 + 7;
// constexpr int MOD = 998244353;

struct Query {
    int a;
    int b;
    int c;
    int d;
};

int dfs(vector<Query>& v, vector<int>& u, int m, int q, int depth)
{
    if (depth == u.size()) {
        // for (const auto x: u) cout << x << ", ";
        // cout << "\n";
        int ans = 0;
        for (size_t i = 0; i < q; i++) {
            if (u[v[i].b] - u[v[i].a] == v[i].c) {
                ans += v[i].d;
            }
        }
        return ans;
    }
    int r = 0;
    if (depth == 0) {
        for (size_t i = 1; i <= m; i++) {
            u[depth] = i;
            r = max(r, dfs(v, u, m, q, depth + 1));
        }
    } else {
        for (size_t i = u[depth - 1]; i <= m; i++) {
            u[depth] = i;
            r = max(r, dfs(v, u, m, q, depth + 1));
        }
    }
    return r;
}

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<Query> v;
    for (size_t i = 0; i < q; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v.push_back({ a - 1, b - 1, c, d });
    }
    vector<int> u(n, 1);
    cout << dfs(v, u, m, q, 0) << "\n";
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using lli=long long int;
const lli mod=1000000007;

constexpr lli mod_normalize(lli a){
  return ((a%mod)+mod)%mod;
}

constexpr lli mod_inv(lli a){
  lli b=mod, u=1, v=0, tmp=0;
  while(b){
    lli t = a/b;
    a -= t*b;
    tmp = a; a = b; b = tmp; //swap(a, b);
    u -= t*v;
    tmp = u; u = v; v = tmp; //swap(u, v);
  }
  return mod_normalize(u);
}

constexpr lli fac_pre_num = 100100;
struct fac_pre_struct{
  lli fac[fac_pre_num], finv[fac_pre_num];
  constexpr fac_pre_struct() : fac{}, finv{} {
    fac[0] = fac[1] = finv[0] = finv[1] = 1;
    for(int i = 2; i < fac_pre_num; i++) fac[i] = i*fac[i-1] % mod;
    finv[fac_pre_num-1] = mod_inv(fac[fac_pre_num-1]);
    for(int i = fac_pre_num-1; i > 2; i--) finv[i-1] = i*finv[i] % mod;
  }
};
constexpr fac_pre_struct fac_pre;

std::tuple<lli, lli, lli> fac_3_mod(lli a, lli b, lli c){
  lli t = 1;
  lli tb=1, tc=1;
  for(int i = 1; i <= a; i++){
    t = (t*i)%mod;
    if(i == b) tb = t;
    if(i == c) tc = t;
  }
  return std::make_tuple(t, tb, tc);
}

lli mod_comb(lli n, lli k){
  if(n < k || k < 0 || n < 0) return 0;
  if(n < fac_pre_num) return fac_pre.fac[n] * (fac_pre.finv[k] * fac_pre.finv[n-k] % mod) % mod;
  lli fn, fk1, fk2;
  std::tie(fn, fk1, fk2) = fac_3_mod(n, k, n-k);
  return fn * (mod_inv(fk1) * mod_inv(fk2) % mod) % mod;
}

class mod_comb_mul{
  std::vector<lli> fac, finv;
  public:
  mod_comb_mul() :
    fac(&fac_pre.fac[0], &fac_pre.fac[fac_pre_num]),
    finv(&fac_pre.finv[0], &fac_pre.finv[fac_pre_num]){}
  lli comb(lli n, lli k){
    if(n < k || k < 0 || n < 0) return 0;
    int pre_size = fac.size();
    if(n >= pre_size){
      fac.resize(n+1);
      finv.resize(n+1);
      for(int i = pre_size; i <= n; i++) fac[i] = i*fac[i-1] % mod;
      finv[n] = mod_inv(fac[n]);
      for(int i = n; i > pre_size; i--) finv[i-1] = i*finv[i] % mod;
    }
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
  }
};

int main(){
  mod_comb_mul mcm;
  int N,K;
  std::cin >> N >> K;
  std::vector<lli> a_arr(N);
  for(int i = 0; i < N; i++) std::cin >> a_arr[i];

  lli min_sum = 0, max_sum = 0;
  std::sort(a_arr.begin(), a_arr.end());
  for(int i = 0; i < N-K+1; i++){
    lli tmp = (a_arr[i]*mod_comb(N-i-1, K-1))%mod;
    min_sum = (min_sum+tmp)%mod;
  }
  std::sort(a_arr.rbegin(), a_arr.rend());
  for(int i = 0; i < N-K+1; i++){
    lli tmp = (a_arr[i]*mod_comb(N-i-1, K-1))%mod;
    max_sum = (max_sum+tmp)%mod;
  }

  std::cout << mod_normalize(max_sum-min_sum+mod) << std::endl;

  return 0;
}



Measured memory_bytes: 2560
import java.util.*;

public class Main {
	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);
		int n=Integer.parseInt(scan.next());
		int k=Integer.parseInt(scan.next());
		int[] h=new int [n];
		for (int i=0;i<n;++i) {
			h[i]=Integer.parseInt(scan.next());
		}
		Arrays.parallelSort(h);
		int min=Integer.MAX_VALUE;
		for(int i=0;i<n-k+1;++i) {
			min=Math.min(min, h[i+k-1]-h[i]);
		}
		
		System.out.print(min);

	}
}
//end


Measured memory_bytes: 48228
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	vector<int> a(n - 1), ans(n, 0);
	for(int i = 0; i < n - 1; ++i) {
		cin >> a[i];
		a[i]--;
		ans[a[i]]++;
	}
	
	for(int i = 0; i < n; ++i) {
		cout << ans[i] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 4848
#include <cstdio>
#include <algorithm>
using namespace std;
int a[3010], n;
long long dp[3010][3010];
long long go(int l, int r) {
	if (l >= r) return 0;
	if (dp[l][r] != -1) return dp[l][r];
	long long &res = dp[l][r];
	int x = (r - l) ^ n;
	if (x & 1) {
		res = min(go(l + 1, r) - a[l], go(l, r - 1) - a[r-1]);
	} else {
		res = max(go(l + 1, r) + a[l], go(l, r - 1) + a[r-1]);
	}
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			dp[i][j] = -1;
		}
	}
	printf("%lld\n", go(0, n));
	return 0;
}


Measured memory_bytes: 70784
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  ll ans = 1;
  vector<ll> num(3);
  for (int i = 0; i < n; ++i) {
    int cnt = 0;
    for (int j = 0; j < 3; ++j) {
      if (num[j] == a[i]) cnt++;
    }
    ans *= cnt;
    ans %= MOD;
    for (int j = 0; j < 3; ++j) {
      if (num[j] == a[i]) {
        num[j]++;
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
using System;
using System.Linq;

class C
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var h = Read();
		var es = new int[h[1]].Select(_ => Read()).ToArray();

		var d = WarshallFloyd(h[0] - 1, es);
		if (d == null) { Console.WriteLine("NEGATIVE CYCLE"); return; }
		Console.WriteLine(string.Join("\n", d.Select(a => string.Join(" ", a.Select(x => x == long.MaxValue ? "INF" : $"{x}")))));
	}

	static long[][] WarshallFloyd(int n, int[][] es)
	{
		var d = new long[n + 1][];
		for (int i = 0; i <= n; i++)
		{
			d[i] = Array.ConvertAll(d, _ => long.MaxValue);
			d[i][i] = 0;
		}

		foreach (var e in es)
		{
			d[e[0]][e[1]] = e[2];
			// 有向グラフの場合、ここを削除します。
			//d[e[1]][e[0]] = e[2];
		}

		for (int k = 0; k <= n; k++)
			for (int i = 0; i <= n; i++)
				for (int j = 0; j <= n; j++)
					if (d[i][k] < long.MaxValue && d[k][j] < long.MaxValue)
						d[i][j] = Math.Min(d[i][j], d[i][k] + d[k][j]);

		if (Enumerable.Range(0, n + 1).Any(i => d[i][i] < 0)) return null;
		return d;
	}
}



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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> v(3, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> v[j][i];
    for (int i = 0; i < n; i++) {
        int ans = 0;
        for (int j = 0; j < 3; j++) {
            if (count(v[j].begin(), v[j].end(), v[j][i]) == 1)
                ans += v[j][i];
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3140
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;

alias Pair = Tuple!(int, "a", int, "b");

void main() {
    readln;
    readln.chomp.group.count.writeln;
}






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

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

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

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


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

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

    int m[3];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n-i; j++){
            int sum;
            sum = 10000*i + 5000*j + (n-i-j)*1000;
            if(sum == y){
                cout << i << " " << j << " " << n-i-j << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl; 
}

Measured memory_bytes: 256
n = gets.split(" ").map(&:to_i)
m = gets.split(" ").map(&:to_i)
ary = []

for i in 1..n.length-1
  if i % 2 != 0
    res = n[i]*100+n[i+1]
    ary.push(res)
  end
end

for s in 1..m.length-1
  if s % 2 != 0
    res = m[s]*100+m[s+1]
    ary.push(res)
  end
end
ary = ary.sort.uniq
arynew = []

for i in 0..ary.length-1
  arynew.push(sprintf("%03d" ,ary[i]))
  arynew[i].insert(-3, ":")
end

puts arynew.join(" ")

Measured memory_bytes: 8720