akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.util.Map.Entry;
 
 
 
public class Main{
	
	
	
	public static Set<Long> set=new HashSet<Long>();
	public static long T;
	public static long ans;
	

 
	
	//最大公約数・最小公倍数（セットで使う）
	public static long gcm(long a, long b) {
		long result = a;
		long k = 0;
		long n = b;
		do {
			k = result % n;
			result = n;
			n = k;
		} while(k != 0);
		return result;
	}
	
	public static long lcm(long a, long b) {
		long g;
		g = gcm(a, b);
		return a/g*b;
	}
	
	static long gcd(long a, long b) {
		if (b == 0) {
			return a;			
		}
		return gcd(b, a % b);
	}
	
	//等差数列
	static long tousasum(int n) {
		return (long)n*((long)n+1)/2;
	}
 
 
 
	//素数判定
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
		return true;
	}
 
 
	//倍数判定（10進数以外のときに有用）
	static boolean isMultiple (String s, int base, int m) {
		int temp = 0;
		for (int i=0; i<s.length(); i++) {
			temp = (temp*base+Character.getNumericValue(s.charAt(i)))%m;
		}
		if (temp==0) {return true;}
		return false;
	}
 
 
	//階乗
	static long factorial (int i) {
		if (i==1) {return 1;}
		else {return i*factorial(i-1);}
	}
 
 
	//進数変換
	static String toNbase (String sm, int m, int n) {
		return Long.toString(Long.parseLong(sm,m),n);
	}
	
	public static final long gcd_n(long[] param) {
	    final int len = param.length;
	    long g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
	    for (int i = 1; i < len - 1; i++) {
	        g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
	    }
	    return g;
	}
	
	public static long lcm_n(long[] numbers) {
		long l;
		l = numbers[0];
		for (int i = 1; i < numbers.length; i++) {
			l = lcm(l, numbers[i]);
		}
		return l;
	}
	
    public static boolean tree(long N,long r) {
    	ans = r;
    	if(N==T) {
    		return true;
    	}else if(2*N==T||2*N+1==T) {
    		ans = r+1;
    		return true;
    	}else if(2*N>T) {
    		return false;
    	}
    	return tree(2*N,r+1)||tree(2*N+1,r+1);
    	
    	
    }
	
	
 public static void main(String[] args) {
	 Scanner sc=new Scanner(System.in);
	 Map<Long,Long> map=new TreeMap<Long,Long>();
	 long N=sc.nextLong();
	 long K=sc.nextLong();
	 for(int i=0;i<N;i++) {
		 long a=sc.nextLong(),b=sc.nextLong();
		 if(map.containsKey(a)) {
			 map.put(a,map.get(a)+b);
		 }else {
			 map.put(a,b);
		 }
	 }
	 long result=0;
	 for (Long nKey : map.keySet())
     {
         result+=map.get(nKey);
         if(result>=K) {
        	 System.out.println(nKey);
        	 return;
         }
     }
    
}
}


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

int main() {
	long long a, b;
	cin >> a >> b;
	if (a > 0) {
		cout << "Positive" << endl;
		return 0;
	}
	if (a * b <= 0) {
		cout << "Zero" << endl;
		return 0;
	}
	cout << ((b - a) % 2 ? "Positive" : "Negative") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	char dayOfWeekStr[7][16] = {"Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday"};
	int numOfDays[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	int i;
	int j;
	int month;
	int day;
	int counter;
	
	while( 1 )
	{
		scanf( "%d%d", &month, &day );
		if( month == 0 )break;
		
		counter = 0;
		for( i = 1; i < month; i++ )
		{
			for( j = 1; j <= numOfDays[i - 1]; j++ )
			{
				counter++;
			}
		}
		for( i = 1; i <= day; i++ )
		{
			counter++;
		}
		printf( "%s\n", dayOfWeekStr[(counter - 1) % 7] );
	}
	
	return (0);
}

Measured memory_bytes: 584
//デバッグ用オプション：-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//以下、素集合と木は同じものを表す
class UnionFind {
public:
    vector<ll> parent; //parent[i]はiの親
    vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
    map<ll,vector<ll>> group;//素集合ごとに管理する連想配列(keyはそれぞれの素集合の親、valueはその素集合の要素の配列)

    //コンストラクタ
    UnionFind(ll n):parent(n),siz(n,1){ 
        //全ての要素の根が自身であるとして初期化
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //データxの属する木の根を取得(経路圧縮も行う)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
    }

    //xとyの木を併合
    void unite(ll x,ll y){
        ll rx=root(x);//xの根
        ll ry=root(y);//yの根
        if(rx==ry) return;//同じ木にある時
        //小さい集合を大きい集合へと併合(ry→rxへ併合)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
    }

    //xとyが属する木が同じかを判定
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //xの素集合のサイズを取得
    ll size(ll x){
        return siz[root(x)];
    }

    //素集合をそれぞれグループ化
    void grouping(ll n){
        //経路圧縮を先に行う
        REP(i,n)root(i);
        //mapで管理する(デフォルト構築を利用)
        REP(i,n)group[parent[i]].PB(i);
    }
};

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  	ll n,q;cin>>n>>q;
  	UnionFind uf(n);
  	REP(_,q){
      	ll t,u,v;cin>>t>>u>>v;
      	if(t==0)uf.unite(u,v);
      	else cout<<ll(uf.same(u,v))<<endl;
    }
}

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

const int MAX = 510000;
const int MOD = 1000000007;
const int MAX_N = 200000;

int ctoi(const char c){
 switch(c){
   case '0': return 0;
   case '1': return 1;
   case '2': return 2;
   case '3': return 3;
   case '4': return 4;
   case '5': return 5;
   case '6': return 6;
   case '7': return 7;
   case '8': return 8;
   case '9': return 9;
   default : return -1;
 }
}

ll value(vector<ll> A){
  ll ans=0;
  ll d=1;
  for(ll i=0;i<A.size();i++){
    ans += d*A[i];
    d*=10;
  }
  return ans;
}

ll ans=0;
ll N_digit;
ll N;

void dfs(vector<ll> A){
  if(value(A)>N){
    return;
  }

  bool flag3=false;
  bool flag5=false;
  bool flag7=false;
  for(ll i=0;i<A.size();i++){
    if(A[i]==3) flag3=true;
    if(A[i]==5) flag5=true;
    if(A[i]==7) flag7=true;
  }

  if(flag3 && flag5 && flag7) ans++;

  vector<ll> LIST={3,5,7};
  for(ll itr : LIST){
    A.push_back(itr);
    dfs(A);
    A.pop_back();
  }

  return ;
}

int main(int argc, const char * argv[]) {
  
  cin >> N;
  N_digit = log10(N)+1;
  vector<ll> A;
  dfs(A);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int a,b,ans;
  
  scanf("%d %d", &a, &b);
  if(1 <= a && a <= 9 && 1 <= b && b <= 9){
    ans = a * b;
  }else{
    ans = -1;
  }
  printf("%d\n", ans);
  return 0;
}

    

Measured memory_bytes: 128
#include <cstdio>
int main() {
  long long n;
  for (int c; (c = getchar_unlocked()) >= '0'; ) { n *= 10; n += c - '0'; }
  long long a = n/3, b = n/5, c = n/15;
  long long ans = n*(n+1)/2 - a*(a+1)/2*3 - b*(b+1)/2*5 + c*(c+1)/2*15;
  char buf[64] = {};
  int i;
  for (i = 0; ans; i++) {
    buf[i] = '0' + ans % 10;
    ans /= 10;
  }
  while (i--) {
    putchar_unlocked(buf[i]);
  }
  
}


Measured memory_bytes: 1536
// 解説後
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  size_t N;
  std::string S;
  std::cin >> N >> S;

  // 共通文字列の最大長を求める
  size_t result = 0;  // 一致する部分文字列の最大長
  std::vector<size_t> z;  // [0, z[i])と[i, i+z[i])が一致している
  for (size_t l1 = 0; l1 < N - 1; ++l1) {
    // バッファをクリアする
    z.clear();
    z.resize(N - l1, 0);

    // Z-Algorithm
    size_t c = 0;  // [l1, l1+len)と[c, z[c])が一致している
    for (size_t i = 1; i < z.size(); ++i) {
      if (i + z[i - c] < c + z[c]) {
        // 一致を確認した範囲の中であれば、以前に計算した値を再利用できる
        z[i] = z[i - c];
      } else {
        // 一致を確認した範囲を外れる場合、改めて一致する部分を探す
        const size_t l2 = l1 + i;
        size_t len = 0;
        if (c + z[c] > i) len = c + z[c] - i;
        for (; l2 + len < N; ++len) {
          if (S[l1 + len] != S[l2 + len]) break;
        }
        z[i] = len;
        c = i;
      }
    }
    z[0] = z.size();

    for (size_t i = 0; i < z.size(); ++i) {
      result = std::max(result, std::min(i, z[i]));
    }
  }

  std::cout << result;
  return 0;
}


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

S = input()
T = S[::-1]

cnt = 0

for i in range(len(S)):
  if S[i] != T[i]:
    cnt += 1
    
print(-(-cnt//2))

Measured memory_bytes: 5704
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>

using namespace std;

template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}

template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define left left228
#define right right228
// #define prev prev228
#define mp make_pair
#define all(v) v.begin(), v.end()
#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define firn(i, n) for (int i = 1; i < (int)n; ++i)
#define x first
#define y second

const int N = 303;
const int MOD = 998244353;

int mod(int x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}
int fp(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = mod(a * a)) {
        if (b & 1) res = mod(res * a);
    }
    return res;
}

int n, m;
bitset<N> a[N];
bitset<N> b[N];
vector< bitset<N> > basis;

void add(bitset<N> x) {
    for (int i = m; i >= 1; --i) {
        if (x[i] == 0) continue;
        if (x[i] && b[i] != 0) {
            x ^= b[i];
        } else {
            b[i] = x; basis.emplace_back(x); break;
        }
    }
    if (x.count() == 0) return;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int y;
            cin >> y;
            a[i][j] = y;
        }
    }
    for (int i = 1; i <= n; ++i) {
        add(a[i]);
    }
    int xor0 = fp(2, n - (int)basis.size());
    int xor1 = mod(fp(2, n) - xor0);
    int answer = mod(xor1 * fp(2, m - 1));
    cout << answer << '\n';
    return 0;

}

/*
3
1 1 2
2 2 2
3 3 2
2 1 1
3 2 1


2 2
1 1 2
2 2 2
1 2 3
2 1 1

2
2 1 2 2 3
2 2 2 1 1

5
1 2
2 3
3 4
3 5
1
2 3
1 2
4 3
2 3 5

*/

Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
 
int main(void){
    char str[1001];     // input; input string , 1<=length<=1000
    int n=0;            // input; command times, 1<=n<=100
    int a=0, b=0;
    char* p_str=str;    // string pointer
    char cpy[1001];
    int i=0, j=0;       // loop index
 
    scanf("%s", str);
    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%s", cpy);
        if(strcmp(cpy, "print") == 0){
            scanf("%d %d", &a, &b);
            p_str = str + a;
            strncpy(cpy, p_str, b-a+1);
            cpy[b-a+1] = '\0';
            printf("%s\n", cpy);
 
        }else if(strcmp(cpy, "reverse") == 0){
            scanf("%d %d", &a, &b);
            p_str = str + b;
            for(j=0;j<b-a+1;j++){
                cpy[j] = *(p_str);
                p_str--;
            }
            p_str = str + a;        // ??????¶???????????????
            for(j=0;j<b-a+1;j++) *(p_str + j) = cpy[j];
 
        }else if(strcmp(cpy, "replace") == 0){
            scanf("%d %d %s", &a, &b, cpy);
            p_str = str + a;
            for(j=0;j<b-a+1;j++) *(p_str + j) = cpy[j];
         
        }else{
         
        }
    }
    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
int n, ma, mb, dp[405][405], a, b, c, ans = 100005;
int main(){
    scanf("%d%d%d", &n, &ma, &mb);
    fill(dp[0], dp[405], 100005);
    dp[0][0] = 0;
    rep(i,n){
        scanf("%d%d%d", &a, &b, &c);
        for(int j = 400; j >= a; j--) for(int k = 400; k >= b; k--) dp[j][k] = min(dp[j][k], dp[j-a][k-b] + c);
    }
    for(int i = 1; i*ma <= 400 && i*mb <= 400; i++) ans = min(ans, dp[i*ma][i*mb]);
    printf("%d\n", ans == 100005 ? -1 : ans);
}

Measured memory_bytes: 896
#include <stdio.h>

int main(void)
{
  int n, m;
  int a[20][20];
  int b[20];
  int c;
  int count = 0;

  scanf("%d %d %d", &n, &m, &c);
  for (int i = 0; i < m; i++)
    scanf("%d", &b[i]);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      scanf("%d", &a[i][j]);
  for (int i = 0; i < n; i++) {
    int sum = c;
    for (int j = 0; j < m; j++) {
      sum += a[i][j] * b[j];
    }
    if (sum > 0)
      count++;
  }
  printf("%d\n", count);
}

Measured memory_bytes: 128
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
#define fi   first
#define se   second
using namespace std;
int n,m,X,Y,c[200005],w[200005],f[200005],a[200005],b[200005],s[200005];
vector<int> v[200005];
ll ans=1,jc[200005],njc[200005];
int get(int x){return x==f[x]?x:f[x]=get(f[x]);}
bool cmp(int x,int y){return w[x]<w[y];}
ll fp(ll x,int k=orz-2){
    ll ans=1;
    while(k){
        if(k&1)ans=ans*x%orz;
        k>>=1,x=x*x%orz;
    }
    return ans;
}
int main(){
    scanf("%d%d%d",&n,&X,&Y);
    for(int i=1;i<=n;++i){
        scanf("%d%d",c+i,w+i);
        f[i]=i;
        if(!a[c[i]]||w[a[c[i]]]>w[i])a[c[i]]=i;
    }
    for(int i=1;i<=n;++i)if(a[i])b[++m]=a[i];
    sort(b+1,b+m+1,cmp);
    for(int i=1;i<=n;++i)if(w[i]+w[a[c[i]]]<=X&&get(i)!=get(a[c[i]]))f[f[i]]=f[a[c[i]]];
    for(int i=1;i<=n;++i){
        int k=b[1];
        if(c[i]==c[k]){
            if(m==1) continue;
            k=b[2];
        }
        if(w[k]+w[i]<=Y&&get(k)!=get(i))f[f[i]]=f[k];
    }
    jc[0]=1;
    for(int i=1;i<=n;++i)jc[i]=jc[i-1]*i%orz;
    njc[n]=fp(jc[n]);
    for(int i=n;i;--i)njc[i-1]=njc[i]*i%orz;
    for(int i=1;i<=n;++i)++s[get(i)],v[get(i)].pb(c[i]);
    for(int i=1;i<=n;++i){
        if(s[i]){
            ans=ans*jc[s[i]]%orz;
            sort(v[i].begin(),v[i].end());
            int o=0;
            for(int j=0;j<v[i].size();++j){
                if(j&&v[i][j]!=v[i][j-1])ans=ans*njc[o]%orz,o=1;
                else ++o;
            }
            ans=ans*njc[o]%orz;
        }
    }
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}


Measured memory_bytes: 18560
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    l=[]
    l.append(2)
    l.append(1)
    for i in range(85):
        l.append(l[-1]+l[-2])
    print(l[n])
if __name__ == '__main__':
    do()

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

int main() {
  ll N;
  string S;

  cin >> N >> S;

  ll res = 1000000;
  vector<ll> ba(N), wa(N);
  int b = 0, w = -1;
  int i = 0, j = N - 1;
  while (i < N) {
    if (S.at(j) == '.') { w++; }
    if (S.at(i) == '#') { b++; }
    wa.at(j) = w;
    ba.at(i) = b;
    i++;
    j--;
  }

  for (int i = 0; i < N; i++) {
    // if (i != N - 1 && S.at(i) != S.at(i + 1)) {
    // if (i != N - 1 && S.at(i) != S.at(i + 1)) {
    res = min(res, (wa.at(i) + ba.at(i)));
    //}
  }
  if (res == 1000000) {
    cout << 0 << endl;
  } else {
    cout << res << endl;
  }
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define F first
#define S second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9+7;

int main(){
    double n;
    cin >> n;
    double l = n/3;
    cout << fixed << setprecision(10) << l*l*l;
}

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

using namespace std;

int main(int argc, char *argv[]) {
    int N, K;
    cin >> N >> K;

    int bunbo = 0;
    int64_t bunsi = 0;
    for (int i = 1; i <= N; i++) {
        int l = i;
        int cnt = 0; //  勝つために振り続ける数
        while (l < K) {
            l *= 2; 
            cnt++;
        }

        int p = pow(2, cnt);
        if (i == 1) bunbo = N * p;

        if (cnt == 0) {  // 必ず勝つ
            bunsi += (bunbo / N);
        } else {
            bunsi += (bunbo / (p * N));
        }
    }

    double ans = bunsi * 1.0 / (bunbo * 1.0);
    cout << setprecision(15) << ans << endl;
    return 0;
}


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

using namespace std;

#define fo(i,n) for(int i=0; i<n; i++)
#define Fo(i,k,n) for(int i=k; i<n; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int n,k;
vi h, dp;

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin>>n>>k;
    h.resize(n+1);
    dp.resize(n+1, INT_MAX);
    Fo(i,1,n+1)cin>>h[i];
    dp[1]=0;
    Fo(i,2,n+1){
        Fo(j,1,k+1){
            if(i-j < 1)break;
            // cout<<dp[i-j]<<" "<<abs(h[i]-h[j])<<" "<<i<< " "<<j<<endl;
            dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

Measured memory_bytes: 1024
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Control.Monad.Trans.State
import qualified Data.ByteString.Unsafe as B
import qualified Data.ByteString.Char8  as C8
import Data.Char
import Data.List
import Data.Maybe
import qualified Data.Vector.Unboxed as U

type Pair = (Int, Int)

main :: IO ()
main = do
  [n,m] <- readInts
  ps <- sortOn fst <$> replicateM n readPair
  print $ solve m ps

solve :: Int -> [Pair] -> Int
solve m = fst . U.foldl' f e . U.fromList
  where
    e = (0,0)
    f (!s,!n) (a,b)
      | n == m    = (s,n)
      | c > m     = (s+a*(m-n),m)
      | otherwise = (s+a*b,c)
      where
        c = n+b

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

readPair :: IO Pair
readPair = head . unfoldr readT <$> C8.getLine
  where
    readT = runStateT $
      (,) <$> StateT (C8.readInt . C8.dropWhile isSpace)
          <*> StateT (C8.readInt . B.unsafeTail)

Measured memory_bytes: 38268
import numpy as np

N = int(input())
a_list = list(map(int, input().split()))
a_list = np.array(a_list)

if N % 3 != 0:
    if (a_list != 0).any():
        print("No")
    else:
        print("Yes")
    exit()

if (a_list == 0).all():
    print("Yes")
    exit()

keta = 0
while (a_list != 0).any():
    s = (a_list & 1).sum()
    if s != 2 * len(a_list) // 3 and s != 0:
        print("No")
        exit()
    else:
        a_list >>= 1

print("Yes")

Measured memory_bytes: 23916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<int> dp(100001);
vector<bool> ok(100001);
vector<vector<int> > g(100001);

int solve(int x) {
	if(ok[x]) return dp[x];
	ok[x] = true;
	int rec = 0;
	rep(y, g[x].size()){
		chmax(rec, solve(g[x][y]) + 1);
	}
	return dp[x] = rec;
}

int main(){
	int n, m;
	cin >> n >> m;
	
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--; y--;
		g[x].push_back(y);
	}

	int ans = 0;
	rep(i, n){
		chmax(ans, solve(i));
	}
	cout << ans << endl;
}

Measured memory_bytes: 10940
import heapq
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
largest = max(A)
A = [(largest - i, i) for i in A]
heapq.heapify(A)

for i in range(M):
  x = heapq.heappop(A)
  heapq.heappush(A, (largest-(x[1]//2), x[1]//2))

print(sum([i[1] for i in A]))



Measured memory_bytes: 17428
s = gets.chop

a,b,c,d = s.split("")

ab = a.to_s + b.to_s
cd = c.to_s + d.to_s

if ab.to_i > 12 && cd.to_i > 12 || ab.to_i > 12 && cd == "00" || cd.to_i > 12 && ab == "00" || cd == "00" && ab == "00"
  puts "NA"
elsif ab.to_i > 12 || ab == "00" && cd.to_i <= 12
  puts "YYMM"
elsif cd.to_i > 12 || cd == "00" && ab.to_i <= 12
  puts "MMYY"
else
  puts "AMBIGUOUS"
end


Measured memory_bytes: 1788
#include<stdio.h>
#include <stdlib.h>
 // (double*) malloc(sizeof(double)*(n+1))


double abso(double a)
{
	return a > 0 ? a : -a;
}


int main() 
{
	// 先输入n，再输入有序的 
	int n;
	scanf("%d", &n);
	double b[n+1]; // 关键字, 下标从1到n 
	double a[n+1]; // 虚节点，下标从0到n 
	double cost[n+2][n+2];
	double w[n+2][n+2];
	int root[n+2][n+2];
	for (int i=1;i<=n;i++)
	{
		scanf("%lf", &b[i]);
	}
//	printf("ok\n");
	double sum = 0;
	for (int i=0;i<=n;i++)
	{
		scanf("%lf", &a[i]);
		sum += a[i];
	}
	
	
	for (int i=0;i<n+2;i++)
	{
		for (int j=0;j<n+2;j++)
		{
			root[i][j] = 0;
			
		}
	}
	
	
	
	for(int i=0;i<=n;i++)
	{
		cost[i+1][i] = 0.0; // 为虚结点的开销赋初始值
		w[i+1][i] = a[i]; // 为虚结点查找概率赋初始值	
	}
	int l;
	for(int j=1;j<=n;j++) // 关键字的规模
	{
		for (int k=1;k<=n-j+1;k++) // 对于下标从k开始的树 
		{
			l = k + j - 1; // 最右边的结点序号 
			w[k][l] = w[k][l-1] + b[l] + a[l];
			cost[k][l] = cost[k][k-1] + cost[k+1][l]; // 初始化为根节点在最左边的情况,先不加上w[k][l] 
			root[k][l] = k; // 初始化为根节点在最左边的情况
			for (int m=k+1;m<=l;m++) // 根节点为m时的情况 
			{
				double temp = cost[k][m-1] + cost[m+1][l];
//				printf("compare %lf and cost[%d][%d] + cost[%d][%d] = %lf\n", cost[k][l], k, m-1, m+1, l, temp);
				if (temp < cost[k][l] && abso(temp - cost[k][l]) > 1e-6 ) // 小于不等于 
				{
					cost[k][l] = temp;
					root[k][l] = m;
				}
			}
			cost[k][l] += w[k][l];
		}
	}
	printf("%lf", cost[1][n]+sum);
//	
//	for (int i=0;i<n+2;i++)
//	{
//		for (int j=0;j<n+2;j++)
//		{
//			printf("%lf ", cost[i][j]);
//			
//		}
//		printf("\n");
//	}
//	for (int i=0;i<n+2;i++)
//	{
//		for (int j=0;j<n+2;j++)
//		{
//			printf("%d ", root[i][j]);
//			
//		}
//		printf("\n");
//	}
	
	getchar(); 
	return 0;
}


Measured memory_bytes: 6780
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

const string YES = "Yes";
const string NO = "No";

void solve(long long N, long long M){
    if(N == M){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    solve(N, M);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define K 101
#define t (1<<28);

int n;
int Gk[K][K];

int main()
{
  int i=0, j=0, k=0;
  int d=0, v=0, c=0;
  int tm=0;
  for(i=0;i<K;i++)
    {
      for(j=0;j<K;j++)
	{
	  if(i==j)Gk[i][j]=0;
	  else Gk[i][j]=t;
	}
    }
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d %d",&d,&k);
      while(1)
	{
	  if(k==0)break;
	  scanf("%d %d",&v,&c);
	  Gk[d][v]=c;
	  k--;
	}
    }

  for(k=0;k<n;k++)
    {
      for(i=0;i<n;i++)
	{
	  for(j=0;j<n;++j)
	    {
	      tm=Gk[i][k]+Gk[k][j];
	      if(tm<Gk[i][j])Gk[i][j]=tm;
	    }
	}
    }

  for(i=0;i<n;++i)
    {
      printf("%d %d\n",i,Gk[0][i]);
    }

  return 0;
}




Measured memory_bytes: 1956
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  long double T, X;
  cin >> T >> X;

  cout << std::fixed << std::setprecision(7) << T / X << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define erep(i,a,b) for(int i=a;i<=(int)(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>(a);i--)
#define eper(i,a,b) for(int i=((int)(a));i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
using namespace std;
typedef long long ll;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n;
ll c, k, ans;
vector<ll> t;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n >> c >> k;
    rep(i, 0, n) {
        ll x; cin >> x;
        t.pb(x);
    }
    sort(t.begin(), t.end());
    t[n] = INF;
    rep(i, 0, n) {
        ll cnt = 1, now = t[i];
        while (cnt < c && t[i+1] <= now+k) {
            cnt++, i++;
        }
        ans++;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i]
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
const int maxN = 1000001;
string extractStringAtKey(string str, int key){
    char *s = strtok((char *)str.c_str(), " ");
    while(key > 1){
        s = strtok(NULL, " ");
        key--;
    }
    return (string)s;
}
bool prime[maxN + 1];
void seive(){
    memset(prime, true, sizeof(prime));
    for(int i = 2; i * i <= maxN; ++i){
        if(prime[i]){
            for(int j = i * i; j <= maxN; j += i){
                prime[j] = false;
            }
        }
    }
}
int32_t main(){
    SPEED;
    int n;
    cin >> n;
    string s = to_string(n);
    int ans = -INF;
    int ln = len(s), cnt = 0, temp = 0, res = 0;
    for(char c: s){
        cnt++;
        res += c - '0';
        temp += c - '0';
        int ln = (len(s) - cnt) * 9;
        ans = max(ans, (temp - 1 + ln));
    }
    cout << max(ans, res) ;
}

Measured memory_bytes: 3684
import java.util.Scanner;

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

        while (true) {
            int a = sc.nextInt();
            String op = sc.next();
            int b = sc.nextInt();
            int ans = 0;

            if (op.equals("?")) {
                break;
            }
            if (op.equals("+")) {
                ans = a + b;
            }
            if (op.equals("-")) {
                ans = a - b;
            }
            if (op.equals("*")) {
                ans = a * b;
            }
            if (op.equals("/")) {
                ans = a / b;

            }
            System.out.println (ans);
        }
    }

}



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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    string s, t; cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    if(s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n, ans = 0;
  cin >> n;
  int x[100003];
  rep(i, n) cin >> x[i];

  for (int i = 0; i < n;) {
    if (i < n - 1) {
      if (x[i] == i + 1 && x[i + 1] == i + 2) {
        ans++;
        i += 2;
      } else if (x[i] == i + 1 && x[i + 1] != i + 2) {
        ans++;
        i++;
      } else {
        i++;
      }
    } else {
      if (x[i] == i + 1) {
        ans++;
      }
      i++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())
using namespace std;
int n,m,t;
bitset<50010> a[50010];
int x[100100],y[100100];
bool rch[50010];
int en[50010];
int cnt[50010];
string s;
void s1(){//subtask 1
	for(int i=1;i<=n;i++){
		a[i].reset();
		rch[i]=false;
	}
	for(int i=1;i<=n;i++)
		a[i].set(i);//自己能到自己 
	for(int i=1;i<=m;i++){//加边 
		a[x[i]]=a[y[i]]=a[x[i]]|a[y[i]];
	}
	for(int i=1;i<=n;i++){//到哪里？ 
		if(a[i].count()==n){//都可到它 
			rch[i]=true;
			for(int j=m;j>=1;j--){
				if(rch[x[j]]){
					rch[y[j]]=rch[x[j]];
					s="^"+s;
				}
				else{
					rch[x[j]]=rch[y[j]];
					s="v"+s;
				}
			}
			cout<<s<<endl;
			return;
		}
	}
	cout<<-1<<endl;
}
void s2(){
	if(n==2){
		cout<<-1<<endl;
		return;
	}
	for(int i=1;i<=n;i++){
		en[i]=i;
		cnt[i]=1;
	}
	for(int i=m;i>=1;i--){
		if(cnt[en[x[i]]]>=2){
			cnt[en[x[i]]]--;
			cnt[en[y[i]]]++;
			en[x[i]]=en[y[i]];
			s="v"+s;
		}
		else{
			cnt[en[y[i]]]--;
			cnt[en[x[i]]]++;
			en[y[i]]=en[x[i]];
			s="^"+s;
		}
	}
	cout<<s<<endl;
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>t;
	for(int i=1;i<=m;i++)
		cin>>x[i]>>y[i];
	if(t==1)
		s1();
	else
		s2();
	return 0;
}


Measured memory_bytes: 306892
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    multiset<ll> ms;
    ll n;
    ll a[100010];
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        auto itr = ms.lower_bound(a[i]);
        // --index;
        if(itr == ms.begin()){
            ms.insert(a[i]);
        }else{
            itr--;
            itr = ms.erase(itr);       //  削除
            ms.insert(a[i]);
        }
    }
    // for (auto e : ms) {
    //     std::cout << e << std::endl;
    // }
    std::cout << ms.size() << std::endl;
    
}




Measured memory_bytes: 5760
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    ll ans = INF;
    rep(i, n) {
        ll a, b;
        cin >> a >> b;
        chmin(ans, a+b);
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 256
n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []
for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i] [j] += A[i] [k] * B[k] [j]

for ni in range(n):
    print(" ".join([str(s) for s in C[ni]]))

Measured memory_bytes: 8988
#include<stdio.h>
#include<stdbool.h>

int main(void){
    int count;
    char mark;
    int num;
    bool card[4][13] = {};
    char current_mark;
    scanf("%d\n", &count);
    for(int i=0; i<count; i++){
        scanf("%c %d\n", &mark, &num);
        switch(mark){
        case 'S':
            mark = 0;
            break;
        case 'H':
            mark = 1;
            break;
        case 'C':
            mark = 2;
            break;
        case 'D':
            mark = 3;
            break;
        }
        card[mark][num-1] = true;
    }
    
    for(int i=0; i<4; i++){
        switch(i){
        case 0:
            current_mark = 'S';
            break;
        case 1:
            current_mark = 'H';
            break;
        case 2:
            current_mark = 'C';
            break;
        case 3:
            current_mark = 'D';
            break;
        }
        for(int j=0; j<13; j++){
            if(card[i][j] != true){
                printf("%c %d\n", current_mark, j+1);
            }
        }
    }
}


Measured memory_bytes: 2056
N = int(input())
S_lis = []
for _ in range(N):
    S_lis.append(input())


S_set = set(S_lis)
S_dict = dict()
# dict initialize
for s in S_set:
    S_dict[s] = 0
# valが全文字通過していくときに辞書のカウントを+1
for val in S_lis:
    S_dict[val] += 1
max_num = max(S_dict.values())
ans = list()
for k, v in S_dict.items():
    if v == max_num:
        ans.append(k)
ans = sorted(ans)
for res in ans:
    print(res)

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

long *tree[300001];

int main(void) {

  long n,m;
  scanf("%ld %ld", &n, &m);
  long tree_s[n*3+1];
  for (long i = 0; i <= n*3; i++) {
    tree_s[i] = 0;
  }
  long u,v;
  for (long i = 0; i < m; i++) {
    scanf("%ld %ld", &u, &v);
    tree[u] = realloc(tree[u], sizeof(long)*(tree_s[u]+1));
    tree[u][tree_s[u]] = n+v;
    tree_s[u]++;
    tree[n+u] = realloc(tree[n+u], sizeof(long)*(tree_s[n+u]+1));
    tree[n+u][tree_s[n+u]] = n*2+v;
    tree_s[n+u]++;
    tree[n*2+u] = realloc(tree[n*2+u], sizeof(long)*(tree_s[n*2+u]+1));
    tree[n*2+u][tree_s[n*2+u]] = v;
    tree_s[n*2+u]++;
  }
  long s,t;
  scanf("%ld %ld", &s, &t);
  long visited[n*3+1];
  for (long i = 0; i <= n*3; i++) {
    visited[i] = -1;
  }
  visited[s] = 0;
  long queue[n*3];
  queue[0] = s;
  long start = 0, end = 0, tail = 0;
  long cur,next;
  int flag;
  while (1) {
    flag = 0;
    for (long i = start; i <= end; i++) {
      cur = queue[i];
      for (long j = 0; j < tree_s[cur]; j++) {
        next = tree[cur][j];
        if (visited[next] != -1) {
          continue;
        }
        visited[next] = visited[cur]+1;
        tail++;
        queue[tail] = next;
        flag = 1;
      }
    }
    if (flag == 0 || tail == n*3-1) {
      break;
    }
    start = end+1;
    end = tail;
  }
  if (visited[t] == -1) {
    printf("-1\n");
  } else {
    printf("%ld\n", visited[t]/3);
  }

  return 0;
}

Measured memory_bytes: 18944
#include <bits/stdc++.h>
using namespace std;
int main(){
  string tap;
  cin >> tap;
  
  for(int i=0; i<tap.size() ; i +=2){
    if(tap.at(i) == 'L' ){
      cout << "No" << endl;
      break;
    }
    if(tap.size() - i != 1 && tap.at(i+1) == 'R'){
       cout << "No" << endl;
      break;
    }
    if(tap.size() - i <= 2){
      cout << "Yes" << endl;
    }
  }
}
      




Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e6 + 10;
LL fact[N];
LL rfact[N];
void init()
{
	fact[0] = 1;
	for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i%INF;
	rfact[0] = rfact[1] = 1;
	for (int i = 2; i < N; i++) rfact[i] = (INF - INF / i)*rfact[INF%i] % INF;
	for (int i = 2; i < N; i++) rfact[i] = rfact[i] * rfact[i - 1] % INF;
}
LL C(int n, int m)
{
	return fact[n + m] * rfact[m] % INF*rfact[n] % INF;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int h, w, a, b;
	init();
	cin >> h >> w >> a >> b;
	LL ans = C(h - 1, w - 1);
	for (int i = 1; i <= b; i++)
	{
		ans -= C(h - a - 1, i - 1)*C(h - (h - a + 1), w - i) % INF;
	}
	ans %= INF;
	if (ans < 0) ans += INF;
	cout << ans << endl;
	return 0;
}

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

using namespace std;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  Bipartite_Matching(int n, int m)
  {
    graph.resize(n);
    match.assign(m, -1);
    used.assign(n, false);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
  }

  void bfs()
  {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a)
  {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }
};

int main()
{
  int M, N, B[500], R[500];
  while(scanf("%d %d", &M, &N), M) {
    Bipartite_Matching flow(M, N);
    for(int i = 0; i < M; i++) scanf("%d", &B[i]);
    for(int i = 0; i < N; i++) scanf("%d", &R[i]);
    for(int i = 0; i < M; i++) {
      for(int j = 0; j < N; j++) {
        if(__gcd(B[i], R[j]) > 1) flow.add_edge(i, j);
      }
    }
    printf("%d\n", flow.bipartite_matching());
  }
}

Measured memory_bytes: 3704
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// D - Grid Repainting
int H, W;
int sy, sx;
int gy, gx;
char maze[60][60];
int dist[60][60];
int vx[4] = {1, 0, -1, 0};
int vy[4] = {0, 1, 0, -1};
int ans = -1;
int numwhite = 0;
queue<pair<int, int>> q;

void bfs(pair<int, int> startq){
    q.push(startq);

    while(!q.empty()){
        pair<int, int> tmp = q.front();
        q.pop();
        rep(i, 0, 4){
            int nx = tmp.first + vx[i];
            int ny = tmp.second + vy[i]; 
            if(maze[nx][ny] == '.' && dist[nx][ny] == 0){
                q.push(mp(nx, ny));
                dist[nx][ny] = dist[tmp.first][tmp.second] + 1;
            }
        }
    }
}

int main(){
    cin >> H >> W;
    
    rep(i, 0, 60){
        rep(j, 0, 60){
            dist[i][j] = 0;
        }
    }
    repeq(i, 1, H){
        repeq(j, 1, W){
            cin >> maze[i][j];
            if(maze[i][j] == '.') ++numwhite;
        }
    }

    bfs(mp(1, 1));

    if(dist[H][W] != 0){
        ans = numwhite - dist[H][W] - 1;
    }

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




Measured memory_bytes: 256
var
	n,x,ans:int64;
	cnt,p:array[0..55]of int64;
	i:Longint;
procedure f(n,x:int64);
begin
	if n=0 then begin
		if x>0 then inc(ans);
		exit;
	end;
	if x<=1 then exit
	else if x<=1+cnt[n-1]then f(n-1,x-1)
	else if x=2+cnt[n-1]then begin
		inc(ans,p[n-1]+1);
		exit;
	end else if x<=2+cnt[n-1]*2 then begin
		inc(ans,p[n-1]+1);
		f(n-1,x-cnt[n-1]-2);
	end else inc(ans,p[n-1]*2+1);
end;
begin
	read(n,x);
	cnt[0]:=1;
	p[0]:=1;
	for i:=1 to 50 do begin
		cnt[i]:=cnt[i-1]*2+3;
		p[i]:=p[i-1]*2+1;
	end;
	f(n,x);
	writeln(ans);
end.


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

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

  vector<int> a;
  a.push_back(0);
  for (int i = 0; i < n; i++) {
    int w;
    cin >> w;
    a.push_back(w);
  }

  a.push_back(0);
  // for (auto &&w : a) cout << w;

  int s = 0;
  for (int i = 0; i < n + 1; i++) s += abs(a[i + 1] - a[i]);
  vector<int> b;
  // cout << s;
  int t;
  for (int i = 0; i < n; i++) {
    t = s + abs(a[i] - a[i + 2]) - abs(a[i] - a[i + 1]) -
        abs(a[i + 1] - a[i + 2]);
    b.push_back(t);
  }
  for (int i = 0; i < n; i++) {
    // cout << s << endl;
    // cout << b[i] << endl;
    cout << b[i] << endl;
  }
  // cout << endl;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int x, y;
  cin >> x >> y;
  int ans = 0;
  if (x <= 3) {
    ans += 300000 - (x - 1) * 100000;
  }

  if (y <= 3) {
    ans += 300000 - (y - 1) * 100000;
  }

  if (x == 1 && y == 1) {
    ans += 400000;
  }

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

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=200005;
//i_am_noob
int n,ans=0;
string str[maxn];
map<string,int> m;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n;
	rep(n){
		cin >> str[i];
		m[str[i]]++;
		ans=max(ans,m[str[i]]);
	}
	for(map<string,int>::iterator it=m.begin(); it!=m.end(); it++){
		if((*it).second==ans) print1((*it).first);
	}
	return 0;
}

Measured memory_bytes: 25472
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;cin>>N>>K;
  vector<int> height(N),ans(N,1000000001);
  for(int i=0;i<N;i++)cin>>height[i];
  ans[0]=0;
  for(int i=1;i<N;i++){
    for(int j=1;j<=K;j++){
      if(i>=j)ans[i]=min(ans[i],ans[i-j]+abs(height[i]-height[i-j]));
      else break;
    }
  }
  cout<<ans[N-1]<<endl;
}


Measured memory_bytes: 1024
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();
		long a[]=new long[n];
		for(int i=0;i<n;++i){
			a[i]=sc.nextLong();
		}

		Arrays.sort(a);
		long amin[]=new long[n-n/2 +1];
		long amax[]=new long[n/2 +1];
		long sum=0;
		long sum2=0;

		for(int i=0;i<n;++i){
			if(i<n-n/2) {amin[i]=a[i]; sum=sum-2*a[i];}
			else {amax[i-n+n/2]=a[i]; sum=sum+2*a[i];}
		}



		if(n%2==0)sum=sum-amax[0]+amin[n-n/2-1];
		else sum=sum+amin[n-n/2-1]+amin[n-n/2-2];



		for(int i=0;i<n;++i){
			if(i<n/2) {amin[i]=a[i]; sum2=sum2-2*a[i];}
			else {amax[i-n/2]=a[i]; sum2=sum2+2*a[i];}
		}



		if(n%2==0)sum2=sum2-amax[0]+amin[n/2-1];
		else sum2=sum2-amax[0]-amax[1];


		System.out.println(Math.max(sum, sum2));


	}
}

Measured memory_bytes: 51140
class Array
  def merge_sort
    merge = -> l, r do
      ret = []
      for i in 0...size do
        case
        when l.empty?
          $cnt += l.size
          ret << r.shift
        when r.empty?
          ret << l.shift
        when l.first > r.first
          $cnt += l.size
          ret << r.shift
        else
          ret << l.shift
        end
      end
      ret
    end
    if size != 1
      mid = size / 2
      l = self[0...mid].merge_sort
      r = self[mid...size].merge_sort
      merge.(l, r)
    else
      self
    end
  end
end


$cnt = 0
gets
gets.split(' ').map(&:to_i).merge_sort
puts $cnt


Measured memory_bytes: 38452