akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdint>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;

typedef pair<int, int> P;

bool ps1(const P &element1, const P &element2)
{ //first昇順
	return element1.first < element2.first;
}
bool ps2(const P &element1, const P &element2)
{ //first降順
	return element1.first > element2.first;
}
bool ps3(const P &element1, const P &element2)
{ //second昇順
	return element1.second < element2.second;
}
bool ps4(const P &element1, const P &element2)
{ //second降順
	return element1.second > element2.second;
}
int digits(int n)
{
	int count = 0;
	while (n > 0)
	{
		n /= 10;
		count++;
	}
	return count;
}
ll combination(ll n, ll r)
{
	if (r * 2 > n)
		r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i)
	{
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}
vector<int> divisor(int n)
{
	vector<int> value;
	FOR(i, 1, pow(n, 0.5) + 1)
	{
		if (i <= sqrt(n))
		{
			if (n % i == 0)
			{
				value.push_back(i);
				if (i * i != n)
				{
					value.push_back(n / i);
				}
			}
		}
	}
	return value;
}

int main()
{
	string s;
	cin>>s;
	int w;
	cin>>w;
	string ans;
	int n=s.size();
	rep(i,n){
		if(i%w==0){
			ans.push_back(s[i]);
		}
	}
	cout<<ans<<endl;
}


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

int main(){
  char a;
  cin >> a;
  if('A'<=a && a<='Z') cout << 'A' << endl;
  else cout << 'a' << endl;
  return 0;
}


Measured memory_bytes: 3572
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    

    class ClassMain {

        public static bool isKaibun(int n) {
            string str = n + "";
            char[] chrs = str.ToCharArray();
            for (int i = 0; i < chrs.Length/2; i++) {
                if (chrs[i] != chrs[chrs.Length - 1 - i]) {
                    return false;
                }
            }
            return true;
        }
        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int n = int.Parse(line);
                if (n == 0) { break; }
                if (isKaibun(n)) { Console.WriteLine(n); break; }
                for (int i = 1; ; i++) {
                    if (isKaibun(n - i)) { Console.WriteLine(n - i); break; }
                    if (isKaibun(n + i)) { Console.WriteLine(n + i); break; }
                }
                
            }
        }

    }

    
}

Measured memory_bytes: 5616
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

constexpr int N = 8192;
int p[N];
ll c[N];
vl v;

int main(){
	int n, k; scanf("%d%d", &n, &k);
	FOR(i, 1, n+1) scanf("%d", p+i);
	FOR(i, 1, n+1) scanf("%lld", c+i);
	ll ans = LLONG_MIN;
	FOR(i, 1, n+1){
		ll sm = 0;
		v.clear(); v.EB(0);
		for(int j = i;;){
			j = p[j];
			v.EB(sm += c[j]);
			if(j == i) break;
		}
		int m = v.size() - 1;
		REP(i, m){
			if(k < i) continue;
			int s = i ? 0 : 1, t = (k-i)/m;
			if(s > t) continue;
			LAR(ans, v[i] + v.back() * s);
			LAR(ans, v[i] + v.back() * t);
		}
	}
	printf("%lld\n", ans);
}





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

long long gcd(long long x, long long y)
{
    long long r;
    while ((r = x % y) != 0) {
        x = y;
        y = r;
    }
    return y;
}

long long lcm(long long  x, long long y)
{
    return (x * y / gcd(x, y));
}

int main() {
	long long x, y, l;
	long long i, a;
	scanf("%lld %lld", &x, &y);
	a = -1;
	l = lcm(x, y);

	for (i = x; i <= l; i += x) {
		if (i % y != 0) {
			a = i;
			break;
		}
	}
	if (a > 100000000000000000) {
		a = -1;
	}

	printf("%lld", a);
	return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  5 09:20:15 2019

@author: maezawa
"""

n, maxw = list(map(int, input().split()))
v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1, n+1):
    vi, wi = list(map(int, input().split()))
    v[i] = vi
    w[i] = wi
    
dp = [0]*(maxw+1)
for i in range(1,maxw+1):
    candidates = [dp[i-w[j]]+v[j] 
                    for j in range(n+1) if i-w[j] >= 0]
    dp[i] = max(candidates)
    #print(i, *dp, sep = '\n')
print(dp[maxw])


Measured memory_bytes: 5932
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i,n)cin >> a[i];
    vector<int>dp(n,INT_MAX);
    reverse(a.begin(),a.end());
    rep(i,n)*upper_bound(dp.begin(),dp.end(),a[i]) = a[i];
    cout << lower_bound(dp.begin(),dp.end(),INT_MAX) - dp.begin() << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define M 10001

int compare(int S1[],int n,int z){
  int j;
  S1[n]=z;
  for(j=0;S1[j]!=z;j++){
  }
    return j!=n;
}

int main(){
  int i,n,q,z,S1[M];
  int match=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S1[i]);
  }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&z);
    if(compare(S1,n,z)){
      match++;
    }
  }

  printf("%d\n",match);

  return 0;
}




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

int main() {
    string s;
    cin >> s;
    for(int i=0; i<3; i++){
        if(s[i] == '9'){
            s[i] = '1';
        }else if(s[i] == '1'){
            s[i] = '9';
        }
    }

    cout << s << endl;
    return 0;
}

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

int main()
{
	long long A[100100];
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		long long a;
		cin >> a;
		if (a == 0)
		{
			cout << "0" << endl;
			return 0;
		}
		else
		{
			A[i] = a;
		}
	}

	long long ans = 1;
	for (int i = 0; i < N; i++)
	{
		if (A[i] <= 1000000000000000000 / ans)
		{
			ans *= A[i];
		}
		else
		{
			cout << "-1" << endl;
			return 0;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4400
import sys
s = input()
k = int(input())
n = len(s)
if n==1:
    print(k//2)
    sys.exit()
if n==2:
    print(k if s[0]==s[1] else 0)
    sys.exit()
i = 1
change = [0, 0]
same = True
while i<n:
    if s[i-1]==s[i]:
        if i==n-1:
            same = False
        change[0] += 1
        i += 1
    i += 1
if s[0]!=s[-1]:
    same = False
if not same:
    print(change[0]*k)
    sys.exit()
i = 2
change[1] = 1
same = True
while i<n:
    if s[i-1]==s[i]:
        if i==n-1:
            same = False
        change[1] += 1
        i += 1
    i += 1
if same:
    print(change[0]+change[1]*(k-1))
else:
    print(change[0]*((k+1)//2)+change[1]*(k//2))

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

int main() {
    int N, M; cin >> N >> M;
    vector<int> A(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for(int k = 1; k <= M; ++k) {
        for(int i = 0; i + 1 < N; ++i) {
            if((A[i] % k) > (A[i + 1] % k)) {
                swap(A[i], A[i + 1]);
            }
        }
    }
    for(auto x : A) {
        cout << x << endl;
    }
}



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

const int MAX_M = 1000, MAX_N = 1000;
string flag[MAX_M];
string Emb[2];

bool lu(int i, int j){ return flag[i][j] == Emb[0][0]; }
bool ru(int i, int j){ return flag[i][j + 1] == Emb[0][1]; }
bool ld(int i, int j){ return flag[i + 1][j] == Emb[1][0]; }
bool rd(int i, int j){ return flag[i + 1][j + 1] == Emb[1][1]; }

int main(){
	int M, N;
	int table[MAX_M][MAX_N];
	int res, plus, n;
	for(int i = 0; i < MAX_M; i++){
		for(int j = 0; j < MAX_N; j++){
			table[i][j] = 0;
		}
	}
	
	cin >> M >> N;
	for(int i = 0; i < M; i++){
		cin >> flag[i];
	}
	for(int i = 0; i < 2; i++){
		cin >> Emb[i];
	}
	
	res = 0;
	for(int i = 0; i < M - 1; i++){
		for(int j = 0; j < N - 1; j++){
			if(lu(i, j) && ru(i, j) && ld(i, j) && rd(i, j)) res++;
			else{
				if(ru(i, j) && ld(i, j) && rd(i, j)) table[i][j] = 1;
				else if(lu(i, j) && ld(i, j) && rd(i, j)) table[i][j] = 2;
				else if(lu(i, j) && ru(i, j) && rd(i, j)) table[i][j] = 3;
				else if(lu(i, j) && ru(i, j) && ld(i, j)) table[i][j] = 4;
				else table[i][j] = -1;
			}
		}
	}
	
	plus = 0;
	for(int i = 0; i < M - 1; i++){
		for(int j = 0; j < N - 1; j++){
			n = 0;
			if(table[i][j] == 1){
				n = 1;
				if(j > 0){
					if(table[i][j - 1] == 2 && Emb[0][0] == Emb[0][1]) n++;
					else if(table[i][j - 1] == 0) n--;
				}
				if(i > 0){
					if(table[i - 1][j] == 3 && Emb[0][0] == Emb[1][0]) n++;
					else if(table[i - 1][j] == 0) n--;
				}
				if(i > 0 && j > 0){
					if(table[i - 1][j - 1] == 3 && Emb[0][0] == Emb[1][1]) n++;
					else if(table[i - 1][j - 1] == 0) n--;
				}
			}
			else if(table[i][j] == 2){
				n = 1;
				if(j < N - 2){
					if(table[i][j + 1] == 1 && Emb[0][0] == Emb[0][1]) n++;
					else if(table[i][j + 1] == 0) n--;
				}
				if(i > 0 && j < N - 2){
					if(table[i - 1][j + 1] == 3 && Emb[1][0] == Emb[0][1]) n++;
					else if(table[i][j + 1] == 0) n--;
				}
				if(i > 0){
					if(table[i - 1][j] == 4 && Emb[1][1] == Emb[0][1]) n++;
					else if(table[i - 1][j] == 0) n--;
				}
			}
			else if(table[i][j] == 3){
				n = 1;
				if(i < M - 2){
					if(table[i + 1][j] == 1 && Emb[0][0] == Emb[1][0]) n++;
					else if(table[i + 1][j] == 0) n--;
				}
				if(j > 0 && i < M - 2){
					if(table[i + 1][j - 1] == 2 && Emb[0][1] == Emb[1][0]) n++;
					else if(table[i + 1][j - 1] == 0) n--;
				}
				if(j > 0){
					if(table[i][j - 1] == 4 && Emb[1][1] == Emb[1][0]) n++;
					else if(table[i][j - 1] == 0) n--;
				}
			}
			else if(table[i][j] == 4){
				n = 1;
				if(i < M - 2 && j < N - 2){
					if(table[i + 1][j + 1] == 1 && Emb[0][0] == Emb[1][1]) n++;
					else if(table[i + 1][j + 1] == 0) n--;
				}
				if(i < M - 2){
					if(table[i + 1][j] == 2 && Emb[0][1] == Emb[1][1]) n++;
					else if(table[i + 1][j] == 0) n--;
				}
				if(j < N - 2){
					if(table[i][j + 1] == 3 && Emb[1][0] == Emb[1][1]) n++;
					else if(table[i][j + 1] == 0) n--;
				}
			}
			
			plus = max(plus, n);
		}
	}
	
	cout << res + plus << endl;
	
	return 0;
}

Measured memory_bytes: 6160
#include<stdio.h>

int main(){
    
    int a,b;
    
    scanf("%d %d",&a,&b);
    
    if(a<b){
        printf("a < b\n");
    }else if(a>b){
        printf("a > b\n");
    }else{
        printf("a == b\n");
    }
    
    return 0;
}


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

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()  
{ 
    FAST_INP;
    long long n,a,b,c,q;
    cin >> n;
    set<long long> num;
    map<long long,long long> m;
    long long sum=0;
    for(int i=0;i<n;i++){
    	cin >> a;
		num.insert(a);
		m[a]++;
		sum+=a;
	}
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> b >> c;
		sum-=(m[b]*b);
		m[c]+=m[b];
		sum+=(m[b]*c);
		m[b]=0;
		cout << sum << endl;
	}
    return 0;
} 


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

int is_check(int n, char *s)
{
	int i = 0;
	while (i < n)
	{
		if (s[n] == s[i])
			return 0;
		i++;
	}
	return 1;
}

int		main(void)
{
	char s[27];
	scanf("%s", s);
	int i = 0;
	int len = strlen(s);
	while (s[i])
	{
		if (is_check(i, s) == 0)
		{
			printf("no\n");
			return 0;
		}
		i++;
	}
	printf("yes\n");
	return 0;
}

Measured memory_bytes: 128
use std::io::BufRead;
fn main() {
    let stdin = std::io::stdin();
    let mut lines: Vec<Vec<i64>> = stdin
        .lock()
        .lines()
        .map(|l| {
            l.unwrap()
                .split_whitespace()
                .map(|w| w.parse().unwrap())
                .collect()
        })
        .collect();
    let (n, k, mut al, mut fl) = (lines[0][0], lines[0][1], lines.remove(1), lines.remove(1));
    if al.iter().sum::<i64>() <= k {
        println!("0");
        return;
    } else {
        al.sort();
        al.reverse();
        fl.sort();
        let mut list: Vec<_> = al.iter().zip(fl.iter()).collect();
        list.sort();
        list.reverse();
        let mut lp:i64 = 1;
        let mut rp:i64 = al.iter().max().unwrap()*fl.iter().max().unwrap();
        // match list[0] {
        //     (a, f) => rp = a * f,
        // }
        let mut mp:i64 = (lp + rp) / 2;
        while (lp!=mp)||(mp!=rp) {
            let cnt: i64 = list
                .iter()
                .filter(|&&(a, f)| (a * f) > mp)
                .map(|&(a, f)| a - (mp / f))
                .sum();
            // let mut cnt =0;
            // for &(a, f) in &list {
            //     if (a * f) > mp {
            //         cnt += a - (mp / f);
            //     } else {
            //         break;
            //     }
            // }
            if k < cnt {
                lp = mp + 1;
            } else {
                rp = mp;
            }
            mp = (lp + rp) / 2;
        }
        println!("{}", mp);
    }
}


Measured memory_bytes: 15072
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
#include <utility>
#include<iomanip>
// #include <numeric>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector<vector<ll>> vvint;
typedef vector<string> vstring;
typedef vector<vector<string>> vvstring;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<long double> vdouble;
typedef vector<vector<long double>> vvdouble;
typedef vector<vector<vector<long double>>> vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define LLONG_MAX 9223372036854775807
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define DIVIDER 1000000007


//
// struct Node{
//   vint children;
//   ll index;
//   ll prop;
// };
// struct edge{ll to; ll cost;};



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

// ll X,Y,Z,K;
// ll pmax = 30000000000;
// vint A,B,C;




// struct UnionFind {
//     vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
//
//     UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
//         for(int i = 0; i < N; i++) par[i] = i;
//     }
//
//     int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
//         if (par[x] == x) return x;
//         return par[x] = root(par[x]);
//     }
//
//     void unite(int x, int y) { // xとyの木を併合
//         int rx = root(x); //xの根をrx
//         int ry = root(y); //yの根をry
//         if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
//         par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
//     }
//
//     bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };
//
// vint divisor(ll n){ // nの約数
//   vint ret;
//   for(ll i=1;i*i<=n;i++){
//     if(n%i == 0){
//       ret.pb(i);
//       if(i*i!=n) ret.pb(n/i);
//     }
//   }
//   vsort(ret);
//   return ret;
// }
//
// ll get_digits_num(ll n){
//   ll ret=0;
//   while(n){
//     n/=10;
//     ret++;
//   }
//   return ret;
// }

ll gcd(ll m, ll n){
  if(m<n) swap(m,n);
  if(n==0) return m;
  return gcd(n, m%n);
}

int main() {
  cout<<fixed<<setprecision(10);

  ll n;cin>>n;
  vint h(n+2,0);rep(i,n)cin>>h[i+1];

  ll ans = 0;

  rep(i,100){
    ll delta = 0;
    rep(j,n){
      if(h[j+1]>0 && h[j+2]<=0) delta++;
    }
    ans+=delta;
    rep(j,n){
      h[j+1]--;
    }


  }

  cout << ans << endl;



}

















//


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

 int main() {
   int n, k;
   cin >> n >> k;
   int count;
   for (int i = 1; n != 0; i++) {
     n = n / k;
     count = i;
   }
   cout << count << '\n';
 }


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

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a));

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const long double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;


LL a,b;

bool ok(LL x)
{
	if(x>2*b)return 0;
	LL w = b-x;
	LL aa = a+w/2;
//	cerr<<aa<<endl;
	return aa>=x;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);

	cin>>a>>b;
	b/=2;
	LL d = max(0ll,(b-a)/2);
	cout<<min(a+d,b);
	return 0;
cerr<<ok(234530);
return 0;
	LL l=0,r=1000000000005ll;

	while(l+1<r)
	{
		LL x = (l+r)/2;
		if(ok(x))
		{
			l=x;
		}else
		{
			r=x;
		}
	}

	cout<<l;
}



Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let s: String = read();
    let t: String = read();

    let si: Vec<char> = s.chars().collect();
    let ti: Vec<char> = t.chars().collect();

    let mut dp = vec![vec!["".to_string(); t.len()+1]; s.len()+1];

    // s の i 番目の文字まで考えて、t の j番目の文字までの中での部分文字列の長さを最大化
    for i in 0..si.len() {
        for j in 0..ti.len() {
            dp[i+1][j+1] = dp[i][j+1].clone();
            if si[i] == ti[j] {
                if dp[i][j].len() + 1 > dp[i+1][j+1].len(){
                    let mut s_new2 = dp[i][j].clone();
                    s_new2.push(si[i]);
                    dp[i+1][j+1] = s_new2;
                }
            }
            if dp[i+1][j].len() > dp[i+1][j+1].len() {
                dp[i+1][j+1] = dp[i+1][j].clone();
            }
            dp[i][j] = "".to_string();
            // println!("{} {} {}", i+1, j+1, dp[i+1][j+1]);
        }
    }

    println!("{}", dp[si.len()][ti.len()]);
}


Measured memory_bytes: 280828
h1, m1, h2, m2, k = map(int,input().split())
 
h=h2 - h1
if h < 0:
    h = 24+h
    m=m2 - m1
    du=h*60+m-k
elif h == 0:
    if m1 < m2:
        du = m2-m1-k
    else:
        du = 24*60 +(m2-m1)-k
else:
    du = h*60+(m2-m1)-k
        
print(du)

Measured memory_bytes: 9192
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for j in d[1]:
    if N in d[j]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Measured memory_bytes: 48144
while True:
  H, W = map(int, input().split())
  if H == 0 and W == 0:
    break
  for j in range(H):
    for i in range(W):
      if i == 0 or j == 0 or i == W-1 or j == H-1:
        print('#', end="")
      else:
        print('.', end="")
    print()
  print()


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

int main(){ 
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, a[100001];
    cin >> n;
    vector<int> dp(n, INT_MAX);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    dp[0] = 0;
    for(int i = 0; i < n; ++i){
        if(i + 1 < n)
            dp[i + 1] = min(dp[i + 1], dp[i] + abs(a[i] - a[i + 1]));
        if(i + 2 < n)
            dp[i + 2] = min(dp[i + 2], dp[i] + abs(a[i] - a[i + 2]));
    }
    cout << dp[n - 1] << '\n';
    return 0;
}


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

const int CN = 310;
const int INF = 0x3f3f3f2f;

int n,m,l,q,f[CN][CN],g[CN][CN];

int main()
{
	memset(f, 0x3f, sizeof(f));
	memset(g, 0x3f, sizeof(g));
	
	scanf("%d%d%d",&n,&m,&l);
	while(m--){
		int a,b,c; scanf("%d%d%d",&a,&b,&c);
		f[a][b] = f[b][a] = c;
	}
	
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        if(f[i][j] <= l) g[i][j] = 1;
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
	
	scanf("%d",&q);
	while(q--){
		int x,y; scanf("%d%d",&x,&y); printf("%d\n",g[x][y] < INF ? g[x][y] - 1 : -1);
	}
}

Measured memory_bytes: 1280
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        long[] a = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        long ans = 0;
        for(long i = 0; i < n; i++)
        {
            ans += a[i] - 1;
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
#include <iterator>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(v) begin(v), end(v)
#define rreps(i, a, n) for (ll i = (a); i <= (ll)(n); ++i)
#define rrep(i, n) rreps(i, 0, n)
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define each(i, n) for (auto&& i : n)
#define fill(x, y) memset(x,y,sizeof(x))
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template <typename T> inline void print(const T& x) {cout << x << '\n';}

signed main()
{ 
  int n; cin>>n;
  string s; cin>>s;
  int ans=0;
  reps(i,1,n)
  {
    map<char, int> a, b;
    rep(j,i)
    {
      a[s[j]]++;
    }
    reps(j,i,n)
    {
      b[s[j]]++;
    }
    int tmp=0;
    rep(j,26)
    {
      if(a['a'+j]>0&&b['a'+j]>0) tmp++;
    }
    ans=max(ans,tmp);
  }
  print(ans);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"\n"
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=3e5+10,mod=1e9+7,INF=0x3f3f3f3f;

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


Measured memory_bytes: 3632
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	k := scanInt()

	as := scanInts(n)

	sort.Ints(as)



	facInit(n)

	ans := 0

	for i := 0; i < n; i++ {
		if i+1 >= k {
			ans = (ans + comb(i,k-1)*as[i]%mod)%mod
		}
		if n-i >= k {
			ans = (ans - comb(n-1-i,k-1)*as[i]%mod)%mod
		}
	}

	fmt.Println(ans)
}

const mod = 1000000007

var (
	fac []int
	ifac []int
)

func facInit(n int) {
	fac = make([]int,n+1)
	ifac = make([]int,n+1)
	
	mpow := func (x,n int) int {
		a := 1
		for {
			if n&1 == 1 {
				a = a*x %mod
			}
			x = x*x %mod
			n = n >> 1
			if n == 0 {
				break
			}
		}
		return a
	}

	fac[0] = 1
	ifac[0] = 1
	for i := 0; i < n; i++ {
		fac[i+1] = fac[i]*(i+1)%mod
		ifac[i+1] = ifac[i]*mpow(i+1,mod-2)%mod
	}
}

func comb(a,b int) int {
	if a == 0 && b == 0 {
		return 1
	}
	return (fac[a]*ifac[b]%mod)*ifac[a-b]%mod
}


Measured memory_bytes: 4736
n = int(input())

res = 0
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        if i<n//i-1:
            res += n//i-1
        if i**2 == n:
            continue
        if n//i<i-1:
            res += i-1
print(res)


Measured memory_bytes: 40556
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
	
string s;

int main()
{
	cin >> s;

	for (int i = 0; i < 3; i++) {
		if (s[i] == 'a') break;
		if (i == 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'b') break;
		if (i == 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'c') break;
		if (i == 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;

    return 0;
}



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

int dfs(int i, int a, int b, int c, int N, int A[], int L[]) {
	if (i == N) {
		if (a == 0 || b == 0 || c == 0) {
			return 10 << 9;
		}
		return (abs(a - A[0]) + abs(b - A[1]) + abs(c - A[2]) - 30);
	}
	int ret1 = dfs(i + 1, a, b, c, N, A, L);
	int ret2 = dfs(i + 1, a + L[i], b, c, N, A, L) + 10;
	int ret3 = dfs(i + 1, a, b + L[i], c, N, A, L) + 10;
	int ret4 = dfs(i + 1, a, b, c + L[i], N, A, L) + 10;
	return min(ret1, min(ret2, min(ret3, ret4)));
}

int main() {
	int N;
	cin >> N;
	int A[3];
	cin >> A[0] >> A[1] >> A[2];
	int L[8] = { 0 };
	for (int i = 0; i < N; ++i) {
		cin >> L[i];
	}
	// L[i] を A[0]に使うか、A[1]に使うか、A[2]に使うか、使わないかの4通り
	int ans = dfs(0, 0, 0, 0, N, A, L);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
using namespace std;
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

int main(){
  int N;
  cin>>N;
  int count =0;
  for(int i=0 ; i <N; i++){
    if(ketasuu(i+1) %2 ==1 ){
      count ++;
    }
  }
  cout<<count<<endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
	int time=0,all;
	for(int i=0;i<4;i++)
	{
		scanf("%d",&time);
		all+=time;
	}
	printf("%d\n%d\n",all/60,all%60);
	return 0;
}


Measured memory_bytes: 3220
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

typedef vector<string> vs;
typedef vector<int> vi;

#define rep(i,b) loop(i,0,b)
#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define all(c) (c).begin(), (c).end()

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

int h,w;
inline bool in(int x, int y){
    return 0<=x && 0<=y && x<w && y<h;
}

vi id{0,1,2,3};
bool solve(vs const& g1, vs const& g2){
    int sx1, sy1, sx2, sy2;
    rep(i,h)rep(j,w){
        if(g1[i][j]=='L'){
            sx1=j;sy1=i;
        }
        if(g2[i][j]=='R'){
            sx2=j;sy2=i;
        }
    }
    queue<vi> q;
    static bool vis[64][64][64][64];
    memset(vis,0,sizeof(vis));
    q.push(vi{sx1,sy1,sx2,sy2});
    while(q.size()){
        vi s=q.front();q.pop();
        int x1=s[0],y1=s[1],x2=s[2],y2=s[3];
        if(vis[x1][y1][x2][y2])continue;
        vis[x1][y1][x2][y2]=true;
        if(g1[y1][x1]=='%' && g2[y2][x2]=='%') return true;
        if(g1[y1][x1]=='%' || g2[y2][x2]=='%') continue;

        random_shuffle(all(id));
        rep(i,4){
            int d=id[i];
            int nx1=x1+dx[d],ny1=y1+dy[d];
            int nx2,ny2;
            if(d&1){
                nx2=x2+dx[d],ny2=y2+dy[d];
            }else{
                nx2=x2-dx[d],ny2=y2-dy[d];
            }
            if(!in(nx1,ny1) || g1[ny1][nx1]=='#')nx1=x1,ny1=y1;
            if(!in(nx2,ny2) || g2[ny2][nx2]=='#')nx2=x2,ny2=y2;
            q.push(vi{nx1,ny1,nx2,ny2});
        }
    }
    return false;    
}

int main(){
    srand(time(0));
    while(cin>>w>>h && w|h){
        vs g1(h), g2(h);
        rep(i,h) cin>>g1[i]>>g2[i];
        vs ans{"No","Yes"};
        cout << ans[solve(g1,g2)] << endl;
    }
}

Measured memory_bytes: 29872
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz size()
#define ll long long
#define all(_v) _v.begin(), _v.end()

const int MAXN = 2e3 + 10;
ll n, x, y;
vector <int> g[MAXN];
ll cnt[MAXN];
vector <ll> bfs(int v) {
    vector <ll> d(n + 3);
    for(int i = 1; i <= n; ++i) d[i] = 1e9;
    d[v] = 0;
    queue <int> q;
    q.push(v);
    while(!q.empty()) {
        int fr = q.front();
        q.pop();
        for(int i = 0; i < g[fr].sz; ++i) {
            int to = g[fr][i];
            if(d[to] > d[fr] + 1) {
                d[to] = d[fr] + 1;
                q.push(to);
            }
        }
    }
    return d;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> x >> y;
    for(int i = 1; i < n; ++i) g[i].pb(i + 1), g[i + 1].pb(i);
    g[x].pb(y);
    g[y].pb(x);
    for(int i = 1; i <= n; ++i) {
        vector <ll> tmp = bfs(i);
        for(int j = i + 1; j <= n; ++j) cnt[tmp[j]]++;
    }
    for(int i = 1; i < n; ++i) cout << cnt[i] << '\n';
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<iterator>
#include<stack>
#include<queue>
#include<utility>
#include<functional>
#include<bitset>
#include<numeric>
#include<cstring>
#include<tuple>
using namespace std;

int n, x, pre = 0, l;
vector< int > arr;

int main( void )
{
	ios :: sync_with_stdio( 0 );
	cin.tie( 0 );
	
	cin >> n >> x;
	arr.emplace_back( pre );
	for( int i = 1; i <= n; ++i )
	{
		cin >> l;
		pre += l;
		arr.emplace_back( pre );		
	}
	cout << ( upper_bound( arr.begin(), arr.end(), x ) - arr.begin() ) << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stack>


using namespace std;


stack<int> visiting;

#define MAX 100
bool adj[MAX + 2][MAX + 2];
int d[MAX + 1], f[MAX + 1];
bool discovered[MAX + 1];
int tt, n;


void dfs(int v)
{
    visiting.push(v);
    discovered[v] = true;
    d[v] = ++tt;

    while (!visiting.empty()) {
        int now = visiting.top();
        int i;
        for (i = 1; i <= n; i++) {
            if (adj[now][i] && !discovered[i])
                break;
        }

        if (!discovered[i] && i <= n) {
            d[i] = ++tt;
            visiting.push(i);
            discovered[i] = true;
        } else {
            f[now] = ++tt;
            visiting.pop();
        }
    }
}


int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int id, k;
        cin >> id >> k;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            adj[id][v] = true;
        }

        discovered[i] = false;
    }

    for (int i = 1; i <= n; i++)
        if (!discovered[i])
            dfs(i);


    for (int i = 1; i <= n; i++) {
        cout << i << " ";
        cout << d[i] << " ";
        cout << f[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3144
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
//const ll mod = 1000000007;
ll mod[2];
ll dp[1000000];
ll val[2] = {0, 0};
ll ans[201000];

void initialize() {
    for(ll i = 1; i < 1e6; i++) {
        ll tmp = __builtin_popcount(i);
        ll to = i % tmp;
        dp[i] = dp[to] + 1;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    initialize();
    ll N;
    string S;
    cin >> N >> S;
    ll one = 0;
    for(int i = 0; i < N; i++) {
        one += (S[i] == '1');
    }
    mod[0] = one + 1;
    mod[1] = one - 1;
    ll factor[2] = {1, 1};
    for(int i = N - 1; i >= 0; i--) {
        for(int j = 0; j < 2; j++) {
            if(S[i] == '1') {
                val[j] += factor[j];
                if(mod[j] != 0) val[j] %= mod[j];
            }
            factor[j] *= 2;
            if(mod[j] != 0) factor[j] %= mod[j];
        }
    }
    for(int i = 0; i < 2; i++) factor[i] = 1;
    for(int i = N - 1; i >= 0; i--) {
        ll tmpval;
        ll MOD;
        if(S[i] == '1') {
            if(one == 1) {
                ans[i] = 0;
                for(int j = 0; j < 2; j++) {
                    factor[j] *= 2;
                    if(mod[j] != 0) factor[j] %= mod[j];
                }
                continue;
            }
            tmpval = val[1];
            tmpval -= factor[1];
            MOD = mod[1];
        }
        else {
            tmpval = val[0];
            tmpval += factor[0];
            MOD = mod[0];
        }
        tmpval %= MOD;
        tmpval += MOD;
        tmpval %= MOD;
        ans[i] = 1 + dp[tmpval];
        for(int j = 0; j < 2; j++) {
            factor[j] *= 2;
            if(mod[j] != 0) factor[j] %= mod[j];
            //cerr << i << " " << j << " " << factor[j] << " " << mod[j] << endl;
        }
    }
    for(int i = 0; i < N; i++) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 13132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

const ll MX=100000;
void solve(){
    ll q;cin>>q;
    vl l(q),r(q);
    rep(i,q)cin>>l[i]>>r[i];

    vl is_prime(MX+5,1);
    is_prime[0]=is_prime[1];
    vl like_2017(MX+5);
    repe(i,2,MX){
        if(!is_prime[i])continue;
        for(ll j=i+i;j<=MX;j+=i){
            is_prime[j]=0;
        }
        if(i%2&&is_prime[i]&&is_prime[(i+1)/2]){
            like_2017[i]=1;
        }
    }
    rep(i,MX)like_2017[i+1]+=like_2017[i];

    rep(i,q){
        cout<<like_2017[r[i]]-like_2017[l[i]-1]<<endl;
    }
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
template < class T > bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N, T;
  cin >> N >> T;
  map< int, int > mp;
  priority_queue< int, vec< int >, greater< int > > q;
  REP(i, N) {
    int p;
    cin >> p;
    if (i > 0) {
      int minp = q.top();
      mp[minp - p]++;
    }
    q.push(p);
  }
  // FORA(e, mp) {
  //   DEBUG(e.fst);
  //   DEBUG(e.snd);
  // }

  // vec< pair< int, int > > a(N);
  // REP(i, N) {
  //   cin >> a[i].fst;
  //   a[i].snd = i;
  // }
  // sort(ALL(a));
  // map< int, int > mp;
  // int end = 1;
  // REP(i, N) {
  //   for (int j = N - 1; j >= end; j--) {
  //     if (a[i].snd < a[j].snd) {
  //       mp[a[i].fst - a[j].fst]++;
  //       end = max(end, j + 1);
  //     }
  //   }
  // }

  print(mp.begin()->snd);
}

Measured memory_bytes: 7284
#include <bits/stdc++.h>
#define r1(i, n) for (int i=0;i<n;i++)
#define r2(i, n) for (int i=1;i<n+1;i++)
#define intc(n) int n; cin >> n;
#define ll long long
#define llc(n) ll n; cin >> n;
#define stringc(s) string s; cin >> s;
using namespace std;
int main() {
  llc(n);
  ll a=0;
  r2(i,n) if(i%3!=0 && i%5!=0) a+=i;
  cout << a << endl;
}

Measured memory_bytes: 3596
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<double>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Tree = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<vector<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 mp make_pair
#define mt make_tuple
#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>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

Vec fac, inv, finv;

ll PowMod(ll a, ll n){
	if(n == 1) return a;
	if(!(n%2)) return PowMod(a*a%MOD, n/2);
	return a*PowMod(a*a%MOD, n/2)%MOD;
}

void fill_fac(ll n){
	fac.resize(n+1);
	fac[0] = 1;
	repn(i, n) fac[i] = (fac[i-1]*i)%MOD;
}

void fill_inv(int n){
	inv.resize(n+1);
	inv[0] = 1;
	repn(i, n) inv[i] = PowMod(i, MOD-2);
}

void fill_finv(int n){
	fill_inv(n);
	finv.resize(n+1);
	finv[0] = 1;
	repn(i, n) finv[i] = (finv[i-1]*inv[i])%MOD;
}

ll combi(int n, int k){
	return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}

int main(void){
	ll n, k;
	cin >> n >> k;
	Vec a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	fill_fac(n);
	fill_finv(n);

	ll ans = 0;
	repn(i, n){
		if(n-i < k-1) break;
		ans += a[n-i]*combi(n-i, k-1);
		ans %= MOD;
	}
	repn(i, n){
		if(n-i < k-1) break;
		ans -= a[i-1]*combi(n-i, k-1);
		ans %= MOD;
		ans += MOD;
		ans %= MOD;
	}
	co(ans);

	return 0;
}


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

int main()
{
    int N;
    cin >> N;
    int min = INT_MAX;
    int sum = 0;

    // 入力
    // 10で割り切れない最小値チェック
    for (int i = 0; i < N; i++)
    {
        int ai;
        cin >> ai;
        sum += ai;

        if (ai < min && ai % 10 != 0)
        {
            min = ai;
        }
    }

    if (sum % 10 == 0)
    {
        sum -= min;
    }

    if (min == INT_MAX)
    {
        sum = 0;
    }

    cout << sum << endl;
}

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

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

        int[] coordinatesLine = new int[n];
        for (int i = 0; i < n; i++) {
            coordinatesLine[i] = scanner.nextInt();
        }
        Arrays.sort(coordinatesLine);
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i < 100; i++) {
            int temp = 0;
            for (int k = 0; k < n; k++) {
                int square = coordinatesLine[k] - i;
                temp += square * square;
            }
            if (temp < answer) {
                answer = temp;
            }
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 22996
//Author : Vipul Sharma

// LIBRARIES
#include <bits/stdc++.h>

// MACROS
#define ll long long int
#define rep(i, a, b) for (i = a; i < b; i++)
#define rev(i,b,a) for(i=b-1;i>=a;i--)
#define s1rep(i,a,b) for( i=1;i<=b;i++)
#define itrep(at) for (auto it = at.begin(); it != at.end(); it++)
#define ld long double
#define pb push_back
#define w(t) while (t--)
#define booster                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define mod 1000000007
#define endl "\n"
#define deb1(x) cout << #x << " : " << x << endl;
#define deb2(x, y) cout << #x << " : " << x << "\t" << #y << " : " << y << endl;
#define deb3(x, y, z) cout << #x << " : " << x << "\t" << #y << " : " << y << "\t" << #z << " : " << z << endl;
#define deb4(x, y, z, w) cout << #x << " : " << x << "\t" << #y << " : " << y << "\t" << #z << " : " << z << "\t" << #w << " : " << w << endl;
#define deb5(a, b, c, d, e) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define deb6(a, b, c, d, e, f) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

using namespace std;
long long cost = 1e18;
// FUNCTIONS
ll power(ll a, ll n)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
        {
            res *= a;
            n--;
        }
        else
        {
            a *= a;
            n >>= 1;
        }
    }
    return res;
}













ll dp[100001];

ll solve(ll a[],ll n)
{
    ll dp[n],i;
    rep(i,0,n) dp[i]=INT_MAX;
    dp[0]=0;
    for( i=0;i<n;i++)
    {
        for(ll j=i+1;j<=i+2;j++)
        {
            if(j<n)
                dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
            
        }
    }
    return dp[n-1];
}



int main()
{
    booster;
    ll n,i;
    cin>>n;
    ll a[n];
    rep(i,0,n) cin>>a[i];
    cout<<solve(a,n)<<endl;
    return 0;

}

Measured memory_bytes: 1792
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

string s;

int main(){
    cin >> s;
    int Mn = sz(s);
    for(char ch = 'a';ch <= 'z';++ch) {
        string s = ::s;
        int times(0);
        while(sz(s)) {
            bool ok = true;
            rep(i,0,sz(s)) ok &= s[i] == ch;
            if(ok) break;
            string t = "";
            rep(i,0,sz(s)-1) t+=s[i]==ch?ch:s[i+1];
            times++;
            s = t;
        }
        Mn = min(Mn , times);
    }
    cout << Mn << endl;
    return 0;
}


Measured memory_bytes: 256