akhauriyash/Code-Regression huggingface dataset:
let rec fold_for a b v f = if a >= b then v else fold_for (a+1) b (f a v) f
let inf = max_int / 100

type edges = { dest: int; mutable cap: int; }

let max_flow start goal g =
  let n = Array.length g in

  let find_flow () =
    let visited = Array.make n false in
    let rec aux x flo =
      if x = goal then flo
      else begin
        visited.(x) <- true;
        fold_for 0 n 0 @@ fun y v ->
          let { dest=y'; cap=c } = g.(x).(y) in
          assert (y = y');
          if v > 0 || visited.(y) || c <= 0 then v
          else begin
            assert (v = 0);
            let v = aux y (min flo c) in
            if v > 0 then begin
              g.(x).(y).cap <- g.(x).(y).cap - v;
              g.(y).(x).cap <- g.(y).(x).cap + v;
            end;
            v
          end
      end
    in
    aux start inf
  in

  let rec loop ans =
    let flo = find_flow () in
    if flo = 0 then ans else loop (ans+flo)
  in loop 0

let () =
  Scanf.scanf "%d %d" @@ fun n m ->
  let g = Array.init n (fun _ -> Array.init n (fun j -> { dest = j; cap = 0 })) in
  for _ = 1 to m do
    Scanf.scanf " %d %d %d" @@ fun u v c -> g.(u).(v).cap <- c
  done;
  Printf.printf "%d\n" (max_flow 0 (n-1) g)



Measured memory_bytes: 4828
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <functional>
#include <ctime>
using namespace std;
#pragma warning(disable: 4996)
long long a[10009], n;
int main() {
	cin >> n;
	a[0] = 2; a[1] = 1; for (int i = 2; i < 88; i++)a[i] = a[i - 1] + a[i - 2];
	cout << a[n] << endl;
	return 0;
}

Measured memory_bytes: 764
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func lib_HasInt(values []int, v int) bool {
	for _, value := range values {
		if value == v {
			return true
		}
	}
	return false
}
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	const initialBufSize = 4096
	const maxBufSize = 1000000
	scanner.Buffer(make([]byte, initialBufSize), maxBufSize)
	scanner.Split(bufio.ScanWords)
	var N int
	scanner.Scan()
	N, _ = strconv.Atoi(scanner.Text())
	A := make([]int, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		A[i], _ = strconv.Atoi(scanner.Text())
	}
	fmt.Println(solve(N, A))
}
func solve(N int, A []int) int {
	if lib_HasInt(A, 0) {
		return 0
	}
	max := int(math.Pow10(18))
	ret := 1
	for _, a := range A {
		if a > max/ret {
			return -1
		}
		ret *= a
	}
	return ret
}


Measured memory_bytes: 5856
h,n=map(int,input().split())
ans=[10**10 for i in range(h+1)]+[0 for i in range(10**4)]
ans[0]=0
for i in range(n):
    a,b=map(int,input().split())
    tmp=0
    while tmp<=h:
        ans[tmp]=min(ans[tmp-a]+b,ans[tmp])
        tmp+=1
print(ans[h])

Measured memory_bytes: 44904
/*
これを入れて実行
g++ code.cpp
./a.out
*/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = { -1, 0, +1, 0 };
int dx4[4] = { 0, +1, 0, -1 };
int dy8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dx8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
	return f.second > s.second;
}

ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}

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

ll nCr(ll n, ll r){
	if (r == 0 || r == n){
		return 1;
	}
	else if (r == 1){
		return n;
	}
	return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}

ll nPr(ll n, ll r){
	r = n - r;
	ll ret = 1;
	for (ll i = n; i >= r + 1; i--) ret *= i;
	return ret;
}

//-----------------------ここから-----------

int main(void){
	int n;
	cin >> n;
	string s;
	cin >> s;

	int cntr = 0;
	int cntb = 0;

	for (int i = 0; i < n; i++){
		if (s[i] == 'R'){
			cntr++;
		} else {
			cntb++;
		}
	}

	if (cntr > cntb){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout << fixed;
  
	int n;
	cin >> n;
	set<int> a;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		a.insert(x);
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		if(a.count(x))cout << x << '\n';
	}
    return 0;
}



Measured memory_bytes: 12540
/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.

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

int mod = 1000000007;
ll dp[100005];;

ll gcd(long long a,long long b){

  if(b == 0)
    return a;
  else return gcd(b,a%b);
}

 int main(){

  int n,a,mini;
  cin>>n;

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

    cin>>a; int counts=0;

     while(a%2 == 0){
        a /= 2;
        counts++;}

     if(i == 0) mini = counts;
     else {
        if(counts < mini)
            mini = counts;
        }
  }

  cout<<mini<<endl;

 return 0;
 }


Measured memory_bytes: 3544
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;


namespace StartFinish
{
    class Program
    {   
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int countNumber = 0;
            int[] array = new int[n];
            for(int i = 0; i < n; i++)
            {
                array[i] = int.Parse(Console.ReadLine());
            }
            for(int i = 0; i < n; i++)
            {
                if (DeterminePrime(array[i]))
                {
                    countNumber++;
                }
            }
            Console.WriteLine(countNumber);
        }

        static bool DeterminePrime(int x)
        {
            if (x == 2)
            {
                return true;
            }
            if (x % 2 == 0)
            {
                return false;
            }
            for(int i = 3; i <= Math.Sqrt(x); i += 2)
            {
                if (x % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

    }
}

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

#define rep(i, n) for (int i=0; i< (n); ++i)
typedef long long ll;
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; }

using namespace std;

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

    int p[n];
    rep(i, n) cin >> p[i];

    //rep(i, n) cout << p[i] << " ";
    //cout << endl;

    int cnt = 0;
    int min = p[0];
    for (int i=0; i< n; i++) {
        if (min >= p[i]) {
            cnt++;
        }
        if (min > p[i])
            min = p[i];
    }
    cout << cnt << endl;
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
)

func main() {
	var (
		a [5]int
		k int
	)
	for i := 0; i < 5; i++ {
		fmt.Scan(&a[i])
	}
	fmt.Scan(&k)

	for j1 := 0; j1 < 5-1; j1++ {
		for j2 := j1 + 1; j2 < 5; j2++ {
			//fmt.Println(a[j2] - a[j1])
			if (a[j2] - a[j1]) > k {
				fmt.Println(":(")
				return
			}
		}
	}
	fmt.Println("Yay!")
}


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

/*
0123
456
78
9
*/
const int data[7][10] = {
						{1, 1, 0, 0, 1, 1, 0, 0, 0, 0},
						{1, 0, 0, 0, 1, 0, 0, 1, 0, 1},
						{1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
						{0, 1, 0, 0, 1, 1, 0, 1, 0, 0},
						{1, 1, 0, 0, 0, 1, 1, 0, 0, 0},
						{1, 0, 0, 0, 1, 1, 0, 0, 1, 0},
						{0, 1, 1, 0, 1, 1, 0, 0, 0, 0}
						};

const int change[10][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}, {0, 1}, {1, 1}, {2, 1}, {0, 2}, {1, 2}, {0, 3}};

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

	while(1){
		int c[15][15];
		for(int i = 0; i < 15; ++i){
			for(int j = 0; j < 15; ++j){
				c[j][i] = 0;
			}
		}

		for(int i = 0; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				char c0;
				if(!(cin >> c0)) return 0;
				c[j][i] = c0 - '0';
			}
		}

		//int m = 0;
		bool check2 = false;
		for(int i = 0; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				for(int k = 0; k < 7; ++k){
					bool check = true;
					for(int l = 0; l < 10; ++l){
						//m = max(m, l);
						if(c[j + change[l][0]][i + change[l][1]] != data[k][l]){
							check = false;
							/*if(i == 4 && j == 4 && k == 1){
								cout << l << endl;
							}*/
							break;
						}
					}
					if(check){
						cout << char('A' + k) << endl;
						check2 = true;
						break;
					}
				}
				if(check2) break;
			}
			if(check2) break;
		}

		//if(!check2) cout << m << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define int long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int mod = 1e9+7;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


int32_t main(){
	#ifndef ONLINE_JUDGE
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif

	int x;
	cin>>x;

	cout<<((x >= 30) ? "Yes" : "No");
	
	return 0;
}

Measured memory_bytes: 3516
import java.util.Scanner;

/**
 * A - AC or WA
 * 高橋君は、プログラミングコンテスト AXC001 に参加しており、問題 A にコードを提出しました。
 * この問題には N 個のテストケースがあり、すべてのテストケースに正解した場合のみ提出は AC となります。
 * 高橋君の提出は、N 個のテストケースのうち M 個のテストケースに正解しました。
 * 高橋君の提出が AC となるか判定してください。
 */
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner( System.in );
        // 入力された整数N
        int n = sc.nextInt();
        // 入力された整数M
        int m = sc.nextInt();

        if( m < n ) {
            System.out.println( "No" );
        }
        else {
            System.out.println( "Yes" );
        }

        sc.close();
    }
}

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x = Integer.parseInt(sc.next());
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());


    String msg ="B";
    if (Math.abs(x-a) < Math.abs(x-b)  ) {
      msg = "A";
    }

    System.out.println(msg);

  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b) {if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b) {if(a<b) a=b;}

template<int MOD>
struct ModInt {
    using M = ModInt;
    long long val;
    ModInt(long long v = 0) {
        set_val(v % MOD + MOD);
    }
    M& set_val(unsigned int v) {
        val = v<MOD ? v : v - MOD;
        return *this;
    }
    explicit operator bool() const {return val != 0;}
    M operator-() const {return M() - *this;}
    M operator+(const M& r) const {return M().set_val(val + r.val);}
    M operator-(const M& r) const {return M().set_val(val + MOD - r.val);}
    M operator*(const M& r) const {return M().set_val((long long) val * r.val % MOD);}
    M operator/(const M& r) const {return *this * r.inverse();}
    M& operator+=(const M& r) {return *this = *this + r;}
    M& operator-=(const M& r) {return *this = *this - r;}
    M& operator*=(const M& r) {return *this = *this * r;}
    M& operator/=(const M& r) {return *this = *this / r;}
    bool operator==(const M& r) const {return val == r.val;}
    M pow(long long n) const {
        M x = *this, r = 1;
        while(n>0) {
            if(n & 1) r *= x;
            x *= x;
            n >> 1;
        }
        return r;
    }
    M inverse() const {
        int a = val, b = MOD, u = 1, v = 0, t;
        while(b>0) {
            t = a/b;
            swap(a-=t*b, b);
            swap(u-=t*v, v);
        }
        return ModInt(u);
    }
    friend istream& operator<<(istream& i, const M& r) {
        long long tmp; i >> tmp;
        r = M(i);
        return i;
    }
    friend ostream& operator<<(ostream& os, const M& r) {
        return os << r.val;
    }
};

template<typename M>
struct BinomialCoefficients {
    vector<M> fact, finv, inv;
    BinomialCoefficients() {};
    BinomialCoefficients(int n) : fact(n+1), finv(n+1), inv(n+1) {
        init(n);
    }
    void init(int n) {
        fact[0] = finv[n] = inv[0] = 1;
        for(int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i;
        finv[n] /= fact[n];
        for(int i = n-1; i >= 0; --i) finv[i] = finv[i+1] * (i+1);
        for(int i = 1; i<= n; ++i) inv[i] = finv[i]*fact[i-1];
    }
    M C(int n, int k) {
        if(n<k || k<0) return 0;
        return fact[n]*finv[n-k]*finv[k];
    }
    M P(int n, int k) {
        if(n<k || k<0) return 0;
        return fact[n]*finv[n-k];
    }
    M H(int n, int k) {
        if(n<0 || k<0) return 0;
        return k == 0 ? 1 : C(n+k-1,k);
    }
};

using mint = ModInt<MOD>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k; cin >> n >> k;
    BinomialCoefficients<mint> bc(n+100);
    REPP(i,k) {
        mint ans = bc.C(n-k+1,i) * bc.C(k-1,i-1);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <stack>
using namespace std;

int main() {
  stack<int>S;
  int a,b,x;
  string s;

  while (cin>>s){
    if (s=="+"){
      a=S.top();S.pop();
      b=S.top();S.pop();
      S.push(a+b);
    }
    else if (s=="-"){
      a=S.top();S.pop();
      b=S.top();S.pop();
      S.push(b-a);
    }
    else if (s=="*"){
      a=S.top();S.pop();
      b=S.top();S.pop();
      S.push(a*b);
    }
    else{
      S.push(atoi(s.c_str()));
    }

  }
  cout<<S.top()<<endl;
}


Measured memory_bytes: 3132
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

#[derive(Debug)]
struct Point {
    x: u32,
    y: u32,
    pair: bool,
}

fn main() {
    let n: usize = read();
    let mut red_points: Vec<Point> = Vec::new();
    let mut pair = 0;
    for _ in 0..n {
        let x = read();
        let y = read();
        red_points.push(Point {
            x: x,
            y: y,
            pair: false,
        });
    }
    red_points.sort_by(|m, n| n.y.cmp(&m.y));
    let mut blue_points: Vec<Point> = Vec::new();
    for _ in 0..n {
        let x = read();
        let y = read();
        blue_points.push(Point {
            x: x,
            y: y,
            pair: false,
        });
    }
    blue_points.sort_by(|m, n| m.x.cmp(&n.x));
    for bp in blue_points.iter_mut() {
        for rp in red_points.iter_mut() {
            if rp.x < bp.x && rp.y < bp.y {
                if !(rp.pair || bp.pair) {
                    rp.pair = true;
                    bp.pair = true;
                    pair += 1;
                }
            }
        }
    }
    println!("{}", pair);
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, p, a[100], e, o;

LL comb(LL x, LL y) {
	if(y == 0) { return 1; }
	LL r = comb(x, y - 1) * (x - (y - 1)) / y;
	return r;
}

int main() {
	cin >> n >> p;
	inc(i, n) { cin >> a[i]; }
	
	inc(i, n) { (a[i] % 2 == 0 ? e : o) += 1; }
	
	LL ans = 0;
	incII(i, 0, o) {
		if(i % 2 == p) { ans += comb(o, i); }
	}
	ans *= (1LL << e);
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))

count = [1000,0]
x = a[0]
for i in range(1,n):
    if a[i] > x:
        d = count[0]//x
        count = [count[0]-d*x, d+count[1]]
    else:
        count = [count[0]+count[1]*x,0]
    x = a[i]
if count[1]:
    count[0] += count[1]*x
print(count[0])

Measured memory_bytes: 61864
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
/******************************************
* AUTHOR : PANDRAVISAM SHIVA SANTHOSH *
* Handle : santhosh_80 *
* INSTITUTION : IIT Palakkad *
******************************************/
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define ll long long int 
#define mod 1000000007
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define S(x) scanf("%d",&(x))
#define P(x) printf("%d\n",(x))
#define Sl(x) scanf("%lld",&(x))
#define Pl(x) printf("%lld\n",(x))
#define pb push_back
#define f first
#define s second


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;cin >> n ;
	set<string> s;
	for(int i = 0; i < n ; i++){
		string s1;cin >>s1;
		s.insert(s1);
	}
	cout << s.size() ;
 	return 0;
}

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

int main()
{
  const int MOD = 1e9 + 7;

  int N, K; cin >> N >> K;
  vector<int> g;
  vector<int> c;

  for (int i = 1; i < sqrt(N); i++)
  {
    g.push_back(i);
    c.push_back(N / i);
  }
  for (int i = floor(sqrt(N)); i >= 1; i--)
  {
    g.push_back(N / i);
    c.push_back(i);
  }

  int num = g.size();
  vector<long long> gnum(num);
  gnum[0] = 1;
  for (int i = 1; i < num; i++)
  {
    gnum[i] = g[i] - g[i - 1];
  }


  vector<long long> dp(num);
  for (int i = 0; i < num; i++) dp[i] = gnum[i];


  for (int i = 1; i < K; i++)
  {
    vector<long long> sumdp(num + 1);
    for (int i = 0; i < num; i++)
    {
      sumdp[i + 1] = (sumdp[i] + dp[i]) % MOD;
    }

    vector<long long> nextdp(num);
    for (int i = 0; i < num; i++)
    {
      nextdp[i] = (gnum[i] * sumdp[num - i]) % MOD;
    }
    dp = nextdp;
  }

  long long ans = 0;
  for (int i = 0; i < num; i++)
  {
    ans = (ans + dp[i]) % MOD;
  }

  cout << ans << endl;
}

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i > 0; i--)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
template <typename Iter> std::string join(Iter begin, Iter end, std::string const& separator){ std::ostringstream result; if (begin != end){ result << *begin++; }; while (begin != end){ result << separator << *begin++; }; return result.str(); }
using namespace std;
typedef long long ll;
void solve() {
  string s, t;
  cin >> s;
  cin >> t;
  bitset<26> s_alphabet, t_alphabet;
  for(char c: s) {
    s_alphabet.set(c - 'a');
    if(s_alphabet.all()) {
      break;
    }
  }
  for(char c: t) {
    t_alphabet.set(c - 'a');
    if(t_alphabet.all()) {
      break;
    }
  }
  if((s_alphabet & t_alphabet) != t_alphabet) {
    cout << -1 << endl;
    return;
  }
  vector<vector<ll>> indices(26, vector<ll>());
  REP(i, s.size()) {
    indices[s[i] - 'a'].push_back(i);
  }
  ll ans = 0;
  for(auto c: t) {
    vector<ll> &cs = indices[c - 'a'];
    ll cur = ans % s.size();
    auto it = lower_bound(cs.begin(), cs.end(), cur);
    if(it == cs.end()) {
      it = cs.begin();
      ans += *it + s.size() - cur + 1;
    } else {
      ans += *it - cur + 1;
    }
  }
  cout << ans << endl;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


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

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

using namespace std;


int main(){
  int n,a,b;
  cin>>n>>a>>b;
  a*=n;
  if(a<b)cout<<a<<endl;
  else cout<<b<<endl;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <complex>

#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define rtr(c, i) for (typeof((c).rbegin()) i = (c).rbegin(); i != (c).rend(); --i)
#define contains(c, x) ((c).find(x) != (c).end())
#define Contains(c, x) (find(all(c), x) != (c).end())
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, (n))
#define To_String to_string< char,std::char_traits<char>,std::allocator<char> >

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

ll dp[31];
int main()
{
	ios_base::sync_with_stdio(0);
	dp[0] = 1;
	REP(i, 1, 31) REP(j, 1, min(4, i+1)) dp[i] += dp[i-j];
	int n;
	while (cin >> n, n) {
		ll t = (dp[n] + 9) / 10;
		ll res = (t + 364) / 365;
		cout << res << endl;
		//cout << res << "(" << dp[n] << ")" << endl;
	}
	return 0;
}

Measured memory_bytes: 0
r, c = map(int, input().split())
a = []
rsum = []

for i in range(r):
  a.append(list(map(int, input().split())))
  a[i].append(sum(a[i]))
  
for i in range(r):
  print(" ".join(list(map(str, a[i]))))
  
csum = []
for j in range(c+1):
  su = 0
  for i in range(r):
    su += a[i][j]
  csum.append(su)
  
print(" ".join(list(map(str, csum))))


Measured memory_bytes: 5696
#include <stdio.h>
#define H 500000

void buildMaxHeap(int*,int);
void maxHeapify(int*,int, int);
int left(int);
int right(int);

int main(){
  int i, k, A[H];

  scanf("%d",&k);
  for(i = 1; i <= k; i++)
    scanf("%d",&A[i]);

  buildMaxHeap(A,k);

  for(i = 1; i <= k; i++)
    printf(" %d",A[i]);
  printf("\n");
  
  return 0;
}

void buildMaxHeap(int* A, int k){
  int i;
  for(i = k/2; i >= 1; i--)
    maxHeapify(A,i,k);
}

void maxHeapify(int* A, int i, int k){
  int l, r, largest, tmp;
  l = left(i);
  r = right(i);
  if(l <= k &&A[l] > A[i])
    largest = l;
  else largest = i;

  if(r <= k && A[r] > A[largest])
    largest = r;

  if(largest != i){
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(A, largest, k);
  }
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i + 1;
}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
int MOD;
ll modex(ll a, ll p, ll m) {
	if (!p) return 1;
	if (p & 1) return a * modex(a, p - 1, m) % m;
	ll v = modex(a, p >> 1, m);
	return v * v % m;
}
vector<int> remainder(vector<int> a, const vector<int>& b) {
	int bs = b.size();
	assert(b[bs - 1]);
	ll invb = modex(b[bs - 1], MOD - 2, MOD);
	for (int i = (int)a.size() - 1; i >= bs - 1; --i) {
		ll mult = (MOD - a[i]) * invb % MOD;
		int j = i;
		a[j] = (a[j] + mult * b[bs - 1 - (i - j)]) % MOD;
		j = i - bs + 2;
		a[j] = (a[j] + mult * b[bs - 1 - (i - j)]) % MOD;
	}
	while (!a.empty() && !a.back()) a.pop_back();
	return a;
}
int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n + 1);
	int g = 0;
	for (int i = n; i >= 0; --i) {
		scanf("%d", &a[i]);
		if (a[i]) g = __gcd(g, abs(a[i]));
	}
	vector<int> ans;
	int p = 2;
	int x = g;
	while (p * p <= x) {
		if (x % p == 0) {
			int cnt = 0;
			do {
				++cnt;
				x /= p;
			} while (x % p == 0);
			ans.push_back(p);
		}
		++p;
	}
	if (x > 1) ans.push_back(x);
	const int MAXN = 10005;
	bitset<MAXN> notp;
	notp[1] = notp[0] = 1;
	for (int i = 2; i < MAXN; ++i)
		if (!notp[i])
			for (int j = i + i; j < MAXN; j += i)
				notp[j] = 1;
	for (int f = 2; f <= n; ++f) {
		if (notp[f] == 1) continue;
		auto b = a;
		for (int i = 0; i <= n; ++i) {
			b[i] = (a[i] % f + f) % f;
		}
		vector<int> r(f + 1);
		r[f] = 1;
		r[1] = f - 1;
		MOD = f;
		auto v = remainder(b, r);
		if (v.empty()) ans.push_back(f);
	}
	sort(ans.begin(), ans.end());
	ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
	for (int a : ans) printf("%d\n", a);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << "\n"
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      cout << '\n';
  }
  return s;
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int a, b;
  cin >> a >> b;
  if (a + b == 15)
    cout << '+' << "\n";
  else if (a * b == 15)
    cout << '*' << "\n";
  else
    cout << 'x' << "\n";
}

Measured memory_bytes: 256
//Mahir Ratanpara (DA-IICT)
#include<bits/stdc++.h>
using namespace std;
#define Ff(i,a,n) for(i=a;i<n;i++)
#define Fr(i,a,n) for(i=a;i>n;i--)
#define ll long long
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef pair<ll, ll>	pa;
typedef vector<ll>		vc;
typedef vector<pa>		vp;
typedef vector<vc>		vvc;
int mpow(int base, int exp); 
void ipgraph(ll n,ll m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vc g[N];

int main() {
    FAST;
    ll t, i, j, k, p, q, r, x, y, u, v, n, m;
    string a,b;
	cin>>a>>b;
	ll ans=0;
	Ff(i,0,a.size())
	{
		if(a[i]!=b[i])
		ans++;
	}
	cout<<ans;
    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(ll n, ll m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 10896
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int mod = 1e5;
int main(){
    vector<int> out;
    while(true){
    int h, w;
    cin >> h >> w;
    if(h == w && h == 0) break;
    vector<vector<vector<int>>> dp(h + 1, vector<vector<int>>(w + 1, vector<int>(4)));
    dp[0][0][2] = 1;
    dp[0][0][3] = 1;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][0]) % mod;
            dp[i + 1][j][3] = (dp[i + 1][j][3] + dp[i][j][0]) % mod;
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % mod;
            dp[i][j + 1][2] = (dp[i][j + 1][2] + dp[i][j][1]) % mod;
            dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i][j][2]) % mod;
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][3]) % mod;
        }
    }
    int ans = 0;
    for(int i = 0; i < 4; i++){
        ans = (ans + dp[h - 1][w - 1][i]) % mod;
    }
    out.push_back(ans);
    }
    for(int i = 0; i < out.size(); i++) cout << out[i] << "\n";
}


Measured memory_bytes: 3672
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <cstring>
#include <algorithm>
#include <set>
#include <climits>
#include <numeric>

//usings
using namespace std;

//type def
typedef long long int64;
typedef pair<int, int> ii;

//consts
const int mod = 1e9 + 7;

//methods
template<typename T>
bool chmax(T& source, const T& compare_to) {
    if(source < compare_to) {
        source = compare_to;
        return true;
    }
    return false;
}

int modpow(int64 base, int n) {
    int64 ret = 1;
    while(n) {
        if(n & 1) ret = ret * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return ret;
}

class Solution {
private:
public:
    vector<int> solve(int n, int x, int y) {
        vector<int> ret(n);
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                int dis = min(j - i, abs(i - x) + abs(j - y) + 1);
                ++ret[dis];
            }
        }
        return ret;
    }
};

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    --x, --y;
    Solution sol;
    auto ret = sol.solve(n, x, y);
    for(int i = 1; i < n; ++i)
        cout << ret[i] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 2147483647;
int prime = 998244353;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);
double PI = 3.14159265358979;
int n;

signed main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int a,b;
    cin >> n >> a >> b;
    vec(x,n);
    input(x,n);
    int ans = 0;
    FOR(i,1,n){
        int tmp = x[i]-x[i-1];
        if(b < a*tmp){
            ans += b;
        }
        else{
            ans += a*tmp;
        }
    }
    print(ans);


    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Measured memory_bytes: 3952
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  k=I()
  s=S()

  n=len(s)
  if n<=k:
    return s
  return s[:k]+'...'

# main()
print(main())


Measured memory_bytes: 10792
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
c = [['#'] + list(input()) + ['#'] for i in range(H)]
c = [['#'] * (W + 2)] + c + [['#'] * (W + 2)]

# 縦方向をy, 横方向をxとする
sx, sy, gx, gy = 1, 1, W, H
ans = 0

visited = [[-1] * (W + 2) for _ in range(H + 2)]
# 未訪問は-1とする。訪問後は距離で上書きしていく

queue = deque([[sy, sx]])
# 次に探索すべきマスを追加していく用

visited[sy][sx] = 1
# スタート地点は訪問済み

shortest = H * W

while queue:
    # queueが空になるまで,つまり訪問すべきマスがなくなるまで行う
    y, x = queue.popleft()
    if [y, x] == [gy, gx]:
        shortest = visited[y][x]
        break

    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + i
        if c[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            # もし上下左右のマスが移動可能かつ未訪問だったら
            visited[new_y][new_x] = visited[y][x] + 1
            # [new_y][new_x]は今いる場所から+1の距離
            queue.append([new_y, new_x])
            # 訪問すべきマスとして追加
else:
    print(-1)
    exit()

print(sum([i.count('.') for i in c]) - shortest)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
	cin>>n;
	int sum=0;
	while(n>=500)
	{
		n-=500;
		sum+=1000;
	}
	while(n>=5)
	{
		n-=5;
		sum+=5;
	}
	cout<<sum;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

int main(void) {
	int h, w, sx, sy, ex, ey;
	cin >> h >> w >> sy >> sx >> ey >> ex;
	sx--, sy--, ex--, ey--;
	vector<string> s(h);
	vector<vector<int>> c(h, vector<int>(w, -1));
	rep(i, 0, h)cin >> s[i];
	deque<pair<int, int>> path, path2;
	path.push_back(make_pair(sx, sy));
	c[sy][sx] = 0;
	const int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
	int C = 0;
	while(1) {
		while (path.size()) {
			auto it = path.front();
			if (it.first == ex && it.second == ey) {
				printf("%d\n", c[ey][ex]);
				return 0;
			}
			path.pop_front();
			rep(i, 0, 4) {
				int tx = it.first + dx[i], ty = it.second + dy[i];
				if (tx < 0 || tx >= w || ty < 0 || ty >= h || c[ty][tx] != -1 && c[ty][tx] <= c[it.second][it.first])continue;
				if (s[ty][tx] == '.') {
					c[ty][tx] = c[it.second][it.first];
					path.push_back(make_pair(tx, ty));
				}
			}
			rep(i, -2, 3) {
				rep(i2, -2, 3) {
					int tx = it.first + i, ty = it.second + i2;
					if (tx < 0 || tx >= w || ty < 0 || ty >= h || c[ty][tx] != -1 && c[ty][tx] <= c[it.second][it.first] + 1)continue;
					if (s[ty][tx] == '.') {
						c[ty][tx] = c[it.second][it.first] + 1;
						path2.push_back(make_pair(tx, ty));
					}
				}
			}
		}
		if (path2.empty())break;
		path = path2;
		path2.clear();
	}
	puts("-1");
	return 0;
}

Measured memory_bytes: 9632
from collections import defaultdict
N = int(input())

d = defaultdict(int)
for i in range(1, N + 1):
    s = str(i)
    f = int(s[0])
    b = int(s[-1])
    d[(f, b)] += 1

ans = 0
for a in range(1, 10):
    for b in range(1, 10):
        ans += d[(a, b)] * d[(b, a)]
print(ans)

Measured memory_bytes: 9404
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=1e9+7;
const int MAXN=2005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
int f[MAXN][MAXN],s[MAXN][MAXN];
inline int upd(int x,int y) { return x+y>=mods?x+y-mods:x+y; }
inline int quick_pow(int x,int y)
{
	if (y<0) return 1;
	int ret=1;
	for (;y;y>>=1)
	{
		if (y&1) ret=1ll*ret*x%mods;
		x=1ll*x*x%mods;
	}
	return ret;
}
int main()
{
	int n=read(),k=read();
	f[0][n+1]=s[0][n+1]=1;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n-i+1;j++) f[i][j]=upd(s[i-1][n+1],mods-s[i-1][j-1]),s[i][j]=upd(s[i][j-1],f[i][j]);
		s[i][n+1]=s[i][n-i+1];
	}
	printf("%d\n",1ll*upd(f[k][1],mods-f[k-1][1])*quick_pow(2,n-k-1)%mods);
	return 0;
}

Measured memory_bytes: 31360
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    c = [i_list() for i in range(3)]

    for i in range(1,3):
        t = c[i][0] - c[0][0]
        if c[i][1] - c[0][1] == t and  c[i][2] - c[0][2] == t:
            pass
        else:
            print("No")
            exit()

    for j in range(1,3):
        t = c[0][i] - c[0][0]
        if c[1][i] - c[1][0] == t and c[2][i] - c[2][0] == t:
            pass
        else:
            print("No")
            exit()
    print("Yes")




if __name__=="__main__":
    main()


Measured memory_bytes: 65912
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
x = readints()
# print(x)
for i in range(5):
    if x[i] == 0:
        print(i+1)


Measured memory_bytes: 72796
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,i;
	string s;cin >> s;
	if(s=="Rainy")
	cout << "Sunny";
	else if(s=="Cloudy")
	cout << "Rainy";
	else
	cout << "Cloudy";
}

Measured memory_bytes: 256
n2 = int(input())

S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
H = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
C = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
D = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

while True:
    try:
        c, n = map(str, input().split())
        n = int(n)
        if c == 'S':
            S.remove(n)
        elif c == 'H':
            H.remove(n)
        elif c == 'C':
            C.remove(n)
        elif c == 'D':
            D.remove(n)
    except:
        break

for i in S:
    print("S {}".format(i))
for i in H:
    print("H {}".format(i))
for i in C:
    print("C {}".format(i))
for i in D:
    print("D {}".format(i))



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

int main() {
  int n = 0;
  cin >> n;
  
  int cnt = 0;
  int MAX = 0;
  
  vector<int> H(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> H[i];
    if (H[i] >= MAX) {
      cnt++;
      MAX = H[i];
    }
  }
  
  cout << cnt << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))


int main(){
    int n;  cin >> n;
    int x=n%10;
    string ans;
    if(x==3) ans = "bon";
    else if(x==2 || x==4 || x==5) ans = "hon";
    else if(x==7 || x==9) ans = "hon";
    else ans = "pon";
    cout << ans << endl;
}

Measured memory_bytes: 3592
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define mem0(a) memset(a,0,sizeof(a))
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int mod=1e9+7;
const int N=1e5+5;
ll a[N];
int main()
{
  ll a,b;
  cin>>a>>b;
  if((a+b)%2==0)
  cout<<(a+b)/2;
  else
  printf("IMPOSSIBLE");
}



Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

long long H, W, A, B;
long long fact[1 << 18], inv[1 << 18];
long long mod = 1000000007;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 33; i++) {
		if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 200000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 200000; i++) inv[i] = modpow(fact[i], mod - 2, mod);
}

long long ncr(long long n, long long r) {
	if (n < r || r < 0) return 0;
	return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}

int main() {
	cin >> H >> W >> A >> B; init();

	long long sum = 0;
	for (int i = 1; i <= H - A; i++) {
		long long v1 = ncr((B - 1) + (i - 1), B - 1);
		long long v2 = ncr((W - B - 1) + (H - i), W - B - 1);
		sum += v1 * v2;
		sum %= mod;
	}
	cout << sum << endl;
	return 0;
}

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

#define pb push_back
     
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    ll q,t;
    cin>>s;
    cin>>q;
    ll k=0;
    string a,b;
    while(q--){
    	cin>>t;
    	ll f;
    	char c;
    	if(t==1)
    		k++;
    	else if(t==2){
    		cin>>f>>c;
    		if((f==1 && k%2==0) || (f==2 && k%2!=0))
    			a.pb(c);
    		else if((f==2 && k%2==0) || (f==1 && k%2!=0))
    			b.pb(c);
    	}
    }
    reverse(a.begin(),a.end());
    a.append(s);
    a.append(b);
    if(k%2!=0)
    	reverse(a.begin(),a.end());
    cout<<a;

	return 0;
}

Measured memory_bytes: 1300