akhauriyash/Code-Regression huggingface dataset:
/***********************************************************************\
|      _____   ____    _____               _    _   _____   __  __      |
|     |_   _| |  _ \  |  __ \      /\     | |  | | |_   _| |  \/  |     |
|       | |   | |_) | | |__) |    /  \    | |__| |   | |   | \  / |     |
|       | |   |  _ <  |  _  /    / /\ \   |  __  |   | |   | |\/| |     |
|      _| |_  | |_) | | | \ \   / ____ \  | |  | |  _| |_  | |  | |     |
|     |_____| |____/  |_|  \_\ /_/    \_\ |_|  |_| |_____| |_|  |_|     |
|                                                                       |
|                   COMPUTER SCIENCE AND ENGINEERING                    |
|             Noakhali Science and Technology University                |
|                     phn:01751552822                                   |
\***********************************************************************/

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

#define     bip(a)         __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front ///for list
#define     mp             make_pair
#define     is             insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))
#define    c1(a)             cin>>a
#define    c2(a,b)            cin>>a>>b
#define    c3 (a,b,c)        cin>>a>>b>>c
#define    mx2(a,b)        max(a,b)
#define    mx3(a,b,c)        max(max(a,b),c)
#define    mn2(a,b)        min(a,b)
#define    mn3(a,b,c)        min(max(a,b),c)
#define    mf           int main()
#define    rt           return


///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));
mf
{
    int a,b;
    cin>>a>>b;
    cout<<a*b<<endl;
}


Measured memory_bytes: 3608
def eratosthenes_generator():
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


n = int(input())
i = 0
buf = []
for k in eratosthenes_generator():
    if k % 5 == 1:
        buf.append(k)
        i += 1
        if i >= n:
            break
print(*buf)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007 
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	int n;
	cin >> n;
	vector<int> v(n);
	cu(i,0,n)cin >> v[i];
	sort(all(v));
	int sum = 0;
	cu(i,0,n-1)sum+=v[i];
	cout << (sum > v[n-1]?"Yes":"No") << endl;
}


Measured memory_bytes: 256
# # 整数の入力
# a = int(input())
# # スペース区切りの整数の入力
# b, c = map(int, input().split())
# # 文字列の入力
# s = input()
n = int(input())

ans = n

for i in range(1, 2000000):
    if n / i == n // i:
        ans = min(ans, i - 1 + n / i - 1)

print(int(ans))


Measured memory_bytes: 2940
// https://atcoder.jp/contests/abc109/tasks/abc109_b

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

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

    set<string> s;
    string p;
    cin >> p;
    s.insert(p);
    for (int i = 0; i < n - 1; i++)
    {
        string w;
        cin >> w;
        if (s.find(w) == s.end()) // ない
        {
            if (p[p.size() - 1] == w[0])
            {
                s.insert(w);
                p = w;
            }
            else
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3632
s=input()
u=s[0]
t=""
ans=1
l=0
while l<len(s)-1:
  for r in range(l+1,len(s)):
    t+=s[r]
    if t==u:

      if r==len(s)-1:
        l=r
      continue
    else:

      ans+=1
      u=t
      t=""
      l=r
      break
print(ans)

Measured memory_bytes: 3500
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

int main() {
	double N, K; cin >> N >> K;
	double ans = 0;
	for (int i = 1; i <= N; i++) {
		double n = 0, x = i;
		while (K > x) { x *= 2; n++; }
		ans += pow(0.5, n) / N;
	}
	cout << fixed << setprecision(10) << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  // 容器1にはあとA - B入る
  if ((C - (A - B)) > 0) {
    cout << C - (A - B);
  } else {
    cout << 0;
  }

  return 0;
}


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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) (v).begin(), (v).end()
#define sz(v) (int) (v).size()

int main(int argc, char* argv[]) {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int> cnt(n + 1, 1);
  for (int i = 2; i <= n; i++) 
    for (int j = i; j <= n; j += i)
      ++cnt[j];
  ll res = 0;
  for (int i = 1; i <= n; i++) 
    res += 1ll * i * cnt[i];
  cout << res << '\n';
  return 0;
}

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

int main(){
    long double a,b,c;
    cin >> a >> b >> c;
    long double cc=sqrt(a*b);

    if(a+b+2*cc<c) printf("Yes\n");
    else printf("No\n");

}

Measured memory_bytes: 256
n = int(input())
c = [0,0,0,0]
for i in range(n):
  x = input()
  if(x == 'AC'):
     c[0] +=1
  elif(x == 'WA'):
    c[1] +=1
  elif(x == 'TLE'):
    c[2] +=1
  elif(x == 'RE'):
    c[3] +=1
print('AC x '+ str(c[0]))
print('WA x '+ str(c[1]))
print('TLE x '+ str(c[2]))
print('RE x '+ str(c[3]))

Measured memory_bytes: 9188
while True:
	n,m = map(int,input().split())
	if n == 0 and m == 0:	
		break
	a = list(map(int,input().split()))
	a.sort()
	list1 = []
	for i in range(n):
		for j in range(i + 1, n):
		 	price1 = a[i] + a[j]
		 	list1.append(price1)
	list1.sort()
	list2 = list(filter(lambda p: m >= p, list1))


	if list2:
		print(max(list2))
	else:
		print("NONE")	


Measured memory_bytes: 31084
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static bool f = false, t = true;
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        var a = Read.Strs().Select(int.Parse).ToArray();
        Array.Sort(a);
        int s = int.Parse(Read.Str());
        var sa = Read.Strs().Select(int.Parse).ToArray();
        Array.Sort(sa);
        int j = 0;
        for (int i = 0; i < a.Length; i++)
        {
            if (j == s) { break; }
            if (sa[j] == a[i])
            {
                j++;
            }
            
        }
        Console.WriteLine(j == s ? "YES":"NO");Console.ReadLine();
    }

    public static long gcd(long a, long b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static long lcm(long a, long b)
    {
        return a / gcd(a, b) * b;
    }
    public static bool IsPrime(long n)
    {
        if (n < 2) return false;
        if (n == 2) return true;

        for (long i = 2; i < n; i++)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static long Long()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] longs()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
    public static int Int()
    {
        return int.Parse(Console.ReadLine());
    }
    public static int[] ints()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 40108
#include<bits/stdc++.h>
using namespace std;
int main(){
   int a,b,c;
   scanf("%d %d %d",&a,&b,&c);
   int ans;
   if(a == b) ans = c;
   else if(a == c) ans = b;
   else 
    ans = a;
printf("%d\n",ans);
    return 0;
}

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

int main() {
    long long x, y;
    cin >> x >> y;
    int cnt = 1;
    while (x * 2 <= y) {
        x *= 2;
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
num_str = input()
num_list = list(num_str)

hon = [2, 4, 5, 7, 9]
pon = [0, 1, 6, 8]
bon = [3]
how_read = ""
for num in hon:
    if int(num_list[-1]) ==num:
        how_read = "hon"
        break
for num in pon:
    if int(num_list[-1]) ==num:
        how_read = "pon"
        break    
for num in bon:
    if int(num_list[-1]) ==num:
        how_read = "bon"
        break
print(how_read)

Measured memory_bytes: 9208
while True:
	n,x=[int(x) for x in input().split()]
	if(n,x)==(0,0): break
	cnt=0
	for i in range(1,n-1):
		for j in range(i+1,n):
			for k in range(j+1,n+1):
				if i+j+k==x: cnt+=1
	print(cnt)


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

template <typename T>
void print(const T &v);

int main()
{
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d);
    rep(i, d) cin >> p[i] >> c[i];

    // 3進数を作成する
    // 0: 使用しない，1:中途半端に使用する，2:完全に使用する
    int num = pow(3, d);
    int ans = INF;
    for (int i = 0; i < num; i++)
    {
        int cp = i;
        vector<int> bit;
        for (int j = 0; j < d; j++)
        {
            int tmp = cp % 3;
            cp /= 3;
            bit.push_back(tmp);
        }
        map<int, int> mp;
        for (int b : bit)
        {
            mp[b]++;
        }
        if (mp[1] > 1)
        {
            continue;
        }
        int total = 0, pts = 0;
        for (int j = 0; j < d; j++)
        {
            if (bit[j] == 2)
            {
                total += (j + 1) * 100 * p[j] + c[j];
                pts += p[j];
            }
        }
        if (g > total)
        {
            int pt = 0;
            for (int j = 0; j < d; j++)
            {
                if (bit[j] == 1)
                {
                    pt = (((g - total) + ((j + 1) * 100) - 1)) / ((j + 1) * 100);
                    if (pt > p[j])
                    {
                        break;
                    }
                    total += (pt * 100 * (j + 1));
                    pts += pt;
                    break;
                }
            }
        }
        if (total >= g)
        {
            ans = min(ans, pts);
        }
    }
    cout << ans << endl;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


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

typedef int INT_;

#define int long long

const int MAX = 1e5 + 10;

INT_ main()
{
	string a; cin>>a;

	int n=a.length();

	int i=0;
	int removed=0;
	int olds=0;
	while(i<n){
		if(a[i]=='S'){
			int j=i;
			while(a[j]=='S' and j<n) j++;
			if(j==n) break;
			int l=j-i;
			i=j;
			while(a[j]=='T' and j<n) j++;
			int r=j-i;
			i=j;
			if(r > l+olds) {
				removed += 2*min(olds+l,r);
				olds=0;
			}
			else {
				removed += 2*min(olds+l,r);
				olds = olds + l - r;
			}
		}
		else i++;
	}

	cout<<n-removed;
}	

Measured memory_bytes: 640
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {
		solution(args);
		if(in!=null){
			in.close();
		}
	}

	public static void solution(String[] args) throws Exception{

		int X=nextInt();
		int A=nextInt();
		int B=nextInt();

		String ans ="dangerous";
		if(A-B>=0){
			ans="delicious";
		}else{
			if((B-A)<=X){
				ans="safe";
			}
		}


		System.out.println(ans);

	}

	public static boolean isPalindromicStr(String s) {
		int h = 0;
		int t = s.length() - 1;
		while (h <= t) {
			if (s.charAt(h) != s.charAt(t)) {
				break;
			}
			h++;
			t--;
		}
		if (h > t) {
			return true;
		}
		return false;
	}
	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


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

using namespace std;

const int N = 1e3 + 5, M = 1e6 + 6, OO = 0x3f3f3f3f;

long long x, init = 100, cnt;
int main()
{
	cin >> x;
	while(init < x)
	{
		init += (init / 100);
		++cnt;
	}
	cout << cnt << endl;
	return 0;
}

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

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

	vector< vector<int> > grid(2,vector<int>(n));

	for(int i = 0;i<n;i++){
		cin>>grid[0][i];
	}
	for(int i = 0;i < n; i++){
		cin>>grid[1][i];
	}
	for(int i = 1; i < n;i++){
			grid[0][i]+=grid[0][i-1];
	}
	grid[1][0]+=grid[0][0];
	for(int i = 1;i < n;i++){
		grid[1][i]+=max(grid[0][i],grid[1][i-1]);
	}
	cout<<grid[1][n-1];
}

Measured memory_bytes: 256
#include<stdio.h>                                                                                                                      
                                                                                                                                       
int main(void){                                                                                                                        
   int A,B,C;                                                                                                                          
   scanf("%d %d %d",&A,&B,&C);                                                                                                         
                                                                                                                                       
   if((A == B && A != C) || (A == C && A != B)||(B == C && B != A)){                                                                   
      printf("Yes");                                                                                                                   
   }else{                                                                                                                              
      printf("No");                                                                                                                    
   }                                                                                                                                   
   return 0;                                                                                                                           
}  

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

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

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

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

u64 lcm(u64 a, u64 b) { return (a / gcd(a, b)) * b; }

u32 MaxNum = 0xFFFFFFFF;

int main() {
  u64 H, N;
  cin >> H >> N;
  vector<u32> A(N), B(N);
  for (u32 i = 0; i < N; ++i) cin >> A[i] >> B[i];
  u32 MaxI = *max_element(A.begin(), A.end());
  vector<u32> dp(H + MaxI);
  for (u32 i = 1; i < H + MaxI; ++i) dp[i] = MaxNum;
  dp[0] = 0;
  for (u32 d = 0; d < H + MaxI; ++d) {
    if (dp[d] != MaxNum) {
      for (u32 i = 0; i < N; ++i) {
        if (d + A[i] < H + MaxI) {
          if (dp[d + A[i]] != MaxNum)
            dp[d + A[i]] = min(dp[d] + B[i], dp[d + A[i]]);
          else
            dp[d + A[i]] = dp[d] + B[i];
        }
      }
    }
  }
  // ArrayPut(dp);
  cout << *min_element(dp.begin() + H, dp.end()) << endl;

  return 0;
}


Measured memory_bytes: 256
def solve() -> 'max(averages), count(max(averages))':
    from collections import Counter
    from functools import lru_cache
    n, a, b = map(int, input().split())
    v = tuple(sorted(map(int, input().split()), reverse=True))

    def max_ave_x() -> 'max(average),{counts_to_make_max_average}':
        ret = -1
        t = 0
        max_i = set()
        for i, e in enumerate(v, 1):
            t += e
            if a <= i:
                ave = t / i
                if ret < ave:
                    max_i = {i}
                    ret = ave
                elif ret == ave:
                    max_i.add(i)
            if i == b:
                break
        return ret, max_i

    @lru_cache(maxsize=None)
    def combination(n, r):
        if n < r or r < 0:
            return 0
        if r > n - r:
            return combination(n, n - r)
        if r == 0:
            return 1
        if r == 1:
            return n
        return combination(n - 1, r - 1) * n // r

    max_, indices = max_ave_x()

    ret = 0

    c1 = Counter(v)
    for i in indices:
        c2 = Counter(v[:i])
        t = 1
        for chr_ in c2:
            t *= combination(c1[chr_], c2[chr_])
        ret += t

    return max_, ret


print(*solve(), sep='\n')

Measured memory_bytes: 38768
import sys
def input(): return sys.stdin.readline().strip()

def direction_odd(x, y, m):
    """
    m本の腕で(0, 0)から(x, y)に移動する手順を出力する（x + yは奇数を想定）
    """
    ans = ""
    for i in range(m - 1, -1, -1):
        if y < x and y > -x:
            ans += "R"
            x -= 2 ** i
        elif y > x and y > -x:
            ans += "U"
            y -= 2 ** i
        elif y > x and y < -x:
            ans += "L"
            x += 2 ** i
        elif y < x and y < -x:
            ans += "D"
            y += 2 ** i
    return ans

def direction_even(x, y, m):
    if y <= x and y >= -x:
        last = "R"
        x -= 1
    elif y >= x and y >= -x:
        last = "U"
        y -= 1
    elif y >= x and y <= -x:
        last = "L"
        x += 1
    elif y <= x and y <= -x:
        last = "D"
        y += 1
    ans = direction_odd(x, y, m)
    return ans + last


def main():
    N = int(input())
    joint = []
    for _ in range(N):
        x, y = map(int, input().split())
        joint.append((x, y))
    
    """
    まず移動可能な頂点の１つを(x, y)として、(x, y)は\pm (dx, dy)の総和として求まるので
    mod 2でx+yは到着可能な位置に依らず不変量になる。
    なので到着したい位置N子に対してx+yの偶奇がすべて一致するかをまずチェックすれば、それで
    答えが-1になるケースは正答できる。

    問題はこの偶奇がすべて一致している場合だが、実はその場合は必ず題を満たすロボットアームが作れる。
    まず直感として最初に長い腕で移動してからだんだん長さの短い腕で微調整すればよさそうである。
    これを２べきにそろえると、なんと到着可能点がぴったり市松模様になる！！！
    """

    even_odd = {0: 0, 1: 0}
    sum_max = 0
    for x, y in joint:
        even_odd[(x + y) % 2] += 1
        sum_max = max(sum_max, abs(x) + abs(y))
    if even_odd[0] > 0 and even_odd[1] > 0:
        print(-1)
        return

    m = 0
    while (2 ** m - 1 < sum_max): m += 1
    arms = [2 ** i for i in range(m - 1, -1, -1)]
    if even_odd[0] == 0:
        print(m)
        print(" ".join(map(str, arms)))
        for x, y in joint: print(direction_odd(x, y, m))
    if even_odd[0] != 0:
        print(m + 1)
        print(" ".join(map(str, arms)) + " 1")
        for x, y in joint: print(direction_even(x, y, m))
    

if __name__ == "__main__":
    main()


Measured memory_bytes: 41456
#include <stdio.h>
int main(){
     int s[13]={0,1,3,1,2,1,2,1,1,2,1,2,1};
     int a,b;
     scanf("%d %d",&a,&b);
     if(s[a]==s[b])printf("Yes");
     else printf("No");
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<math.h>
int main(void)
{
    int No,count=0;
    double kg,m,BMI;
    while(scanf("%d,%lf,%lf",&No,&kg,&m)!=EOF)
    {
        BMI=kg/(m*m);
        if(BMI>=25)
        {
            printf("%d\n",No);
            count++;
        }
    }
    if(count==0)
        printf("????????????\n");
    return 0;
}

Measured memory_bytes: 628
import java.util.Scanner;
class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int H,W;
        while(true){
            H=sc.nextInt();
            W=sc.nextInt();
            if(H==0&&W==0)break;
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                    if((i+j)%2==0)
                        System.out.print("#");
                    else System.out.print(".");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 36696
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll pw(ll n) { return n*n; }
pll operator - (pll a, pll b) { return pll(a.first-b.first, a.second-b.second); }
ll operator * (pll a, pll b) { return a.first*b.second - b.first*a.second; }
ll ccw(pll a, pll b, pll c) { return a*b + b*c + c*a; }
ll dst(pll a) { return pw(a.first) + pw(a.second); }

const ld PI = acos(ld(0)) * 2;
const int MAXN = 105;

vector<int> CV;

pll P[MAXN];

ld Ans[MAXN];

int N;

void convexhull(vector<int> &V) {
	vector<int> O;
	{
		int mni = (int)(min_element(P+1, P+N+1) - P);
		O.pb(mni);
		for(int i = 1; i <= N; i++) if(i != mni) O.pb(i);
	}
	sort(O.begin()+1, O.end(), [&](int a, int b) {
		ll dt = ccw(P[O[0]], P[a], P[b]);
		return dt ? 0 < dt : P[a] < P[b];
	});

	V.clear();
	for(int v : O) {
		for(; 1 < sz(V) && ccw(P[befv(V)], P[V.back()], P[v]) <= 0; V.pop_back());
		V.pb(v);
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;

	for(int i = 1; i <= N; i++) cin >> P[i].first >> P[i].second;

	convexhull(CV);

	if(sz(CV) <= 2) {
		for(int v : CV) Ans[v] = 0.5;
		for(int i = 1; i <= N; i++)
			cout << Ans[i] << endl;
		return 0;
	}

	for(int i = 0; i < sz(CV); i++) {
		int bi = (i-1 + sz(CV)) % sz(CV);
		int ni = (i+1) % sz(CV);
		bi = CV[bi];
		ni = CV[ni];

		pll va = P[bi] - P[CV[i]], vb = P[ni] - P[CV[i]];
		ll S = abs(va*vb);

		//cout << i << " : " << S << " " << dst(va) << " " <<dst(vb) << endl;

		ld theta = ld(S) / sqrt(dst(va)) / sqrt(dst(vb));
		theta = asin(theta);

		if(dst(va) + dst(vb) >= dst(P[ni]-P[bi]))
			theta = PI - theta;

		Ans[CV[i]] = theta;
	}

	{
		ld sum = 0;
		for(int i = 1; i <= N; i++) sum += Ans[i];

		for(int i = 1; i <= N; i++)
			cout << (Ans[i]/sum) << endl;
	}

	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main (){
    int a,b,c,d,sum1,sum2,sum3;
    while (cin>>a>>b>>c>>d){
        sum1=abs(a-b);
        sum2=abs(b-c);
        sum3=abs(a-c);
        if ((sum1<=d&&sum2<=d) || sum3<=d){
            cout<<"Yes"<<endl;
        }else {
            cout<<"No"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()


int main(){
  int H, N; cin >> H >> N;
  vector <P> AB(N);
  rep(i, N){
    int a, b;cin >> a >> b;
    AB[i] = make_pair(a, b);
  }
  int inf = 1000000000;
  int dp[H + 1];
  rep(i, H + 1) dp[i] = inf;
  dp[0] = 0;
  rep(i, H){
    rep(j, N){
      dp[min(i + AB[j].first, H)] = min(dp[min(i + AB[j].first, H)], dp[i] + AB[j].second);
    }
  }
  cout << dp[H] << endl;
}



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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a != b && b != c && c != a) {
    cout << 3 << endl;
  }
  else if (a == b && b == c) {
    cout << 1 << endl;
  }
  else {
    cout << 2 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
ll INF = 1000000007;

//-----------------//
  #define amin main
//-----------------//

ll exp(ll x, ll n)
{if(n==0) return 1;if(n==1) return x%INF;if(n%2==0) return exp((x*x)%INF,n/2); else return(x*exp((x*x)%INF,n/2))%INF;}


int amin()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t,i,j;
	ll n;
	cin>>n;
	if(n<=599 && n>=400)
		cout<<8<<endl;
	else if(n<=799 && n>=600)
		cout<<7<<endl;
		else if(n<=999 && n>=800)
			cout<<6<<endl;
			else if(n<=1199 && n>=1000)
				cout<<5<<endl;
				else if(n<=1399 && n>=1200)
					cout<<4<<endl;
					else if(n<=1599 && n>=1400)
						cout<<3<<endl;
						else if(n<=1799 && n>=1600)
							cout<<2<<endl;
								else if(n<=1999 && n>=1800)
									cout<<1<<endl;


	


	
	

	
	


	
	return 0;
}

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

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

    int n, x;
    cin >> n >> x;
    vector<int> L(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
    }

    int now = 0, ans = 1;
    for(int i = 0; i < n; i++){
        if(now > x) break;
        now += L[i];
        if(now > x) break;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main(){
  int n,m,s,sum[25]={},ans=0;
  cin >> n >> m;
  rep(i,n){
    rep(j,m){
      cin >> s;
      sum[i] += s;
      ans = max(sum[i],ans);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

int main(void){
	ll n, k;
	cin >> n >> k;
	VecD a(n);
	rep(i, n) cin >> a[i];

	ll l = 0, r = INF;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		ll cnt = 0;
		rep(i, n) cnt += (a[i] - 1) / m;
		if (cnt <= k) r = m;
		else
			l = m;
	}

	co(r);

	return 0;
}


Measured memory_bytes: 6340
#include<stdio.h>
#define max 10000
#define nil -1

struct Node{
  int parent,left,right;
};

struct Node T[max];
int n,D[max],H[max];

void setDepth(int u,int d){
  if(u==nil)return;
  D[u] = d;
  setDepth(T[u].left,d+1);
  setDepth(T[u].right,d+1);
}

int setHeight(int u){
  int h1=0,h2=0;
  if(T[u].left != nil){
    h1 = setHeight(T[u].left)+1;
  }
  if(T[u].right != nil){
    h2 = setHeight(T[u].right)+1;
  }
  return H[u] = (h1>h2?h1:h2);
}

int getSibling(int u){
  if(T[u].parent == nil)return nil;
  if(T[T[u].parent].left != u && T[T[u].parent].left !=nil)
  return T[T[u].parent].left;
  if(T[T[u].parent].right != u && T[T[u].parent].right !=nil)
  return T[T[u].parent].right;

  return nil;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ", T[u].parent);
  printf("sibling = %d, ",getSibling(u) );
  int deg = 0;
  if(T[u].left != nil )deg++;
    if(T[u].right != nil )deg++;
    printf("degree = %d, ",deg );
    printf("depth = %d, ",D[u] );
    printf("height = %d, ",H[u] );

    if(T[u].parent == nil){
      printf("root\n" );
    }
  else if(T[u].left == nil && T[u].right== nil){
    printf("leaf\n" );
  }else {
    printf("internal node\n" );
  }
}

int main(){
  int v,l,r,root = 0,n;
  scanf("%d",&n);

  for(int i = 0;i<n;i++){
    T[i].parent = nil;
  }

  for(int i = 0;i<n;i++){
    scanf("%d %d %d", &v,&l,&r );
    T[v].left = l;
    T[v].right = r;
    if(l!=nil)T[l].parent =v;
    if(r!=nil)T[r].parent = v;
  }

  for(int i = 0;i<n;i++)if(T[i].parent ==nil)root =i;

  setDepth(root,0);
  setHeight(root);

  for(int i ;i <n;i++)print(i);

  return 0;
}



Measured memory_bytes: 2104
import math

def solve():
    shorts_cm, longs_cm, hour, minute = map(int, input().split())

    shorts_degree = (hour * 60 + minute) * 0.5
    longs_degree = minute * 6.0

    degree = abs(longs_degree - shorts_degree)
    degree = min(degree, 360-degree)
    aPower2 = abs(shorts_cm ** 2 + longs_cm ** 2 + (-2 * shorts_cm * longs_cm * math.cos(math.radians(degree))))

    print(math.sqrt(aPower2))

solve()

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

int main() {
    int n;
    cin >> n;
    vector<int> ans(n);
    int a;
    rep(i,n) {
        cin >> a;
        a--;
        ans[a] = i+1;
    }

    rep(i,n) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 3788
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  ll dx = tx - sx, dy = ty - sy;

  string ans = "";
  rep(i, dx) ans += "R";
  rep(i, dy) ans += "U";
  rep(i, dx) ans += "L";
  rep(i, dy) ans += "D";
  ans += "D";
  rep(i, dx+1) ans += "R";
  rep(i, dy+1) ans += "U";
  ans += "L";
  ans += "U";
  rep(i, dx+1) ans += "L";
  rep(i, dy+1) ans += "D";
  ans += "R";

  cout << ans << endl;

  return 0;
}


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

#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
#define ll long long
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 200100;
const long long MX = sqrt(N);
const long long H = 17;
const long long MAGIC = 1000;
const long long mod = 1e9 + 7;

using namespace std;

ll n;
ll k;
ll ans;
ll a[N];
ll b[N];

void dv(int l, int r)
{
        if(l == r){
                return;
        }
        int m = (l + r) / 2;
        dv(l, m);
        dv(m + 1, r);
        vector < ll > v;
        int j = m + 1;
        ll cnt = 0;
        for(int i = l; i <= m; i++){
                while(j <= r && b[j] < b[i]){
                        v.pb(b[j++]);
                }
                cnt += r - j + 1;
                v.pb(b[i]);
        }
        ans += cnt;
        while(j <= r){
                v.pb(b[j++]);
        }
        for(int i = l; i <= r; i++){
                b[i] = v[i - l];
        }
}

void solve()
{
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                a[i] += a[i - 1];
                b[i] = a[i] - k * i;
        }
        dv(0, n);
        cout << ans << endl;
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("landscape.in");
        //fout("landscape.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}


Measured memory_bytes: 6512
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,k,m[200001],z=1,l;
	long long int w[200001]={0};
	cin>>n>>k;
	vector<long long int>a;
	for(long long int i=1;i<=n;i++)
    {
        cin>>m[i];
    }
    a.push_back(1);w[1]=1;z++;
    while(1)
    {
        if(!w[m[a[a.size()-1]]])
        {
            w[m[a[a.size()-1]]]=z++;
            a.push_back(m[a[a.size()-1]]);
        }
        else
        {
            z=z-w[m[a[a.size()-1]]];
            break;
        }
    }
    l=a.size()-z;
    if(k<l)cout<<a[k]<<endl;
    else
    {
        k=k-l;
        k%=z;
        cout<<a[k+l]<<endl;
    }
	return 0;
}


Measured memory_bytes: 8396
function Main(input){ 
var inputs =input.split(" ");
var a = parseInt(inputs[0],10);
var b = parseInt(inputs[1],10);
var count = 0;
count += (a-1);
if(b>=a){
  count += 1;
}
console.log(count);
}
  Main(require('fs').readFileSync('/dev/stdin','utf8'));

Measured memory_bytes: 7372
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h> 
#include <stack>
#include <bitset>
#include <map>
#include <cmath>
#include <climits>
#include <queue>

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

using namespace std;

int main() {
	int s, w;
	scanf("%d %d", &s, &w);
	if (s <= w) printf("unsafe\n");
	else printf("safe\n");
}

Measured memory_bytes: 3688
n,c,k = map(int, input().split())
t = []
for i in range(n):
    t.append(int(input()))
t.sort()

ni,nt,ans = 0,0,0
while 1:
    if ni >= n:
        break
    nt = t[ni]
    for i in range(1,c+1):
        if ni>=n or t[ni] > nt + k:
            break
        ni += 1
    ans += 1
print(ans)


Measured memory_bytes: 7388
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
// #include <pair>

long long
ans(long long k,long long a,long long b){
    long long c = 1;
    if(b <= a+2) return c+k;
    long long nokori = k - (a-c);
    if (nokori <= 1) return c+k;
    c = a;
    if(nokori%2==1){
        nokori--;
        c++;
    }
    c += (b-a)*(nokori/2);
    return c;
}

int main(){
    long long k, a, b;
    long long c;
    std::cin >> k >> a >> b;
    c = ans(k,a,b);
    std::cout << c << std::endl;
	return 0;
}


Measured memory_bytes: 256
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def main():
    N = int(input())
    V_1 = sorted(list(map(int, input().split())))
    logging.info("Hello!")

    total = V_1[0]
    
    for i in range(1, len(V_1)):
        total = (total + V_1[i]) / 2

    print(total)
    
    
if __name__ == "__main__":
    main()


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

N = int(input())
A = list(map(int, input().split()))
A.append(0)
cur = 1000
cnt = 0
for i in range(N):
    if A[i] > A[i+1]:
        # sell
        cur += cnt * A[i]
        cnt = 0
    elif A[i] < A[i+1]:
        # buy
        cnt += cur // A[i]
        cur %= A[i]
print(cur)

Measured memory_bytes: 61748
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
//i64 mod = 998244353;
int int_max = 2147483647;
i64 INF = 1e16;
int max_n = 1e5;


template<typename IntType>
struct union_find_tree {
    union_find_tree(std::size_t sz) : parent(sz, -1) {

    }
    IntType find(IntType x) {
        if (parent[x] < 0) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }
    bool unite(IntType x, IntType y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;

        if (parent[x] > parent[y]) swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
        return true;
    }
    bool is_same(IntType x, IntType y) {
        return find(x) == find(y);
    }
    IntType size(IntType x) {
        return -parent[find(x)];
    }

private:
    std::vector<IntType> parent;
};

int main(int argc, char **argv) {
    i64 n,m;
    cin >> n >> m;
    union_find_tree<i64> uft(n);

    for (int i=0 ; i<m; ++i) {
        i64 a, b;
        cin >> a >> b;
        --a; --b;
        uft.unite(a,b);
    }

    i64 ans{0};
    for (int i=0; i<n; ++i) {
        ans = max(ans, uft.size(i));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4748
#include <bits/stdc++.h>
#define MAX_H 100000
#define MAX_W 100000
#define BASE 1000000007
using namespace std;

long fact_memo[MAX_H + MAX_W + 1];
unordered_map<long, long> inv_memo;

void init(long h, long w) {
    fact_memo[0] = 1;
    fill(fact_memo + 1, fact_memo + h + w + 1, 0);
}

long mod_pow(long x, long k) {
    long ret = 1;
    while (k > 0) {
        if (k & 1)
            ret = (ret * x) % BASE;
        x = (x * x) % BASE;
        k >>= 1;
    }
    return ret;
}

long mod_inv(long x) {
    if (inv_memo.find(x) != inv_memo.end())
        return inv_memo[x];
    return inv_memo[x] = mod_pow(x, BASE - 2);
}

long mod_fact(long x) {
    if (fact_memo[x] > 0)
        return fact_memo[x];
    return fact_memo[x] = (x * mod_fact(x - 1)) % BASE;
}

long mod_combi(long n, long r) {
    long ret = (((mod_fact(n) * mod_inv(mod_fact(r))) % BASE) * mod_inv(mod_fact(n - r))) % BASE;
    return ret;
}

int main() {
    long h, w, a, b;
    cin >> h >> w >> a >> b;
    init(h, w);
    long ans = 0;
    for (long i = 0; i < h - a; i++) {
        ans = (ans + (mod_combi(b + i - 1, i) * mod_combi(w - b + h - i - 2, h - i - 1)) % BASE) % BASE;
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int A,B;
  cin >> A >> B;
  int n = A;
  int sum = 0;
  while (n <= B) {
    int a = n / 10000;
    int b = (n % 10000) / 1000;
    int c = (n % 1000) / 100;
    int d = (n % 100) / 10;
    int e = n % 10;

    if (a == e && b == d) sum++;
    n++;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
<?php
class In {
    private $array = [];
    private $length = 0;
    private $count = 0;

    function __construct()	{
        while (!feof(STDIN)) {
            $str = trim(fgets(STDIN));
            $this->array = array_merge($this->array, explode(' ', $str));
        }
        $this->length = count($this->array);
    }
    
    public function get(int $i){
        $this->array[$i];
    }

    public function next() {
        return $this->array[$this->count++];
    }
    public function hasNext() {
        return $this->count < $this->length;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
    public function nextString() {
        return (string)$this->next();
    }
}

class Out {
    public static function line($str = "") {
        echo $str . PHP_EOL;
    }
}

$in = new In();

$people = $in->nextInt();
$candy = $in->nextInt();
$first = $candy;
$qtys = [];

for ($i = 0; $i < $people; ++$i) {
    $qtys[$i] = $in->nextInt();
}
sort($qtys);

$cnt = 0;
foreach ($qtys as $key => $value) {
    $candy -= $value;
    if($candy == 0){
        ++$cnt;
        break;
    }else if($candy < 0){
        break;
    }else{
        ++$cnt;
    }
}

if($candy > 0){
    --$cnt;
}

Out::line($cnt);

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

using namespace std;
typedef long long ll;

int main(){
ll N; cin >> N;
vector<pair<ll,ll>> a(N); 
for(ll i = 0; i < N; i++){ cin >> a[i].first; a[i].second = i+1;}

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

set<ll> se;

se.insert(0); se.insert(N+1);

ll ans = 0;

for(ll i = 0; i < N; i++){
 ll r = a[i].second; 
 se.insert(r);
 auto itr = se.lower_bound(r);
 auto itr1 = itr; auto itr2 = itr;
 
 itr1--; itr2++;
 
 ll res = (r-*itr1)*(*itr2-r);
 ans += res*a[i].first;
 
 }
 
 cout << ans << endl;
 
 return 0;
 }



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

int main() {
  string s;
  cin >> s;
  bool n=false;
  bool m=false;
  bool w=false;
  bool e=false;
  rep(i,s.size()){
    if(s.at(i)=='N'){
      n=true;
    }
    else if(s.at(i)=='S'){
      m=true;
    }
    else if(s.at(i)=='W'){
      w=true;
    }
    else if(s.at(i)=='E'){
      e=true;
    }
  }
  if((n&&m&&w&&e)||(n&&m&&!w&&!e)||(!n&&!m&&w&&e)){
    cout<<"Yes"<<endl;
  }
  
  else{
    cout<<"No"<<endl;
  }
  
 
}




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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e15
typedef long long ll;

int N;
int N_MAX = 1e5;
vector<int> A(N_MAX, INF);
vector<ll> dp(N_MAX, INF);
//multiset<int> dp;

int main() {
    cin >> N;
    REP(i,N){
        cin >> A[i];
    }
    dp[0] = A[N-1];//広義単調減少列の最長の長さでは？
    FOR(i,1,N){
        auto itr = upper_bound(ALL(dp), A[N-1-i]);
        *itr = A[N-1-i];
    }

    auto len = lower_bound(ALL(dp), INF);
    int ans = len - dp.begin();
    cout << ans << endl;

    // dp.insert(A[0]);
    // FOR(i,1,N){
    //     auto itr = lower_bound(ALL(dp), A[i]);
    //     if(itr != dp.begin()){//更新できるときは貪欲に最大のものを選ぶ
    //         itr--;
    //         dp.erase(itr);
    //     }
    //     dp.insert(A[i]);
    // }

    // cout << dp.size() << endl;


    return 0;
}

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

bool isMultiable(int n){
	int x = n/9;
	if (x*9 == n) return true;
	return false;
}
int main() {
	string s;
	cin >> s;
	int sum = 0;
	int ss = s.size();
	for(int i=0; i < ss; i++){
		sum += s[i]- 48;
	}
	if(isMultiable(sum)) cout << "Yes\n";
	else  cout << "No\n";
}


Measured memory_bytes: 3700