akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define len(s) s.length()
#define forp(i,a,b) for( i=a;i<=b;i++)
#define FOR(tt,a,b) for(int tt=a;tt<=b;tt++)
#define rep(i,n)    for( i=0;i<n;i++)
#define ren(i,n)    for( i=n-1;i>=0;i--)
#define forn(i,a,b) for( i=a;i>=b;i--)
#define all(v) v.begin(),v.end()
#define b(v) v.begin()
#define e(v) v.end()
#define mem(n,m) memset(n,m,sizeof(n))
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vii vector<int>
#define vll vector<long long>
#define gl(cin,s)  getline(cin,s);
#define bitc(n) __builtin_popcountll(n)
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 

#define boost ios_base::sync_with_stdio(0)
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define SIZE 100001

typedef long long  ll;
typedef unsigned long long ull;
typedef long double  ldo;
typedef double  db ;
using namespace std;
int main()
{  	
	/* #ifndef ONLINE_JUDGE
	freopen(fi, "r", stdin);
	#endif */
	//freopen("route.in","r",stdin);
	//freopen("route.out","w",stdout);
	//cin.ignore();
	//cin.clear();
	boost;
	//cin.tie(0);
	//cout<<"Case #"<<tt<<": ";
	int i,n,x;
	int a[SIZE];
	cin>>n>>x;
	forp(i,1,n){
		cin>>a[i];
	}
	ll ans=0;
	forp(i,2,n){
		if(a[i]+a[i-1]>x){
			if(a[i-1]>x){
				ans += a[i];
				a[i]=0;
				ans += a[i-1]-x;
				a[i-1]=x;
			}
			else{
				ll temp=x-a[i-1];
				ans += a[i]-temp;
				a[i]=temp;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
    int H,W;
    cin >> H >> W;
    while(H!=0 && W!=0){
        string s1,s2; s1=""; s2="";
        for(int i=0;i<W;i++){
            if(i%2==0){
                s1+="#";s2+=".";
            }else if(i%2==1){
                s1+=".";s2+="#";
            }
        }
        for(int i=0;i<H;i++){
            if(i%2==0){
                cout << s1 << endl;
            }else if(i%2==1){
                cout << s2 << endl;
            }
        }
        cout << endl;

        cin >> H >> W;
    }
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
struct Fast {Fast(){std::cin.tie(0);std::ios::sync_with_stdio(false);}} fast;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define repR(i, n) for(ll i = n; i >= 0; i--)
#define For(i, m, n) for(ll i = m; i < n; i++)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) v.begin(), v.end()

using namespace std;

inline ll gcd(ll a, ll b){
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

inline ll lcm(ll x, ll y)
{
    if(x == 0 || y == 0) {
        return -1;
    }
    
    return (x * y / gcd(x, y));
}

inline ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

inline ll nCr(ll n, ll r) {
    if ( r * 2 > n ) r = n - r;
    ll dividend = 1;
    ll divisor  = 1;
    for ( ll i = 1; i <= r; ++i ) {
        dividend *= (n-i+1);
        divisor  *= i;
    }
    return dividend / divisor;
}

inline vector<pair<ll, int>>factorize(ll n){
    vector<pair<ll, int>> res;
    for(ll i = 2; i * i <= n; ++i){
        if(n % i) continue;
        res.emplace_back(i, 0);
        while(n % i == 0){
            n /= i;
            res.back().second++;
        }
    }
    if(n != 1) res.emplace_back(n, 1);
    return res;
}

inline bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

ll mod = 1e9+7;

int main(){
    ll res = 0;
    ll n;
    cin >> n;
    string s;
    cin >> s;

    if(n % 2 != 0){
        cout << "No" << endl;
        return 0;
    }
    ll mid = n/2;
    
    rep(i, mid){
        if(s[i] != s[i + mid]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()
N = len(S)

for i in range(N // 2):
    if S[i] != S[-1 - i]:
        print("No")
        exit()

for i in range((N - 1) // 4):
    if S[i] != S[(N-1)//2-i-1]:
        print("No")
        exit()

for i in range((N - 1) // 4):
    # print(S[(N+3)//2+i-1])
    if S[(N+3)//2+i-1] != S[-1 - i]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3064
import bisect

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

A.sort()
n = A[-1]
mid = bisect.bisect(A, n/2)

if abs(n/2-A[mid-1]) > abs(n/2-A[mid]):
    print(n, A[mid])
else:
    print(n, A[mid-1])


Measured memory_bytes: 20144
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}

int main()
{
	int n=read(),temp=n,cnt=0;
	while(temp>0)
	{
		cnt+=temp%10;
		temp=temp/10;
	}
	puts(n%cnt?"No":"Yes");
	return 0;
}



Measured memory_bytes: 256
h,w = map(int,input().split())
a = []
for i in range(h):
    ans = str(input())
    a.append((ans))
a_h = []
for i in range(h):
    check_h = False
    for j in range(w):
        if a[i][j] == '#':
            check_h = True
    if check_h:
        a_h.append(a[i])
ans = ['']*len(a_h)
for i in range(w):
    check_w = False
    for j in range(h):
        if a[j][i] == '#':
            check_w = True
    if check_w:
        for k in range(len(a_h)):
            ans[k] += a_h[k][i]
for i in range(len(ans)):
    print(ans[i])

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

int main(){
  string s;
  cin >> s;
  int rem_A, rem_Z;
  
  for (int i=0; i<s.size(); i++){
    if (s.at(i) == 'A'){
      rem_A = i;
      break;
    }
  }
  
  for (int i=s.size()-1; i>0; i--){
    if (s.at(i) == 'Z'){
      rem_Z = i;
      break;
    }
  }
  
  cout << rem_Z - rem_A + 1 << endl;
}

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

using namespace std;

using ll = int_fast64_t;
constexpr ll llmax = INT_FAST64_MAX; // std::numeric_limits<int_fast64_t>::max()
constexpr ll llmin = INT_FAST64_MIN; // std::numeric_limits<int_fast64_t>::min()
using ull = uint_fast64_t;
constexpr ull ullmax = UINT_FAST64_MAX; // std::numeric_limits<uint_fast64_t>::max()

#define FOR(i, b, e) for (int i = (b); i < (e); ++i)
#define RFOR(i, b, e) for (int i = ((e) - 1); (b) <= i; --i)
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define RREP(i, N) for (int i = ((N) - 1); 0 <= i; --i)
#define scanInt(x) int x; scanf("%d", &(x)); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &(x)); getchar();
#define scanVecInt(A, N) vector<int> A(N); REP(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); REP(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    scanInt(M);
    scanVecLLInt(H, N);
    vector<pair<int, int>> AB; AB.reserve(M);
    REP(m, M){
        scanInt(Am); --Am;
        scanInt(Bm); --Bm;
        AB.emplace_back(Am, Bm);
    }
    vector<int> flags(N, 1);
    REP(m, M){
        auto& Ai = AB[m].first;
        auto& Bi = AB[m].second;
        auto& Ha = H[Ai];
        auto& Hb = H[Bi];
        if (Ha <= Hb) flags[Ai] = 0;
        if (Hb <= Ha) flags[Bi] = 0;
    }
    int result = 0;
    REP(n, N){
        if (flags[n]) ++result;
    }
    cout << result << endl;
}


Measured memory_bytes: 5124
#include <iostream>
using ll = long long;
using namespace std;

int main() {
    string s;
    cin >> s;
    int a = 101, b = -1;
    for (int i = 0; i < s.length(); ++i) {
        if(s[i] == 'C') a = min(a, i);
        if(s[i] == 'F') b = max(b, i);
    }

    cout << (a < b ? "Yes" : "No") << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios()                \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0)

const int MOD = 1e9 + 7;

int dp[100010];

signed main()
{
	ios();
	int N;
	int M;
	cin >> N >> M;
	int a[M];
	for (int i = 0; i < M; i++) {
		cin >> a[i];
	}
	dp[0] = 1;
	sort(a,a + M);
	int mi = 0;
	for (int i = 0; i < N; i++) {
		if (i + 1 == a[mi]) {
			mi ++;
			dp[i + 1] = 0;
		} else {
			if(i >= 1) dp[i + 1] = ( dp[i] + dp[i-1]) % MOD;
			else dp[i + 1] = dp[i] % MOD;
		}
	}
	cout << dp[N] << endl;


}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <utility>
#include <string>
#include <cmath>
#include <set>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    int a,b,c;
    int d[10]={};
    cin >> a >> b >> c;
    d[a]++;
    d[b]++;
    d[c]++;
    if(d[5]==2&&d[7]==1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] S = new int[n];
		for (int i = 0; i < n; i++) {
			S[i] = sc.nextInt();
		}
		Arrays.sort(S);
		
		int q = sc.nextInt();
		int[] T = new int[q];
		for (int i = 0; i < q; i++) {
			T[i] = sc.nextInt();
		}
		Arrays.sort(T);
		
		int s = 0;
		int t = 0;
		int count = 0;
		while(s < S.length && t < T.length) {
			if (S[s] == T[t]) {
				count++;
				s++;
				t++;
			} else if(S[s] > T[t]) {
				t++;
			} else {
				s++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 32124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> mp;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,m,c;cin>>n>>m>>c;
    ll b[m];for(ll i=0;i<m;i++)cin>>b[i];
    ll ans=0,x;
    for(ll i=0;i<n;i++){
        ll tot=0;
        for(ll i=0;i<m;i++)cin>>x,tot+=x*b[i];
        tot+=c;
        if(tot>0)ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 256
s = input()
text = []
for i in range(len(s)):
  if s[i] == '0':
    text.append('0')
  elif s[i] =='1':
    text.append('1')
  else:
    if len(text) > 0:
      text.pop(len(text)-1)
result = ''.join(text)
print(result)

Measured memory_bytes: 3060
import Data.List
import Data.Ord
import Data.Char
import Data.Ratio
import Data.Maybe

main = do
  n <- readLn :: IO Int
  let ys = [[y|y<-[x,x-1..1], mod x y==0]|x<-[1,3..n]]
  print $ length $ map head [z|z<-ys, length z==8]

Measured memory_bytes: 3944
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  ll n,i;
  cin >> n >> i;
  cout << n-(i-1)<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
typedef long long ll;
using namespace std;
int main() {
	string s;
	int k;
	cin >> s;
	cin >> k;
	int n = s.size();
	for (int i = 0; i < s.size(); i++) {
      	if(s[i]=='a'){continue;}
		int x = (26 - (s[i] - 'a'));
		if (x <= k) { s[i] = 'a'; k -= x; };
	}
  	for(int i=0; i<s.size(); i++){
      	int x = (26 - (s[i] - 'a'));
		if (x <= k) { s[i] = 'a'; k -= x; };
    }
  	s[n-1]+=(k%26);
	cout << s << endl;
} 

Measured memory_bytes: 512
N, P = map(int, input().split())
S = input()

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  mods = [0] * (N+1)
  for i in range(N-1, -1, -1):
    mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
  c = dict()
  for m in mods:
    c[m] = c.get(m, 0)+1
  for key in c:
    ans += c[key]*(c[key]-1)//2

print(ans)

Measured memory_bytes: 17392
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC096_A();
        }

        static void ABC096_A()
        {
            var ab = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(ab[0] <= ab[1] ? ab[0] : ab[0]-1);
        }
    }
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection) (collection).begin(), (collection).end()  // begin to end
#define each(e, collection) for(auto& e: collection)              // for each
#define rep(i, begin, end) for (ll i = begin; i < end; i++)       // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)      // repeat reverse
#define size(collection) ((ll) (collection).size())               // collection size

#endif

namespace NyaGadget
{
	/**
	@brief 素因数分解ライブラリ
	@note
	 nを素因数分解する。
	 ans[i]がnだったとき、素因数分解して得られた積のなかにn個の素数iが含まれていることを表す。
	 例えばn=12のとき ans = {0, 0, 2, 1, 0, 0, ..., 0}; となるので 12 = 2 * 2 * 3 と分かる。
	**/
	/*
	void PrimeFactorization(ll n, vector<ll>& ans)
	{
		ans.resize(n+2);
		for (ll i = 2; i * i <= n; i++)
		{
			while (n % i == 0)
			{
				ans[i]++;
				n /= i;
			}
		}
		if (n != 1)
			ans[n]++;
	}
	*/
	void PrimeFactorization(ll n, map<ll, ll>& ans)
	{
		for (ll i = 2; i * i <= n; i++)
		{
			while (n % i == 0)
			{
				ans[i]++;
				n /= i;
			}
		}
		if (n != 1)
			ans[n]++;
	}
}

namespace NyaGadgetCpp17
{
	/**
	@brief 最大公約数を計算する関数
	@note
	 aとbの最大公約数を返す
	**/
	long long Gcd(long long a, long long b)
	{
		return b ? Gcd(b, a % b) : a;
	}
	/**
	@brief 最小公倍数を計算する関数
	@note
	 aとbの最小公倍数を返す
	**/
	long long Lcm(long long a, long long b)
	{
		return a / Gcd(a, b) * b;
	}
};

using namespace NyaGadget;

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

//	vector<ll> ans;
//	PrimeFactorization(NyaGadgetCpp17::Gcd(a, b), ans);

	map<ll, ll> ans;
	PrimeFactorization(NyaGadgetCpp17::Gcd(a, b), ans);

	cout << size(ans) + 1;
	return 0;
}



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

int mod = 1000000007;

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B + C || B == A + C || C == A + B)
        cout << "Yes";
    else
        cout << "No";
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define mod 1000000007;

int main (void) {
	int n,a,b;
	cin >> n;
	if(n==1){
		cout << "Hello World" << endl;
		return 0;
	}
	cin >> a >> b;
	cout << a+b << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

d = [[False for i in range(N)] for i in range(N)]
visited = [False] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = True
    d[b][a] = True

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    ret = 0
    visited[now] = True

    for i in range(N):
        if d[now][i]:
            ret += dfs(i, depth + 1)
    
    visited[now] = False

    return ret

print(dfs(0,0))

Measured memory_bytes: 3064
#include <stdio.h>

int main(void) {
	int a,b,i,j;

	while(scanf("%d %d",&a,&b)!=EOF)
	{
			i=1;
			j=0;
		while((a+b)/i!=0){
		i=i*10;
		j++;
		}
		printf("%d\n",j);
	}
	return 0;
}

Measured memory_bytes: 600
def main():
    N = int(input())
    a = sorted(map(int, input().split()),reverse=True)      #降順のリスト

    alice = 0
    bob = 0

    for i in range(N):
        if i % 2 == 0:
            alice += a[i]

        else:
            bob += a[i]

    print(alice - bob)


if __name__ == "__main__":
    main()


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

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

int main() {
    int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
};
    int k;
    cin >> k;
    cout << a[k - 1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

char num_to_char(int n) {
    if (n == 1) return 'a';
    else if (n == 2) return 'b';
    else if (n == 3) return 'c';
    else if (n == 4) return 'd';
    else if (n == 5) return 'e';
    else if (n == 6) return 'f';
    else if (n == 7) return 'g';
    else if (n == 8) return 'h';
    else if (n == 9) return 'i';
    else if (n == 10) return 'j';
    else return 'z';
}

vector<string> v;
int N;

void dfs(string s, int i) {
    if (s.size() == N) v.push_back(s);
    else {
        rep1(j,i) {
            dfs(s + num_to_char(j), i);
        }
        dfs(s + num_to_char(i+1), i+1);
    }
}

int main(){ 
    cin >> N;

    dfs("a",1);

    rep(i,v.size()) cout << v[i] << endl;
}


Measured memory_bytes: 7796
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

// vector<vector<int>> data(3, vector<int>(4));

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

  string s, t;
  cin >> s >> t;

  ll min = INF;

  ll buf = 0;

  rep(i, s.size() - t.size()+1) {
    buf = 0;
    rep(k, t.size()) {
      if (t[k] != s[k + i]) {
        buf++;
      }
    }
    min = fmin(min, buf);
  }

  if(min == INF){

  }

  cout << min;

  return 0;
}

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

using namespace std;

const int N = 100005;
const int mod = 1e9+7;
int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}
int mul(int a, int b) {
	return int(1LL * a * b % mod);
}
int fexp(int b, int e = mod - 2) {
	int ans = 1;
	while(e) {
		if(e & 1) ans = mul(ans, b);
		b = mul(b, b);
		e /= 2;
	}
	return ans;
}
int fat[N], ifat[N];
int C(int n, int k) {
	if(n < k) return 0;
	return mul(mul(fat[n], ifat[k]), ifat[n - k]);
}
int n, k;

vector<int> a;

int main() {
	fat[0] = 1;
	for(int i = 1; i < N; i++) fat[i] = mul(i, fat[i - 1]);
	ifat[N - 1] = fexp(fat[N - 1]);
	for(int i = N - 2; i >= 0; i--) {
		ifat[i] = mul(i + 1, ifat[i + 1]);
	}

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

	a.resize(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	if(k == 1) return printf("0\n"), 0;
	sort(a.begin(), a.end());
	for(int &x : a) {
		x %= mod;
		if(x < 0) x += mod;
	}

	int ans = 0;

	int fac = 0;
	for(int i = k - 1; i < n; i++) {
		fac = add(fac, C(i - 1, k - 2));
		ans = add(ans, mul(fac, a[i]));
	}
	fac = 0;
	for(int i = n - k; i >= 0; i--) {
		fac = add(fac, C(n - 1 - i - 1, k - 2));
		ans = add(ans, mod - mul(fac, a[i]));
	}
	printf("%d\n", ans);

}


Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

// ---------------------
// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

// ---------------------
#define INF (1 << 21)
typedef long long ll;

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

  vector<int> V[n];
  int E[n][n];
  int d[n];
  int visited[n];

  REP(x, n) {
    REP(y, n) {
      E[x][y] = INF;
    }
    d[x] = INF;
    visited[x] = 0;
  }

  REP(_, n) {
    int u, k;
    cin >> u >> k;
    REP(__, k) {
      int v, c;
      cin >> v >> c;
      V[u].push_back(v);
      E[u][v] = c;
      // E[v][u] = c;
    }
  }

  d[0] = 0;
  REP(_, n) {
    int minv = -1;
    int mincost = INF;
    REP(v, n) {
      if (!visited[v] && d[v] < mincost) {
        minv = v;
        mincost = d[v];
      }
    }
    visited[minv] = 1;
    for (vector<int>::iterator it = V[minv].begin(); it != V[minv].end(); it++) {
      if (E[minv][*it] < INF && d[minv] + E[minv][*it] < d[*it]) {
        d[*it] = d[minv] + E[minv][*it];
      }
    }
  }

  REP(i, n) {
    cout << i << " " << d[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3212
#include<bits/stdc++.h>
using namespace std;
long long n,l,r,z;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l>>r;
		z+=(r-l)+1;
	}
	cout<<z;
	return 0; 
}

Measured memory_bytes: 256
def judge(N):
    a = []
    n = N
    while n != 0:
        j = n % 10
        if len(a) == 0:
            a += [j]
        elif j != a[0]:
            return False
        n //= 10
    return True

def main():
    n = int(input())
    while not judge(n):
        n += 1

    print(n)

main()


Measured memory_bytes: 2940
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define ll long long

struct Data
{
    ll origin;
    ll modify;
    ll count;

    Data(ll iorigin, ll imodify, ll icount)
    {
        origin = iorigin;
        modify = imodify;
        count = icount;
    }
};

void solve()
{
    auto compare = [](Data a, Data b) {
        return a.modify < b.modify;
    };

    ll N, M;
    cin >> N >> M;
    priority_queue<Data,
                   vector<Data>,
                   decltype(compare)>
        A{compare};
    for (ll i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        A.push(Data(a, a, 0));
    }

    ll money = 0;
    for (ll i = 0; i < M; i++)
    {
        Data top = A.top();
        top.count++;
        top.modify = top.origin / pow(2, top.count);
        A.pop();
        A.push(top);
    }

    while (!A.empty())
    {
        money += A.top().modify;
        A.pop();
    }

    cout << money << endl;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 4980
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi a(n),b(n);
    rep(i,n) cin >> a[i] >> b[i];
    sort(all(a));
    sort(all(b));
    if(n&1) {
        cout << b[n/2]-a[n/2]+1 << endl;
    } else {
        cout << (b[n/2]+b[n/2-1])-(a[n/2]+a[n/2-1])+1 << endl;
    }
}

Measured memory_bytes: 4756
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include <algorithm>
#include<initializer_list>
#include<map>
#include<set>
using namespace std;
int conSize(int n, int m, vector<vector<int>> g, int begin, vector<int> &color) {
	if (color[begin] == 1) return 0;
	int size = 1;
	color[begin] = 1;
	for (int i = 0; i < g[begin].size(); i++) {
		size += conSize(n, m, g, g[begin][i], color);
	}
	return size;
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n, vector<int>());
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	int bridge = 0;
	vector<int> color(n, 0);
	vector<int> cc = color;
	int iniSize = conSize(n, m, g, 0, cc);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < g[i].size(); j++) {
			vector<vector<int>> g2 = g;
			int deleteEdgeNode1 = i;
			int deleteEdgeNode2 = g2[i][j];
			for (auto it = g2[deleteEdgeNode2].begin(); it != g2[deleteEdgeNode2].end();) {
				if (*it == deleteEdgeNode1) it = g2[deleteEdgeNode2].erase(it);
				else ++it;
			}
			g2[i].erase(g2[i].begin() + j);
			vector<int> cc = color;
			int newSize = conSize(n, m, g2, 0, cc);
			if (newSize != iniSize)bridge++;
		}
	}
	cout << bridge/2;
	return 0;
}





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

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

  if (a+b == c+d) {
    cout << "Balanced" << endl;
  }else if(a+b > c+d){
     cout << "Left" << endl;
  }else{
     cout << "Right" << endl;
  }  
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

int a[100032], b[100032];

int main() {
	int n;
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%d",a+i);
		b[i] = (i&1 ? 1 : -1) * (!i || i==n-1 ? 1 : 2);
	}
	std::sort(a, a+n);
	std::sort(b, b+n);
	long long ans = 0, ans2 = 0;
	for (int i = 0; i < n; i++) {
		ans += a[i] * b[i];
		ans2 += a[i] * -b[n-1-i];
	}
	printf("%lld\n",std::max(ans, ans2));
	return 0;
}


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

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int a, b, c; cin>>a>>b>>c;
	if (a - b >= c)
	{
		cout<<0<<endl;
	}
	else
	{
		c = c - (a-b);
		cout<<c<<endl;
	}
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#include <cstdlib>  
#include <cmath>
#include <string>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;
using P= pair<ll,ll>;
const ll MOD = 1000000007;
int main() {
    ll N;
    cin>>N;
    vector<ll> A(N);
    ll sum=0;
    ll answer=0;
    rep(i,N){
      cin>>A[i];
      sum+=A[i];
      sum%=MOD;
    }
    for(int i=0;i<N;i++)
    {
      sum-=A[i];
      if(sum<0)sum+=MOD;
      answer +=A[i]*sum;
      answer %=MOD;
    }
    //if(D/S>T)cout<<"No"<<endl;
    cout<<answer<<endl;
    return 0;
}

Measured memory_bytes: 4796
#include <stdio.h>

int main() {
    int h, w, n;
    // 3 7
    scanf("%d %d %d", &h, &w, &n);
    if (h > w) {
        int swap = h;
        h = w;
        w = swap;
    }
    n % w == 0 ? printf("%d\n", n / w) : printf("%d\n", n / w + 1);
}


Measured memory_bytes: 1732
#!/usr/bin/env python3
import sys

def solve(N: int, L: "List[int]", R: "List[int]"):
    LR= list(zip(L,R))
    LR.sort(key=lambda x:x[0])

    r_left_max = [] ##index 以下のrightのmin
    for lr in LR:
        if r_left_max:
            r_left_max.append(min(r_left_max[-1],lr[1]))
        else:
            r_left_max.append(lr[1])

    r_right_max = []
    for lr in LR[::-1]:
        if r_right_max:
            r_right_max.append(min(r_right_max[-1],lr[1]))
        else:
            r_right_max.append(lr[1])

    answer = 0
    for i in range(1,N):
        a = 0
        a += max(r_left_max[i-1]-LR[i-1][0]+1,0)
        a += max(r_right_max[N-i-1]-LR[-1][0]+1,0)
        answer = max(a,answer)

    ## 一つとその他の場合。indexがiのものを一つにする
    for i in range(N):
        a =0 
        a+= LR[i][1]-LR[i][0]+1
        if i == N-1:
            min_upper_limit = r_left_max[N-2]
            a+= max(min_upper_limit-LR[N-2][0]+1,0)
        elif i == 0:
            min_upper_limit = r_right_max[N-2]
            a+= max(min_upper_limit-LR[-1][0]+1,0)
        else:
            min_upper_limit = min(r_left_max[i-1],r_right_max[N-i-2])

            a+= max(min_upper_limit-LR[-1][0]+1,0)

        answer = max(a,answer)
    
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int()] * (N)  # type: "List[int]"
    R = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, L, R)

if __name__ == '__main__':
    main()


Measured memory_bytes: 20624
// https://atcoder.jp/contests/agc027/tasks/agc027_a
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#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()
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int c, int d) { return c / gcd(c, d) * d; }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int> v(n);
    REP(i, n) cin >> v[i];
    sort(ALL(v));
    int sum = 0;
    REP(i, n) {
        sum += v[i];
        if (sum > x) {
            cout << i << endl;
            return 0;
        }
    }
    if (sum == x) {
        cout << n << endl;
    } else {
        cout << n - 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

// https://atcoder.jp/contests/abc087/tasks/abc087_b
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner scanner = new Scanner(System.in);

		int a = scanner.nextInt();// 500円の枚数
		int b = scanner.nextInt();// 100円の枚数
		int c = scanner.nextInt();// 50円の枚数
		int x = scanner.nextInt();// 合計金額


		int count = 0;
		for(int i=0;i<=a;i++) {
			for(int j=0;j<=b;j++) {
				for(int k=0;k<=c;k++) {
					int sum = i*500+j*100+k*50;
					if(sum==x) {
						count++;
					}
				}
			}
		}

		System.out.println(count);
		scanner.close();
	}
}


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

using namespace std;

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

	int ans = -1;
	for (int i = 0; i <= n; i++) {
		int tmp = 1.08 * i;
		if (tmp == n) {
			ans = i;
			break;
		}
	}

	if (ans == -1) {
		cout << ":(" << endl;
	} else {
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#coding:utf-8
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
p = [0, 0]
for i in range(n):
    p[i%2]  += a[np.argmax(a)]
    a[np.argmax(a)] = 0
print(p[0]-p[1])

Measured memory_bytes: 21544
// g++ -Wall -Wextra -pedantic -std=c++17 -O3 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -fsanitize=address -fno-sanitize-recover -fstack-protector contest.cpp

#include <bits/stdc++.h>

// #define _GLIBCXX_DEBUG 1
// #define _GLIBCXX_DEBUG_PEDANTIC 1
// #define _FORTIFY_SOURCE 2

using namespace std;
#define int long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
#define PI 3.1415926535897932384626433832795
int MOD=1e9+7;
int powmod(int a,int l, int md){a%=md; int res=1;while(l){if(l&1)res=res*a%md;l/=2;a=a*a%md;}return res;}
int binpow(int a,int l){int res=1;while(l){if(l&1)res=res*a;l/=2;a=a*a;}return res;}
int invmod(int a, int md){return powmod(a,md-2,md);}
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii;
typedef vector<ll> vl; typedef pair<ll,ll> pll; typedef vector< pair<ll,ll> > vll;
#define pb push_back
int __set(int b, int i) {return b|(1LL<<i);} //set ith bit
int __unset(int b, int i) {return b&(~(1UL<<i));}
int __check(int b, int i) {return b&(1LL<<i);} //returns 0 if ith bit is 0
int mulmod(int a, int b, int md) {return ((a%md)*(b%md))%md;}
int addmod(int a, int b, int md) {return (a+b)%md;}
int submod(int a, int b, int md) {return (((a-b)%md)+md)%md;}
int divmod(int a, int b, int md) {return mulmod(a, powmod(b, md-2, md), md);} //if md is prime;
const ll inf = 0xFFFFFFFFFFFFFFFL; //very large number
priority_queue<int, vector<int>, greater<int> > pq; //for min priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
const int MX = 400010;

int f[MX];
int rf[MX];

int C(int l,int k, int md) 
{
    if (k<0||k>l){
        return 0;
    }
    return f[l]*rf[k]%md*rf[l-k]%md;
}

void precfac() {
    f[0]=1;
    for (int i=1;i<MX;i++){
        f[i]=f[i-1]*i%MOD;
    }
    rf[MX-1]=powmod(f[MX-1],MOD-2, MOD);
    for (int i=MX-2;i>=0;i--){
        rf[i]=rf[i+1]*(i+1)%MOD;
    }
}

int fac(int x) {
	int ret=1;
	for(int i = 1; i <= x; i++) {
		ret*=i;
		ret%=MOD;
	}
	return ret;
}
signed main(void)
{
	IOS;
	int n,dr;
	cin>>n>>dr;
	if(n>=10) {
		cout<<dr<<endl;return 0;
	}
	cout<<dr+100*(10-n)<<endl;
	time();
	return 0;
}

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

int main(){
    int a,b;
    cin >> a >> b;
    if (a<=b) return cout << "Impossible", 0;
    int cur = 0, cnt = 0;
    for(int i=0;i<a+b;i++){
    	if (!cnt)	cur = i, cnt++;
    	else{
    		cout << "? " << i << ' ' << cur << endl;
    		char c;
    		cin >> c;
    		cnt += (c == 'Y' ? 1 : -1);
    	}	
    }
    string ans;
    for(int i=0;i<a+b;i++){
    	cout << " ? " << cur << ' ' << i << endl;
    	char c;	cin >> c; ans.push_back('0'+(c == 'Y'));
    }
    cout << "! " << ans << endl;
}

Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}


class UnionFind {
public:
  int par[8], rank[8];
  UnionFind(){
    rep(i,8) par[i] = -1;
    rep(i,8) rank[i] = 0;
  }
  int find(int x){
    if(par[x]<0) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y){
    x=find(x); y=find(y);
    if(x==y) return;
    if(rank[x] < rank[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
    if(rank[x]==rank[y]) rank[x]++;
  }
  inline bool same(int x, int y){ return find(x) == find(y); }
  inline int size(int x){ return -par[find(x)]; }
};

int n;
int x[101],y[101];

int main(){
  scanf("%d",&n);
  rep(i,n) scanf("%d%d",x+i,y+i);

  using P = pair<int,int>;
  using PP = pair<P,int>;
  map<PP, vector<P>> lines;
  rep(i,n) repl(j,i+1,n){
    int dx=x[i]-x[j];
    int dy=y[i]-y[j];
    swap(dx,dy);
    dy = -dy;
    PP cp;
    if(dy==0){
      cp = PP({1,0}, y[i]+y[j]);
    }
    else if(dx==0){
      cp = PP({0,1}, x[i]+x[j]);
    }
    else{
      int g = __gcd(dx,dy);
      dx /= g; dy /= g;
      if(dx<0){ dx=-dx; dy = -dy; }
      cp = PP({dx,dy}, (y[i]+y[j])*dx - (x[i]+x[j])*dy);
    }
    lines[cp].push_back({i,j});
  }

  map<vector<int>, int> dp;
  vector<int> init(n);
  rep(i,n) init[i] = i;

  dp[init] = 0;
  int ref[8];
  for(auto &vp : lines){
    map<vector<int>, int> nxt(dp);
    for(auto &sv : dp){
      UnionFind uf;
      rep(i,n) uf.unite(i, sv.first[i]);
      for(auto &p : vp.second) uf.unite(p.first, p.second);

      rep(i,n) ref[i] = i;
      rep(i,n) ref[uf.find(i)] = min(i, ref[uf.find(i)]);
      vector<int> ns(n);
      rep(i,n) ns[i] = ref[uf.find(i)];

      auto itr = nxt.find(ns);
      if(itr == nxt.end()) nxt[ns] = sv.second + 1;
      else itr->second = min(itr->second, sv.second + 1);
    }
    swap(dp, nxt);
  }

  vector<int> fin(n,0);
  cout << dp[fin] << endl;

  return 0;
}



Measured memory_bytes: 4220
#ifndef TKLIB_KRUSKAL_HPP
#define TKLIB_KRUSKAL_HPP

#ifndef UNION_FIND_HPP
#define UNION_FIND_HPP

#include <vector>

namespace tklib {

class UnionFind {
private:
    std::vector<int> par;
    int components;

public:
    UnionFind(int n) : par(n, -1), components(n) {}

    bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) {
            return false;
        } else {
            if (par[x] < par[y]) std::swap(x, y);
            par[y] += par[x];
            par[x] = y;
            --components;
            return true;
        }
    }

    int find(int x) {
        if (par[x] < 0) return x;
        else return par[x] = find(par[x]);
    }

    int size(int x) {
        return -par[find(x)];
    }

    int count() {
        return components;
    }
};

} // namespace tklib

#endif // UNION_FIND_HPP

#include <algorithm>
#include <vector>
#include <tuple>

namespace tklib {

template <typename T>
auto kruskal(std::size_t V, std::vector<std::tuple<int, int, T>> &G) {
    using edge_type = std::tuple<int, int, T>;

    std::sort(begin(G), end(G), 
    [](const edge_type &lhs, const edge_type &rhs)
    { return std::get<2>(lhs) < std::get<2>(rhs); });
    
    tklib::UnionFind uf(V);
    std::vector<edge_type> edgelist;

    for(edge_type &edge : G) {
        if(uf.unite(std::get<0>(edge), std::get<1>(edge))) {
            edgelist.push_back(edge);
        }
    }

    return edgelist;
}

} // namespace tklib

#endif // TKLIB_KRUSKAL_HPP

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    int V, E;
    cin >> V >> E;
    vector<tuple<int, int, int>> G;
    while(E--) {
        int s, t, w;
        cin >> s >> t >> w;
        G.emplace_back(s, t, w);
    }

    auto edgelist = tklib::kruskal(V, G);
    int weight_sum = 0;
    for(auto e : edgelist) weight_sum += get<2>(e);
    cout << weight_sum << '\n';
}


Measured memory_bytes: 4448
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);++v)
#define FORE(x,c) for(auto &x:c)
#define FOR(v,a,n) for(int v=a;v<(int)(n);++v)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=((int)(n)-1);v>=0;--v)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1e9; const long long INFLL=1e18;
template<class T> ostream& operator << (ostream &os, const vector<T> &v) {
    ITR(i,v) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is, vector<T> &v) {
    ITR(i,v) is>>*i; return is; }
//------------------------------------------------------------------------------

signed main() {
    int n,k;
    cin>>n>>k;
    vector<vi> b={
        {4,2,0,9,7},
        {1,10,8,6,4},
        {9,7,5,3,1},
        {6,4,2,0,9},
        {3,1,10,8,6},
        {0,9,7,5,3},
        {8,6,4,2,0},
        {5,3,1,10,8},
        {2,0,9,7,5},
        {10,8,6,4,2},
        {7,5,3,1,10}
    };
    n-=2;
    int ans=(n/11)*5;
    n%=11;
    REP(i,n) {
        REP(j,5) {
            if(b[i][j]==k) ans++;
        }
    }

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


Measured memory_bytes: 256
N = int(input())
A = [int(x) for x in input().split()]


def mod_2(num,mod):
    a = num%mod 
    if a ==0:
        a = mod
    return a
m = min(A)
def min_mod(minimum,A_list):
    if all([A_list[j]==minimum for j in range(len(A_list))]):
        return minimum
        
    A_list = [mod_2(A_list[i],minimum) for i in range(len(A_list)) ]
    minimum = min(A_list)
    return min_mod(minimum,A_list)
    
print(min_mod(m,A))

Measured memory_bytes: 14224
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

D, G = MAP()
pc = [LIST() for i in range(D)]

B = list(product([0, 1], repeat=D))

ans = INF
for b in B:
    point = 0
    count = 0
    for i, vonus in enumerate(b):
        if vonus == 1:
            # take all with vonus
            point += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
        # print(count)
    if point >= G:
        ans = min(count, ans)
        # print(count)
    else:
        # 後ろから
        need_point = G - point
        added_count = count
        for i in range(len(b)-1, -1, -1):
            if b[i] == 0:
                # while need_point > 0:
                    # count_max = pc[i][0]
                    num = ceil(need_point / (100 * (i + 1)))
                    if num >= pc[i][0]:
                        ###?
                        count = INF
                        break
                    count += ceil(need_point/ ((i+1) * 100))
                    break
                    # if need_point - point_max >= 0:
                    #     need_point -= point_max
                    #     count += count_max
                    # else:
                    #     count += ceil(need_point / (100 * (i + 1)))
                    #     need_point -= point_max
        ans = min(ans, count)
print(ans)




Measured memory_bytes: 5704
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll H; cin >> H;
  ll cnt = 1;
  while (H > 0) {
    H >>= 1;
    cnt *= 2;
  }
  cout << cnt - 1 << endl;

  return 0;
}



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

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

  bool ans = true;
  if (S.at(0)=='A' && S.at(1)=='A' && S.at(2)=='A') ans=false;
  if (S.at(0)=='B' && S.at(1)=='B' && S.at(2)=='B') ans=false;
  
  if (ans) {
   cout << "Yes" << endl;
  }
  else {
   cout << "No" << endl;
  }

}

Measured memory_bytes: 256
n  = gets.strip.to_i
xs = gets.strip.split.map(&:to_i)

w = []
count = 0
for i in 0...xs.max
  prev = 0
  for j in 0...n
    if xs[j] > 0 then
      xs[j] -= 1
      count += 1 if prev == 0
      prev = 1
    else
      prev = 0
    end
  end
end
puts count

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

int main(){
   string s;
   bool flag=true;
   cin >> s;
   int len=s.length();
   sort(s.begin(),s.end());
   for(int i=1;i<len;i++){
       if(s[i]==s[i-1]) flag=false;
   }
   if(flag) cout << "yes" <<endl;
   else cout << "no" <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int i,n,u,v,count=0;
	bool flag[31];
	for(i=1;i<31;i++) flag[i] = false;
	for(i=0;i<28;i++){
		scanf("%d",&n);
		flag[n] = true;
	}
	for(i=1;i<31;i++){
		if(!flag[i]&&!count){
			u = i;count++;
		}
		if(!flag[i]&&(count>0)) v = i;
	}
	if(u<v)	printf("%d\n%d\n",u,v);
	else	printf("%d\n%d\n",v,u);
	return 0;
}

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

int main(){
	int n, t;
	int two, five;
	while(cin >> n){

		if(n==0)break;

		two=0;
		five=0;

		for(int i=2;i<=n;i+=2){
			t=i;

			while(t%2==0){
				++two;
				t/=2;
			}
		}

		for(int i=5;i<=n;i+=5){
			t=i;

			while(t%5==0){
				++five;
				t/=5;
			}
		}

		if( two <= five )cout << two << endl;
		else cout << five << endl;


	}


	return 0;
}

Measured memory_bytes: 1160
x0, y0 = 0, 0
w, h, n = map(int, input().split())

for _ in range(n):
    x, y, a = map(int, input().split())
    if a == 1 and x0 < x:
        x0 = x
    elif a == 2 and x < w:
        w = x
    elif a == 3 and y0 < y:
        y0 = y
    elif a == 4 and y < h:
        h = y

print(max(0, w - x0) * max(0, h - y0))

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

char S[1005];

int main() {
	scanf(" %s", S);
	string s = S;
	if (s[s.size() - 1] == 's') s += "es";
	else s += "s";
	printf("%s\n", s.c_str());
	return 0;
}


Measured memory_bytes: 3656
#include<stdio.h>
int main(void)
{
	int x;
	int t=0;
	scanf("%d",&x);
	for(int i=1;i<=x;i++)
	{
		if(i%2==1)
		t++;
	}
	printf("%.9lf",(t*1.0)/(x*1.0));
	return 0;
	} 


Measured memory_bytes: 128
#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

A, B = ISI()
S = IS()
Num = ["0","1", "2", "3", "4", "5", "6", "7", "8", "9"]
a = S[:A]
b = S[A+1:]
c = S[A]
good = True
for _a in a:
    if _a in Num:
        continue
    else:
        good = False
for _b in b:
    if _b in Num:
        continue
    else:
        good = False
if c != "-":
    good = False
if good == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<stdio.h>
int main(){
  char s[100001];
  int i,kai=0;
  
  scanf("%s",s);
  
  if(s[0]=='0'){
    for(i=1;i<100001;i++){
      if(i%2==0&&s[i]=='1'){
        kai++;
      }
      if(i%2==1&&s[i]=='0'){
        kai++;
      }
      if(s[i]=='\0'){
        break;
      }
    }
  }
  if(s[0]=='1'){
    for(i=1;i<100001;i++){
      if(i%2==0&&s[i]=='0'){
        kai++;
      }
      if(i%2==1&&s[i]=='1'){
        kai++;
      }
      if(s[i]=='\0'){
        break;
      }
    }
  }
  printf("%d",kai);
  return 0;
}

Measured memory_bytes: 256