akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct LDT {
	int h, p, q;
	LDT() {}
	LDT(int h, int p, int q) : h(h), p(p), q(q) {}
};

bool operator <(const LDT& l1, const LDT& l2) {
	return l1.h < l2.h;
}

int main() {
	int n, m, a;
	while ( cin >> n >> m >> a, n || m || a ) {
		vector<LDT> v;
		for (int i = 0; i < m; ++i) {
			int h, p, q; cin >> h >> p >> q;
			v.push_back( LDT(h, p, q) );
		}
		sort(v.begin(), v.end());

		vector<int> ans(n);
		for (int i = 0; i < n; ++i) ans[i] = i+1;
		for (int i = 0; i < v.size(); ++i) {
			swap(ans[v[i].p-1], ans[v[i].q-1]);
		}
		cout << ans[a-1] << endl;
	}
}

Measured memory_bytes: 1224
import numpy as np
N, C = map(int, input().split())
D = np.array(list(map(int, input().split())), dtype=int)
for i in range(C-1):
    D = np.vstack((D, np.array(list(map(int, input().split())), dtype=int)))
Z = np.array(list(map(int, input().split())), dtype=int)
for i in range(N-1):
    Z = np.vstack((Z, np.array(list(map(int, input().split())), dtype=int)))
num = np.zeros((3,C), dtype=int)
for i in range(3):
    X = np.array([[(x+y+2)%3==i for y in range(N)] for x in range(N)])
    for c in range(C):
        Y = ((Z*X)==(c+1))
        num[i,c] = Y.sum()
costs = np.dot(num, D)
mincost = 10**10
for c0 in range(C):
    for c1 in range(C):
        if c1 ==c0:
            continue
        for c2 in range(C):
            if c2 == c0 or c2 == c1:
                continue
            cost = costs[0,c0]+costs[1,c1]+costs[2,c2]
            mincost = min(mincost, cost)
print(mincost)

Measured memory_bytes: 19384
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,N) for(int i = 0;i < (int)(N);i++)
int main(){
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n) cin>>a[i];
  int sum=0;
  rep(j,n){
    rep(i,j){
      sum+=a[i]*a[j];
    }
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxH=10,mxW=1e3;
int h,w,k,ans=1e9;
string g[mxH];
vector<int> v[mxW];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>h>>w>>k;
	for(int i=0;i<h;++i)
	cin>>g[i];
	for(int i=0;i<1<<h-1;++i) 
	{
		int ca=__builtin_popcount(i);
		for(int j=0;j<w;++j) 
		{
			int s=0;
			for(int k=0;k<h;++k) 
			{
				s+=g[k][j]&1;
				if(i>>k&1) 
				{
					v[j].push_back(s);
					s=0;
				}
			}
			v[j].push_back(s);
			for(int vi : v[j])
			if(vi>k)
			ca=1e9;
		}
		vector<int> u(v[0].size());
		for(int j=0;j<w;++j) 
		{
			bool split=0;
			for(int l=0;l<u.size();++l)
			split|=u[l]+v[j][l]>k;
			if(split)
			{
				++ca;
				u=vector<int>(u.size());
			}
			for(int l=0;l<u.size();++l)
			u[l]+=v[j][l];
			v[j].clear();
		}
		ans=min(ca,ans);
	}
	cout<<ans;
}


Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int n, x;
	cin >> n >> x;
	int d=0, cnt=1;
	for(int i=0; i<n; i++){
		int l;
		cin >> l;
		d+=l;
		if(d<=x) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    map<int, int> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.at(i) = a;
        m[a]++;
    }

    vector<int> cnt(2);
    for (auto i: m) {
        cnt.at(i.second % 2)++;
    }
    
    int ans = cnt.at(1) + ((cnt.at(0) % 2 == 0) ? cnt.at(0): cnt.at(0) - 1);
    cout << ans << endl;
}   

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int s, int t, vector<int> & ans)
{
	if(n == 1)
	{
		ans = {s, t};
		return;
	}
	vector<int> l, r;
	int j = __builtin_ctz(s ^ t);
	int mask = (1 << j) - 1;
	int news = (s & mask) ^ ((s >> 1) & (~mask));
	int newt = (t & mask) ^ ((t >> 1) & (~mask)); 
	int mid = news ^ 1;
	solve(n - 1, news, mid, l);
	solve(n - 1, mid, newt, r);
	for(auto v : l)
		ans.push_back((v & mask) ^ ((v & (~mask)) << 1) ^ (s & (1 << j)));
	for(auto v : r)
		ans.push_back((v & mask) ^ ((v & (~mask)) << 1) ^ (t & (1 << j)));
}
int main()
{
	int n, s, t;
	scanf("%d%d%d", &n, &s, &t);
	if(!(__builtin_popcount(s ^ t) & 1))
	{
		puts("NO");
		return 0;
	}
	puts("YES");
	vector<int> ans;
	solve(n, s, t, ans);
	for(int i = 0; i < ans.size(); ++i)
		printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' '); 
	return 0;
}

Measured memory_bytes: 1628
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <complex>
 
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
 
#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define RALL(c) (c).rbegin(), (c).rend()
#define ALLA(a,n) ((a)+0), ((a)+n)
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<string> vstring;
typedef vector<double> vdouble;
 
template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<< ' ' ; cout << endl; }
template<class T>void pp(T v){ EACH(it,v) cout << *it << ' ' ; cout << endl;  }
template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a; }
template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a; }
inline ll to_i(const string& s){ll n;sscanf(s.c_str(),"%lld",&n);return n;}
inline string to_s(ll n){char buf[32];sprintf(buf,"%lld",n);return string(buf);}

int main() {
  int n, m;
  while (cin >> n >> m) {
    int lo = 1, hi = n;
    REP(iter, m) {
      int x, y; cin >> x >> y;
      gs(lo, x);
      ls(hi, y);
    }
    int result = 0;
    gs(result, hi - lo + 1);
    cout << result << endl;
  }
}


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

const int N = 105;

int v[N], h[N];
string t[N];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> t[i];
	
	// horizontal check
	for (int i = 0; i < n; i++) {
		bool temp = true;
		for (int j = 0; j < m; j++) {
			if (t[i][j] == '#') {
				temp = false;
				break;
			}
		}
		if (temp) {
			v[i] = 1;
		}
	}
	
	// vertical check
	for (int j = 0; j < m; j++) {
		bool temp = true;
		for (int i = 0; i < n; i++) {
			if (t[i][j] == '#') {
				temp = false;
				break;
			}
		}
		if (temp) {
			h[j] = 1;
		}
	}
	
	for (int i = 0; i < n; i++) {
		int temp = true;
		if (v[i] == 1) temp = false;
		else for (int j = 0; j < m; j++) if (h[j] != 1) cout << t[i][j];
		if (temp) cout << endl;
		
	}
	
	return 0;
}

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

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

Measured memory_bytes: 256
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;
ll max_n = 1000000000000000;

void Main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> as(N);
    ll s = 1, prev_s = 1;

    rep(i, N){
        sll(as[i]);
        // s *= as[i];
        if(i>=K){
            // if(s%as[i-K] != 0)exit(0);
            if(as[i]>as[i-K]){
                cout << "Yes" <<endl;
            }else{
                cout << "No" <<endl;

            }
        }
        // prev_s = s;
    }
}

int main(){
    Main();
}

Measured memory_bytes: 4344
#include <bits/stdc++.h>
using namespace std;
//using lint = long long;

struct P
{
    int x,y,z;

    bool operator<(const P &a)const{
              return x>a.x;
    }

};

vector<int> v[1];
//bitset<4001000> b;
int a,c,i,b,n,m,k,d;//dy[15]={0,1,0,-1,-1,1,-1,1},dx[15]={1,0,-1,0,1,1,-1,-1};//
int o[111111];
int l[1];
int j[1];
int e;
int dx[10]={0,1,0,-1,1,1,-1,-1},dy[10]={1,0,-1,0,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
long long x,y,mod=998244353,mod2=1000000009,mod3=2017;
long long z;
double pi=3.14159265;
P u[1];
stack<int> s;

//set<long long> s;
queue<int> q,q1;

//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p;
//list<int> l;

string r,r1;
//char r[111331];
//deque<int> de;

bool as(P a,P b)
{
    //if(a.x!=b.x)
        return a.x<b.x;
    //return a.y<b.y;
}


int main()
{
    scanf("%d %d",&a,&b);
    for(int t=1;t<=a;t++)
        scanf("%d",&o[t]);
    int x=1987654321;
    for(int t=1;t+b-1<=a;t++)
    {
        if(o[t]<0&&o[t+b-1]>0)
        {
            x=min(x,o[t+b-1]-o[t]+min(-o[t],o[t+b-1]));
        }
        else if(o[t]<0)
        {
            x=min(x,-o[t]);
        }
        else
        {
            x=min(x,o[t+b-1]);
        }
    }
    printf("%d",x);
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
int main() {
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(i % 2 == 0) {
            cout << s[i];
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n;
	std::cin >> n;
	int val = 0;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++) {
		std::cin >> a[i];
		val ^= a[i];
	}
	for(int i = 0; i < n; i++) {
		a[i] ^= val;
		std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
	}
}

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

int main(){
  string s;
  cin >> s;
  cout << s.at(0) << s.length()-2 << s.at(s.length()-1) <<endl;
}

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

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
 
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int n,k;
int main() {
    cin >> n >> k;
    int ans = n-k+1;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int main()
{
	#ifndef ONLINE_JUDGE
	freopen(".in.txt", "r", stdin);
	freopen(".out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	vector<int> ans(n + 1);
	for(int x = 1; x <= 100; x++) for(int y = 1; y <= 100; y++) for(int z = 1; z <= 100; z++)
	{
		int s = x * x + y * y + z * z + x * y + y * z + x * z;
		if(s <= n) ans[s]++;
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << endl;

	return 0;
}

Measured memory_bytes: 3548
#include <stdio.h>

int sum1to2(int* a,int x,int y){
  int ans=0;
  for(int i=x;i<=y;i++){
    ans+=a[i];
  }
  return ans;
}
int main(){
  int N;
  scanf("%d",&N);
  int lt[N];
  int lv[N+1];
  for(int i=0;i<N;i++){
    scanf("%d",&(lt[i]));
  }
  for(int i=0;i<N;i++){
    scanf("%d",&(lv[i]));
  }
  lv[N]=0;
  double x=0,v=0,pv=0,t,dt=0.5;
  int flag=0,fj;
  for(int i=0;i<N;i++){
    t=0;
    	if(v>lv[i]){
	  v=(double)lv[i];
	  }
    while(t<lt[i]){
      if(i>fj){
        flag=0;
      }
      pv=v;
      for(int j=i;j<N;j++){
	if(sum1to2(lt,i,j)-t<=v-lv[j+1]){
	  flag=1;
	  fj=j;
	}
      }
      if(flag==1){//残り時間で下げられる速度が下げなきゃいけない速度より小さい
	v-=1*dt;
      }else if(v<lv[i]){
	v+=1*dt;
	if(v>lv[i]){
	  v=(double)lv[i];
	  }
      }
      x+=(v+pv)/2.0*dt;
      t+=dt;
    }
  }
  printf("%f",x);
  return 0;
}


Measured memory_bytes: 256
/*
Author: Snickeen 
Email : ff@snickeen.com
If you find any bug, please tell me.
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL INF = 1e18+7;
const LL MOD = 1e9+7;
const LL MAXN = 1e6+7;

/////**********************************************/////



signed main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	LL n,m;
	cin>>n>>m;
	if(n>m)swap(n,m);
	if(n==1)return cout<<(m==1?1:m-2ll),0;
	n-=2;m-=2;
	cout<<n*m<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n,m;
    cin >> n >> m;
    vector<ll>x(m),y(m);
    for(ll i=0;i<m;i++){
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    vector<ll>num(n,1);
    vector<bool>data(n,false);
    data[0]=true;
    for(ll i=0;i<m;i++){
        if(data[x[i]]){
            data[y[i]]=true;
        }
        num[x[i]]--;
        num[y[i]]++;
        if(num[x[i]]==0){
            data[x[i]]=false;
        }
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        if(data[i]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5568
#include<stdio.h>

int main()
{
 int n;
 int a;
 int b;
 int c;
 scanf("%d",&n);
 if(n==1)
 {
  printf("Hello World\n");
 }else{
  scanf("%d %d",&a,&b);
  c=a+b;
  printf("%d\n",c);
 }
 return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int n,mn=INT_MAX,mx=0;
    cin>>n;
     while(n--){
        int a;
        cin>>a;
        mn=min(mn,a);
        mx=max(mx,a);
     }
     cout<<mx-mn<<endl;

    return 0;
}


Measured memory_bytes: 3640
N = int(input())
W = [input() for _ in range(N)]

judge0 = 1
judge1 = 1

if len(set(W)) < len(W):
    judge0 = 0
    
W = list(map(list, W))
    
for n in range(N-1):
    if W[n][-1] != W[n+1][0]:
        judge1 = 0
        break

if judge0 == 1 and judge1 == 1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
N=int(input())
AL=list(map(int, input().split()))
L=[]
for i in range(N-1,-1,-1):
    s=AL[i]
    for j in range((i+1)*2-1,N,i+1):
        s^=AL[j]
    AL[i]=s
    if AL[i]==1:
        L.append(i+1)
print(len(L))
if L:
    print(*L)



Measured memory_bytes: 65244
import java.util.Scanner;

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

        int max = 0;
        int cnt = 0;

        for(int i=0; i<N; i++){
            int tmp = scanner.nextInt();
            if(max <= tmp){
                cnt++;
                max = tmp;
            }
        }

        System.out.println(cnt);

    }
}


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

int main()
{
	string s,t;
	cin>>s>>t;
	int n=s.length();
	int m=t.length();
	vector<vector<int> > dp(n+1,vector<int> (m+1,0));
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(i==0 ||j==0)
			{
				dp[i][j]=0;
			}
			else if(s[i-1]==t[j-1])
			{
				dp[i][j]=1+dp[i-1][j-1];
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	//cout<<dp[n][m]<<" ";
	string ans="";
	int i=n,j=m;
	while(i>0 && j>0)
	{
		if(s[i-1]==t[j-1])
		{
			ans=s[i-1]+ans;
			i--;j--;
		}
		else
		{
			if(dp[i-1][j]>dp[i][j-1])
			{
				i--;
			}
			else
			{
				j--;
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 35584
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, X, Y = iim()
    ans = [N-i-1 for i in range(N-1)]
    X1, Y1 = X-1, Y -1

    xy2 = (X+Y)  // 2
    for i in range(0, xy2+1):
        x1 = X1 - i
        if x1 < 0: x1 = -x1
        for j in range(xy2, N):
            d1 = j - i - 1
            y1 = Y1-j
            if y1 < 0: y1 = -y1
            d2 = x1 + y1
            if d1 > d2:
                #print((i+1, j+1), d1+1, d2+1, x1, y1)
                ans[d1] -= 1
                ans[d2] += 1

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3444
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    string s;
    cin>>s;
    long long int  len = s.length();
    long long int a[26]={0};
    for(int i=0;i<s.length();i++)
        a[s[i]-'a']++;
    long long int ans = len*(len-1)/2;
    for(long long int i=0;i<26;i++)
        ans -= ((a[i]*(a[i]-1))/2);
    cout<<ans+1;
    return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (size_t i = 0; i < size_t(n); i++)
#define forn1(i,n) for (size_t i = 1; i <= size_t(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }

int n,m;
string s;

int main()
{
  fastio();

  cin >> n >> m >> s;

  vi next(n+1);
  int cur = n+1;
  for (int i = n; i >= 0; i--) {
    if (s[i] == '0') cur = i;
    next[i] = cur;
  }

  vi ans;
  int i = n;
  while (true) {
    int j = max(0, i - m);
    if (i == next[j]) {
      cout << -1 << endl;
      return 0;
    }
    ans.push_back(i - next[j]);
    i = next[j];
    if (i == 0) break;
  }

  for (int i = ans.size() - 1; i >= 0; i--)
    cout << ans[i] << ' ';
  cout << endl;


  return 0;
}


Measured memory_bytes: 1480
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;


public class Main {
	static int N;
	static int[] S, T;
			
	static private void solve()
	{
		int[] train = new int[24*60*60];
		
		for (int i = 0; i < 24*60*60; i++) train[i] = 0;
		for (int i = 0; i < N; i++) {
			train[S[i]]++;
			train[T[i]]--;
		}
		for (int i = 1; i < 24*60*60; i++) train[i] += train[i-1];
		
		int max = 0;
		for (int i = 0; i < 24*60*60; i++)
		{
			max = Math.max(max, train[i]);
		}
		
		System.out.println(max);
	}
	
	static public void main(String[] args)
	{
		Scanner sca = new Scanner(System.in);
		
		while(true)
		{
			N = sca.nextInt();
			if(N == 0) break;
			
			S = new int[N];
			T = new int[N];
			for (int i = 0; i < N; i++) {
				String str;
				int h, m, s;
				
				str = sca.next();
				h = (str.charAt(0) - '0') * 10 + (str.charAt(1) - '0');
				m = (str.charAt(3) - '0') * 10 + (str.charAt(4) - '0');
				s = (str.charAt(6) - '0') * 10 + (str.charAt(7) - '0');
				S[i] = h * 60 * 60 + m * 60 + s;
				
				str = sca.next();
				h = (str.charAt(0) - '0') * 10 + (str.charAt(1) - '0');
				m = (str.charAt(3) - '0') * 10 + (str.charAt(4) - '0');
				s = (str.charAt(6) - '0') * 10 + (str.charAt(7) - '0');
				T[i] = h * 60 * 60 + m * 60 + s;
			}
			
			solve();
		}
	}
}

Measured memory_bytes: 70772
#include <iostream>

using namespace std;

int main()
{
  int h, n;
  cin >> h >> n;
  for (int i = 0; i < n; i++)
  {
    int att;
    cin >> att;
    h -= att;
    if (h <= 0)
    {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

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

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int main() {
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d);
    for (int i = 0; i < d; ++i) {
        cin >> p[i] >> c[i];
    }

    int ans = inf;
    int mask = (1 << d) - 1;
    for (int i = 0; i < (mask + 1); ++i) {
        int score = 0;
        int cnt = 0;
        for (int j = 0; j < d; ++j) {
            if (i >> j & 1) {
                score += (j + 1) * 100 * p[j] + c[j];
                cnt += p[j];
            }
        }

        if (score >= g) {
            ans = min(ans, cnt);
            continue;
        }

        int k = i ^ mask;
        for (int j = d - 1; j >= 0; --j) {
            int _score = score;
            int _cnt = cnt;
            if (k >> j & 1) {
                for (int l = 0; l < p[j] - 1; ++l) {
                    _score += (j + 1) * 100;
                    ++_cnt;

                    if (_score >= g)
                        break;
                }

                if (_score >= g) {
                    ans = min(ans, _cnt);
                }
                break;
            }
        }
    }

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

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

struct Card{
	char c;
	int a;
};

bool compare(Card i,Card j){
	return (i.a<j.a);
}

int partition(Card *A,int p,int r){
  Card x=A[r];
  int i=p-1;

  for(int j=p;j<=r-1;j++){
    if(A[j].a<=x.a){
      i++;
      swap(A[i],A[j]);
    }
  }
  swap(A[i+1],A[r]);
  return i+1;

}

void quicksort(Card* A,int p,int r){
	int q;
	if(p<r){
		q=partition(A,p,r);
		quicksort(A,p,q-1);
	    quicksort(A,q+1,r);
	}
}


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

	Card m[n];
	Card l[n];

	
	for(int i=0;i<n;i++){
		cin>>m[i].c>>m[i].a;
		l[i]=m[i];
	}

	quicksort(m,0,n-1);
	stable_sort(l,l+n,compare);

	int judge=1;
	int j=0;
	while(judge&&j<n){
		if(m[j].c!=l[j].c){
			judge=0;
		}
		j++;
	}

	if(judge){
		cout<<"Stable"<<endl;
	}else{
		cout<<"Not stable"<<endl;
	}

	for(int i=0;i<n;i++){
		cout<<m[i].c<<' '<<m[i].a<<endl;
	}

	return 0;

}


Measured memory_bytes: 4632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18,MOD = 1e9 + 7;
const int INT_INF = 1e9,INT_MOD=1e9+7;
#define rep(i, N) for(int i = 0; i < N; i++)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
signed main(){
    ll h;cin>>h;
    ll ans=1,count=2;
    for(;h>1;count*=2){
        ans+=count;
        h/=2;
    }
    //ans+=count/2;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;
int main(){
	int n,k;
	long double ans=0;

	scanf("%d %d",&n,&k);

	for(int i=1;i<=n;i++){
		int coinN=0;
		int point=i;
		//printf("saikoro:%d\n",i);
		while(point<k){
			coinN++;
			point*=2;
			//printf("point:%d\n",point);
		}
		//printf("%lf",(1.0/(long double)n)*pow(1.0/2.0,(long double)coinN));
		//cout<<endl;
		ans+=(long double)((long double)1.0/(long double)n)*pow((long double)(1.0/2.0),(long double)coinN);
	}
	printf("%.9Lf",ans);

	return 0;
}

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

int main(){
  int h1,m1,h2,m2,k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
 
  int d=(h2-h1)*60+m2-m1;
  cout << d-k << endl;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int h = sc.nextInt();
        int ans = (a + b) * h / 2;
        System.out.println(ans);
    }
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;  // or pb_ds;

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#ifndef DEBUG
#define endl "\n"
#endif
#define fff ff
#define sss ss.ff
#define ttt ss.ss
#define INF (1 << 30)
#define LLF (1ll << 60)
#define PRIME (1000000007)
#define FASTIO std::ios::sync_with_stdio(false)
#ifdef DEBUG
#define debug(x) cerr << #x << " = " << x << endl
#else
#define debug(x)
#endif
#define rep(i, begin, end)                            \
  for (__typeof(end) i = (begin) - ((begin) > (end)); \
       i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define FILE_INPUT                  \
  freopen("input.txt", "r", stdin); \
  freopen("output.txt", "w", stdout)

#define all(x) x.begin(), x.end()

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<string> vs;

template <typename T, typename B = null_type>
using oset =
    tree<T, B, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order / order_of_key

const ld eps = 1e-12;

/*-----------------END TEMPLATE-----------------*/

int(((((((((((((((main)))))))))))))))() {
  FASTIO;
  ll k;
  cin >> k;
  vector<ll> numbers;
  if (k <= 10) {
    cout << k << endl;
    exit(0);
  }
  rep(i, 1, 10) numbers.pb(i);
  int i = 0;
  while (numbers.size() < k) {
    ll cur = numbers[i];
    ll last = cur % 10;
    ll placeholder = cur * 10;
    if (last > 0) {
      numbers.pb(placeholder + last - 1);
    }
    numbers.pb(placeholder + last);
    if (last < 9) {
      numbers.pb(placeholder + last + 1);
    }
    i++;
  }

  cout << numbers[k - 1] << endl;
}

/*

0 1 2 3 4 5 6
      B B C C

1 2 3 4 5
    A A A
B B B
      C C

*/

Measured memory_bytes: 1400
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <queue>
using namespace std;

#define N 3
#define N2 9

struct Puzzle {
	int f[N2];
	int space;
	string path;

	bool operator < (const Puzzle &p ) const{
		for(int i=0;i<N2;i++){
			if(f[i] == p.f[i]) continue;
			return f[i] > p.f[i];
		}
		return false;
	}
};

static const int dx[4] = {-1,0,1,0};
static const int dy[4] = {0,-1,0,1};
static const int dir[4] = {'u','l','d','r'};

bool isTarget(Puzzle p){
	for(int i = 0;i<N2;i++)
	if(p.f[i] != (i+1) ) return false;
	return true;
}

string bfs(Puzzle s) {
	queue<Puzzle> Q;
	map<Puzzle,bool> V;
	Puzzle u, v;
	s.path = "";
	Q.push(s);
	V[s] = true;
	
	while( !Q.empty() ){
		u = Q.front();Q.pop();
		if( isTarget(u) )return u.path;
		int sx = u.space / N;
		int sy = u.space % N;
		for(int r = 0; r < 4 ; r++){
			int tx = sx + dx[r];
			int ty = sy + dy[r];
			if( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
			v = u;
			swap(v.f[u.space],v.f[tx * N + ty]);
			v.space = tx * N + ty;
			if( !V[v] ){
				V[v] = true;
				v.path += dir[r];
				Q.push(v);
			}
		}
	}
	
	return "unsolvable";
}

int main(){
	Puzzle in;
	
	for(int i = 0;i < N2; i++){
		cin >> in.f[i];
		if(in.f[i] == 0 ){
			in.f[i] = N2; // set space
			in.space = i;
		}
	}
	string ans = bfs(in);
	cout << ans.size() <<  endl;
	
	return 0;
}



Measured memory_bytes: 30504
#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.at(i);

  long X = 0, index;
  for (int i = 0; i < N; i++) if (A.at(i) > X) X = A.at(i), index = i;

  long Y, mi = 2e18;
  for (int i = 0; i < N; i++) {
    if (i == index) continue;
    int tmp = abs(A.at(i) * 2 - X);
    if (tmp < mi) mi = tmp, Y = A.at(i);
  }

  cout << X << " " << Y << "\n";
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

int main(){
	char x[1001];
	int num;
	bool f=0;
	while (1){
		scanf("%s", x);
		if (x[0]=='0') break;
		int sum = 0;
		for (int i = 0; i < strlen(x); i++){
			num = x[i] - '0';
			sum += num;
		}
		printf("%d\n",sum);
	}
}

Measured memory_bytes: 964
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, x = 0;
  cin >> N;
  int M = N;
  while (M > 0) {
    x += M % 10;
    M /= 10;
  }
  //cout << x <<endl;
  if (N % x) {
    cout << "No" <<endl;
  }
  else {
    cout << "Yes" <<endl;
  }
}

Measured memory_bytes: 3596
def solve(S):
    N = len(S) - 1
    ret = 0
    used_equation = set()
    for i in range(pow(2, N)):
        tmp_equation = ''
        last_j = -1
        for j in range(N):
            if i >> j & 1:
                tmp_equation = tmp_equation + '+' + S[last_j + 1: j + 1]
                last_j = j
        if last_j < N:
            tmp_equation = tmp_equation + '+' + S[last_j + 1:]
        ret += eval(tmp_equation) if tmp_equation not in used_equation else 0
        used_equation.add(tmp_equation)
    print(ret)

if __name__ == "__main__":
    S = input()
    solve(S)

Measured memory_bytes: 39152
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long h;
    cin >> n >> h;
    long a[n];
    long b[n];
    for(int i=0;i<n;i++)cin >> a[i] >> b[i];
    sort(a,a+n,greater<long>());
    sort(b,b+n,greater<long>());
    
    int i = 0;
    long ans = 0;
    while(h>0){
        if(i<n && b[i] > a[0]){
            ans++;
            h-= b[i];
            i++;
        }else{
            ans += (h+a[0]-1)/a[0];
            h=0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define MOD 1000000007
#define endL << '\n'
#define ii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define endL << '\n'
#define vii vector<ii>
#define pb push_back

/*
ll powmod(ll x, ll y, ll mod){
	ll res = 1;
	while (y > 0){
		if (y%2) res = (res*x) % mod;
		x = (x*x) % mod;
		y /= 2;
	}
	return res;
}
*/

/*const int N = 1000000;
int lp[N+1];
vector<ll> pr;

void sieve(){
	for (int i=2; i<=N; ++i) {
	    if (lp[i] == 0) {
	        lp[i] = i;
	        pr.push_back (i);
	    }
	    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
	        lp[i * pr[j]] = pr[j];
	}
}*/

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1; //cin >> t;
	while(t--){
		int n, m; cin >> n >> m;
		vector<string> s(n);
		for (int i = 0; i < n; i++) cin >> s[i];

		vvll dp(n, vll(m, 0));
		dp[0][0] = 1;
		for (int j = 1; j < m; j++){
			if (s[0][j] == '#') dp[0][j] = 0;
			else dp[0][j] = dp[0][j-1];
		}
		for (int i = 1; i < n; i++){
			if (s[i][0] == '#') dp[i][0] = 0;
			else dp[i][0] = dp[i-1][0];
		}
		
		for (int i = 1; i < n; i++){
			for (int j = 1; j < m; j++){
				if (s[i][j] == '#') dp[i][j] = 0;
				else dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
				//cout << dp[i][j] << " ";
			}
			//cout endL;
		}

		cout << dp[n-1][m-1];
		
	}
}

Measured memory_bytes: 9216
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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_MAX	2,147,483,647 = 2*1.0e9

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

  int ans = max(max((A + B), (A - B)) , (A * B));
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */
ll bpow(ll a , ll b){
  if (b == 0) return 1;
  ll ret;
  if (b%2 == 0){
    ll  t = bpow(a, b/2);
    ret = t*t;
  }else{
    ll t = bpow(a, (b-1)/2);
    ret = a*t*t;
  }
  return ret;
}

int main() {
  int N, P;
  cin >> N >> P;
  int odd = 0;
  REP(i, N){
    int a;  cin >> a;
    if(a%2==1) odd++;
  }
  int even = N - odd;
  ll ans;
  if(odd == 0 && P == 1 ){
    ans = 0;
  }else if (odd == 0){
    ans = bpow(2, N);
  }else{
    ans = bpow(2, N-1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>

#define len(x) (int)((x).size())
#define endl '\n'
#define x first
#define y second
#define int long long
#define all(a) (a).begin(), (a).end()
#ifdef LOCAL
	#define dbg(x) cout << #x << " = " << x << endl;
#else 
	#define dbg(x)
#endif 

using namespace std;

void solve(); signed main() {
#ifdef LOCAL
    freopen("file1.txt", "r", stdin);                                       
    freopen("file2.txt", "w", stderr);
#endif
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(6);
    solve();
}

const int INF = 1e9, MAXN = 1e5 + 10;                 	

void solve() {                         
	int a, b;
	cin >> a >> b;
cout << (b - 1 + a - 2) / (a - 1) << endl;
	

}	


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

typedef long long LL;

const int MaxN=1e5+5;

int N,Tot;
LL Ans;
int Head[MaxN],Nxt[MaxN<<1],To[MaxN<<1],Weight[MaxN<<1];
int Size[MaxN],F[MaxN],W[MaxN];

void Add_Edge(int u,int v,int w){
	Nxt[++Tot]=Head[u];
	To[Tot]=v,Weight[Tot]=w;
	Head[u]=Tot;
}

void DFS(int u,int fa,int w){
	int i,v;
	Size[u]=1,W[u]=w;
	for(i=Head[u];i;i=Nxt[i])
		if((v=To[i])^fa){
			DFS(v,u,Weight[i]);
			Size[u]+=Size[v];
			F[u]=max(F[u],Size[v]);
		}
	F[u]=max(F[u],N-Size[u]);
	if(w)
		Ans+=2llu*w*min(Size[u],N-Size[u]);
}

int main(){
	int i,j,u,v,w,mn=1<<30;
	scanf("%d",&N);
	for(i=1;i<N;i++){
		scanf("%d%d%d",&u,&v,&w);
		Add_Edge(u,v,w);
		Add_Edge(v,u,w);
	}
	DFS(1,0,0);
	for(i=1;i<=N;i++)
		if(Size[i]<<1==N){
			printf("%lld\n",Ans-W[i]);
			return 0;
		}
	for(i=1;i<=N;i++)
		if(F[i]<=N>>1)
			for(j=Head[i];j;j=Nxt[j])
				mn=min(mn,Weight[j]);
	printf("%lld\n",Ans-mn);
	return 0;
}

Measured memory_bytes: 9472
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DIM 100007
#define INF 1000000009.0
#define X 500007
#define epc 0.0000001
#define pi 3.14159265358979323846
#define MAX 25
#define MODULO 10009
const long double gr=(1+sqrt(5))/2;

typedef int I;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef pair<I,I> pII;
typedef pair<ll,ll> pllll;
typedef pair<ld,ld> pldld;

typedef vector<I> vI;
typedef vector<ll> vll;
typedef vector<pllll> vpllll;

typedef char cr;
typedef string str;

typedef tree<
I,
null_type,
less<I>,
rb_tree_tag,
tree_order_statistics_node_update> mset;

ll n,k,h[DIM],d[DIM],mind,minj;

int main()
{
    //freopen("suffarray.in", "r", stdin);
    //freopen("suffarray.out", "w", stdout);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //cout<<"ops"<<endl;

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

    //ll x1,y1,xs,ys,y1,y2,x3,x4,y3,y4;

    cin>>n>>k;
    for(int i=1;i<=n;i++){
     cin>>h[i];
     if(i>1){
      mind=INF;
      minj=i-k;
      if(minj<1)minj=1;
      for(int j=minj;j<i;j++)if((abs(h[i]-h[j])+d[j])<mind)mind=abs(h[i]-h[j])+d[j];
      d[i]=mind;
     }
    }
    cout<<d[n]<<endl;
}


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

using namespace std ;

int main(void){
    int d[100000],n;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> d[i];
    }
    sort(d, d+n);

    cout << abs(d[n/2 -1] -  d[n/2]) << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
long long a[100010];
long long fac[200020], finv[200020], inv[200020];
void init() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < 200020; i++) {
		fac[i] = fac[i - 1] * i % 1000000007;
		inv[i] = 1000000007 - inv[1000000007 % i] * (1000000007 / i) % 1000000007;
		finv[i] = finv[i - 1] * inv[i] % 1000000007;
	}
}
long long comb(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % 1000000007) % 1000000007;
}
int main() {
	long long n, k;
	cin >> n >> k;
	for (long long i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	init();
	long long ans = 0;
	for (long long i = 0; i < n; i++) {
		ans = (ans - comb(n - i - 1, k - 1) * a[i]) % 1000000007;
		ans = (ans + comb(i, k - 1) * a[i]) % 1000000007;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5760
import decimal
decimal.getcontext().prec = 100
def sum1(pre,l,r):
    l=max(l,0)
    if(l==0):
        return pre[r]
    return pre[r] - pre[l - 1]

x=int(raw_input())
arr=map(int,raw_input().split())
b=[arr[0]-1]
mi=b[0]
for i in range(1,len(arr)):
    if(arr[i]-1>=mi):
        b.append(arr[i]-1)
    else:
        b.append(arr[i])
    mi=b[-1]
if b==sorted(b):
    print 'Yes'
else:
    print 'No'            


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

#define rep(i, j, n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
#define Puts(x) puts(x? "Yes":"No")
const int mod = 998244353;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(int n, int m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(int n, int m) {return (n / gcd(n, m) * m);}
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

vt<i64> f;

i64 power(i64 x, i64 n) {
  i64 ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return ret;
}

i64 comb(i64 n, i64 k) {
  i64 res = ((f[n] * power(f[k], mod - 2)) % mod) * power(f[n - k], mod - 2);
  res %= mod;
  return res;
}

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

  i64 n, a, b, k;
  cin >> n >> a >> b >> k;

  f.resize(n + 1);
  f[0] = 1;
  for(i64 i = 1; i <= n; ++i) {
    f[i] = f[i - 1] * i;
    f[i] %= mod;
  }

  i64 ans = 0;
  for(i64 i = 0; i <= n; ++i) {
    if(k < a * i) continue;

    if((k - a * i) % b == 0) {
      i64 j = (k - a * i) / b;
      if(j > n) continue;

      ans += comb(n, i) * comb(n, j);
      ans %= mod;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		String ansa ="";
		String ansb ="";
		int ia = Integer.parseInt(a);
		int ib = Integer.parseInt(b);
		for(int i = 0;i<ia;i++){
			ansb+=b;
		}
		for(int i = 0;i<ib;i++){
			ansa+=a;
		}
		if(ia<=ib){
			System.out.println(ansa);
		}else{
			System.out.println(ansb);
		}
	}
}

Measured memory_bytes: 21972
#include<stdio.h>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
long long n,k,i,a[500005],mi,x;
int main()
{
    scanf("%lld%lld",&k,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[n+i]=a[i]+k;
    }
    sort(a+1,a+n*2+1);
    mi=k;
    for(i=n;i<2*n;i++)
    {
        x=a[i]-a[i-n+1];
        if(x<mi)mi=x;
    }
    printf("%lld\n",mi);
}

Measured memory_bytes: 3328
class UnionFind:
    def __init__(self, n: int):
        self.__n = n
        self.__par = list(range(self.__n))
        self.__size = [1 for _ in range(self.__n)]

    def root(self, x: int) -> int:
        if self.__par[x] == x:
            return x
        self.__par[x] = self.root(self.__par[x])
        return self.__par[x]

    def merge(self, x: int, y: int) -> bool:
        rx, ry = self.root(x), self.root(y)
        if rx == ry: return False

        if self.__size[rx] < self.__size[ry]:
            rx, ry = ry, rx

        self.__size[rx] += self.__size[ry]
        self.__par[ry] = rx
        return True

    def check(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        return self.__size[self.root(x)]


from collections import defaultdict

N, K, L = map(int, input().split())
rail_uf = UnionFind(N + 1)
road_uf = UnionFind(N + 1)

for _ in range(K):
    p, q = map(int, input().split())
    rail_uf.merge(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    road_uf.merge(r, s)

d = defaultdict(int)
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    d[tup] += 1

ans = []
for i in range(1, N + 1):
    tup = (rail_uf.root(i), road_uf.root(i))
    ans.append(str(d[tup]))

print(" ".join(ans))


Measured memory_bytes: 64256
import itertools
N,M = map(int,input().split())
tmp = [0 for i in range(N)]
S = []
for _ in range(M):
    k = list(map(int,input().split()))
    s = list(tmp)
    for i in k[1:]:
        s[i-1] = 1
    S.append(s)
P = list(map(int,input().split()))
#print(S)
x = [0,1]
Y = list(itertools.product(x,repeat=N))
#print(Y)
ans = 0
for i in Y:
    on = []
    for j in range(M):
        count = 0 
        for n in range(N):
            if i[n] == 1 and S[j][n] == 1:
                count += 1
        if count % 2 == P[j]:
            on.append(1)
        else:
            on.append(0)
    #print(on)
    if 0 not in on:
        ans += 1
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  int K[N];
  vector <int> Marray(M, 0);
  for(int i = 0; i < N; i++){
    cin >> K[i];
    int A[K[i]];
    for(int j = 0; j < K[i]; j++){
      cin >> A[j];
      Marray[A[j]-1]++;
    }
  }

  int count = 0;
  for(int i = 0; i < M; i++){
    if(Marray[i] == N) count++;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <map>

const int64_t MOD=1e9+7;
const int64_t INV2=5e8+4;

int vis[100005];

int next[100005];
std::vector<int> prev[100005];
int buddy[100005];
int root[100005];
bool cycle[100005];

int64_t inv[100005];

void fail(){
  printf("0\n");
  exit(0);
}

void dfs_root(int node){
  root[node]=node;
  if(!root[next[node]]) dfs_root(next[node]);
  root[node]=root[next[node]];
}

int main(){
  int N;
  scanf("%d",&N);
  inv[1]=1;
  for(int i=2;i<=N;i++){
    inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
  }
  for(int i=1;i<=N;i++){
    scanf("%d",&next[i]);
    prev[next[i]].push_back(i);
  }
  for(int i=1;i<=N;i++){
    if(prev[i].size()>2) fail();
  }
  for(int i=1;i<=N;i++){
    int layer[4];
    int layer_cnt=0;
    for(int x:prev[i]) layer[layer_cnt++]=x;
    while(layer_cnt==2){
      int a=layer[0],b=layer[1];
      //printf("LAYER %d:%d\n",a,b);
      if(buddy[a]||buddy[b]){
	assert(buddy[a]==b);
	assert(buddy[b]==a);
	break;
      }
      buddy[a]=b,buddy[b]=a;
      
      layer_cnt=0;
      for(int x:prev[a]) layer[layer_cnt++]=x;
      for(int x:prev[b]) layer[layer_cnt++]=x;
    }
    if(layer_cnt>2) fail();
  }
  std::map<int,int> pures;
  for(int i=1;i<=N;i++){
    if(!root[i]) dfs_root(i);
  }
  for(int i=1;i<=N;i++){
    if(root[i]==i){
      bool ispure=true;
      int length=0;
      int j=i;
      do{
	if(prev[j].size()>1) ispure=false;
	cycle[j]=true;
	length++;
	j=next[j];
      }while(j!=i);
      
      if(ispure){
	pures[length]++;
      }
    }
  }
  int64_t ans=1;
  for(int i=1;i<=N;i++){
    if(cycle[i]&&buddy[next[i]]&&!buddy[i]){
      ans=ans*2%MOD;
    }
  }
  for(auto pair:pures){
    int64_t len=pair.first,cnt=pair.second;
    //printf("PURE %ld x%ld\n",len,cnt);
    int64_t ac=1;
    if(len%2==1&&len>1){
      for(int i=0;i<cnt;i++){
	ac=ac*2%MOD;
      }
    }
    int64_t sum=ac;
    //printf(" %ld",ac);
    int pairs=0;
    while(cnt>1){
      ac=(ac*len)%MOD*((cnt*(cnt-1)/2)%MOD)%MOD*inv[++pairs]%MOD;
      cnt-=2;
      if(len%2==1&&len>1){
	ac=ac*INV2%MOD*INV2%MOD;
      }
      sum=(sum+ac)%MOD;
      //printf("+%ld",ac);
    }
    //printf(" => %ld\n",sum);
    ans=ans*sum%MOD;
  }
  printf("%ld\n",ans);
  return 0;
}


Measured memory_bytes: 9088
n, k = map(int, input().split())
an = list(map(int, input().split()))
for i in range(n):
    an[i] -= 1
    
import math
dv = []
dv.append(an)
K = k
N = n
for _ in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)

for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
# N 回目を 2 ^ t で表すためにビット演算を用いる
# a : dv の何行目を用いるかを格納
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
        
print(now + 1)

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

int main(){
  ll n,k;
  cin >> n >> k;
  int a[n+1];
  a[0] = 0;
  rep(i,1,n+1) cin >> a[i];

  vector<int> r;
  set<int> st;
  r.push_back(0);
  st.insert(1);
  int next = 1;
  int count = 0;
  while(1){
    int tmp = next;
    next = a[tmp];
    r.push_back(next);
    st.insert(next);
    count++;
    if(count == k){
      cout << next << endl;
      return 0;
    }
    if(st.size()<count) break;
  }

  int p;
  rep(i,0,r.size()){
    if(r[i] == next){
      p = i;
      break;
    }
  }

  cout << r[p + ((k-count)%(count-p))] << endl;

  return 0;
}

Measured memory_bytes: 12080