akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define AB_BHI_NI_DEGI               \
   ios_base::sync_with_stdio(false); \
   cin.tie(NULL);                    \
   cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
int mod = 1e9 + 7;
//int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define ll long long
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double
#define endl "\n"

#define ordered_set tree<P, null_type, less<P>, rb_tree_tag, tree_order_statistics_node_update>

int32_t main()
{
   AB_BHI_NI_DEGI
   //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
   //cout.precision(20);
   //cout << fixed;
   int T = 1;
   //cin >> T;
   int cnt = 1;
   while (T--)
   {
      string s, t;
      cin >> s >> t;
      if (s == t)
      {
         cout << "0\n";
         return 0;
      }
      int ans = inf;
      int m = t.size();
      for (int i = 0; i + m <= s.size(); i++)
      {
         string temp = s.substr(i, m);
         int cnt = 0;
         for (int j = 0; j < m; j++)
            cnt += temp[j] != t[j];
         ans = min(ans, cnt);
      }
      cout << ans << "\n";
   }
   return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<int, int>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

int main() {
  int D; cin >> D;
  vector<int> c(26); REP(i, 26) cin >> c[i];
  vector<vector<int>> s(D, vector<int>(26));
  REP(i, D) {
    REP(k, 26) {
      cin >> s[i][k];
    }
  }
  REP(i, D) {
    int max_n = 0;
    int res = 0;
    REP(k, 26) {
      if(res < s[i][k]) {
        res = s[i][k];
        max_n = k + 1;
      }
    }
    cout << max_n << endl;
  }
}

Measured memory_bytes: 3680
# Problem  https://atcoder.jp/contests/abc069/tasks/abc069_b
# Python 3rd Try


def solver(inputStr) :
    top =  inputStr[0]
    middle = len(inputStr)-2
    endChar = inputStr[-1]
    return top,middle,endChar


if __name__=="__main__" :
    answer1=''
    answer2=0
    answer3=''
    S = input()
    answer1,answer2,answer3= solver(S)
    print(answer1,answer2,answer3,sep='')


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int x;
vector<int> sieve(int n) {
	vector<int> prime;
	vector<bool> is_prime(n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; ++i) {
		if (is_prime[i]) {
			prime.push_back(i);
			for (int j = 2 * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	return prime;
}
int main() {
	cin >> x;
	if (x < 105) {
		cout << "0" << endl;
	}
	else if (105 <= x && x < 135) {
		cout << "1" << endl;
	}
	else if (135 <= x && x < 165) {
		cout << "2" << endl;
	}
	else if (165 <= x && x < 189) {
		cout << "3" << endl;
	}
	else if (189 <= x && x < 195) {
		cout << "4" << endl;
	}
	else if (195 <= x && x <= 200) {
		cout << "5" << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<utility>
#include<algorithm>
#include<math.h>
using namespace std;
using ll = long long;
constexpr ll INF=1000000011;

int main (){
    int N,K;
    int h[100007] = {};
    ll dp[100007] = {};
    int k;

    cin >> N >> K;

    fill_n(dp,N+1,INF);

    for(int i=1;i<=N;i++){
        cin >> h[i];
    }

    dp[1] = 0;

    for(int i=1;i<=N;i++){
        for(int k=1;k<=K && i+k<=N;k++){
            dp[i+k] = min(dp[i] + abs(h[i]-h[i+k]),dp[i+k]);
        }
    }

    cout << dp[N] << endl;

}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#pragma GCC optimize ("Ofast")
#define __IO ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
int n , m , dist[100005] , ans = 0 , x, y , vis[100005];
vector<int> v[100005];
bool used[100005];
void dfs(int now){
	vis[now] = 1;
	for(auto &c : v[now]){
		if(!vis[c])dfs(c);
		dist[now] = max(dist[c]+1 , dist[now]) , ans = max(ans , dist[now]);
	}
}
int main(){__IO
	cin >> n >> m;
	for(int i=0 ; i<m ; ++i)cin >> x >> y , v[y].push_back(x) ,used[x] = 1;
	for(int i=1 ; i<=n ; ++i)if(used[i] == 0)dfs(i);
	cout << ans <<'\n';
}

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

using namespace std;

const int N = 2e3 + 5;

int cnt[N];
int n, x, y;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> x >> y;
  for (int s = 1; s <= n; s++)
    for (int t = s + 1; t <= n; t++)
      cnt[min(t - s, abs(s - x) + 1 + abs(t - y))]++;
  for (int i = 1; i < n; i++)
    cout << cnt[i] << '\n';
  return 0; 
}

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

int main(){
  string S; cin >> S;
  bool humiyasui = true;
  for(int i = 0; i < S.size(); i++){
    if((i+1)%2 == 1 && S[i] == 'L'){
      humiyasui = false;
      break;
    }
    else if((i+1)%2 == 0 && S[i] == 'R'){
      humiyasui = false;
      break;
    }
  }
  if(humiyasui) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toLong() }

    var ans = 0L
    val gpI = mutableMapOf<Long,Long>()
    val gpJ = mutableMapOf<Long,Long>()
    for (i in 0 until n) {
        val plus = a[i]+i
        val minus = i-a[i]
        if (gpI[plus] != null) gpI[plus] = gpI[plus]!! + 1
        else gpI[plus] = 1
        if (gpJ[minus] != null) gpJ[minus] = gpJ[minus]!! + 1
        else gpJ[minus] = 1
    }

    gpI.forEach {
        if (gpJ[it.key] != null) {
            ans += it.value * gpJ[it.key]!!
        }
    }

    println(ans)

}


Measured memory_bytes: 95336
#include<iostream>
#include <string>

using namespace std;

int main(void) {

	int N;
	int t[55];
	string S[55];

	cin >> N;
	for (int i = 1; i <= N; i++) { cin >> S[i] >> t[i]; }

	string X;
	cin >> X;

	int ans = 0;
	for (int i = 1; i <= N; i++) { ans += t[i]; }

	for (int i = 1; i <= N; i++) {
		ans -= t[i];
		if (X == S[i]) { break; }
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;

#define INF 1000000000

// try to use from bigger number
int search(int n, int k, int s){
  if(k==1){
    if(n>=s) return 1;
    else return 0;
  }
  int res=0;
  for(int i=min(n,s-1); i>1; i--){
    // use i
    res += search(i-1, k-1, s-i);
  }
  return res;
}

int main(){
  int n,k,s;
  while(scanf("%d %d %d", &n, &k, &s), n|k|s){
    cout<<search(n,k,s)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<int, ll> pli;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define TIME(i) Timer i(#i)
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define TIME(i)
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif
class Timer {
private:
    string scope_name;
    chrono::high_resolution_clock::time_point start_time;
public:
    Timer (string name) : scope_name(name) {
        start_time = chrono::high_resolution_clock::now();
    }
    ~Timer () {
        auto stop_time = chrono::high_resolution_clock::now();
        auto length = chrono::duration_cast<chrono::microseconds>(stop_time - start_time).count();
        double mlength = double(length) * 0.001;
        debug(scope_name, mlength);
    }
};

const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
// const ll MAXN = 

int a, b;
/********** Good Luck :) **********/
int main () {
    TIME(main);
    IOS();

    cin >> a >> b;

    int cur = 1;
    REP (i, 100) {
        if (cur >= b) {
            cout << i << endl;
            break;
        }
        cur += a - 1;
    }

    
    return 0; 
}


Measured memory_bytes: 256
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

long long gcd(long long a, long long b) {
	long long r = -1;
	if (a < b) {
		swap(a, b);
	}
	while (r != 0) {
		r = a % b;
		if (r == 0) {
			return b;
		}
		else {
			a = b;
			b = r;
		}
	}
}

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

int main() {
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define M 1000003
using namespace std;
int n,d[M];
string str,key;

int stoi(string s){
  int r=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='A')r=r*4+1;
    if(s[i]=='C')r=r*4+2;
    if(s[i]=='G')r=r*4+3;
    if(s[i]=='T')r=r*4+4;
  }
  return r;
}

void insert(int k){
  int i=0,f=0;
  while(!f){
    int p=(k%M+i*(1+k%(M-1)))%M;
    if(d[p]<0)d[p]=k,f=1;
    i++;
  }
}

bool find(int k){
  int i=0;
  while(i!=M){
    int p=(k%M+i*(1+k%(M-1)))%M;
    if(d[p]==k)return true;
    if(d[p]<0)return false;
    i++;
  }
  return false;
}

int main(){
  cin>>n;
  for(int i=0;i<M;i++)d[i]=-1;
  while(n--){
    cin>>str>>key;
    int k=stoi(key);
    if(str[0]=='i')insert(k);
    else{
      if(find(k))cout<<"yes"<<endl;
      else cout<<"no"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 5108
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double

#define pll pair<ll,ll>
#define ff first
#define ss second

#define pb push_back
#define all(x) x.begin(),x.end()

#define MOD  1000000007
const int N = 100005; 

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    string s,t;
    cin >> s >> t;
    ll ans = 1e9;
    for(ll i=0;i<s.size()-t.size()+1;i++)
    {
        ll sum = 0;
        for(ll j=0;j<t.size();j++)
        {
            if(s[i+j]!=t[j])   sum++;
        }
        ans = min(ans,sum);
    }
    cout<<ans;
}

int main()
{
    FAST;
    int t = 1;
 // cin >> t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
}

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

int main(){
  string S,T;
  cin >> S >> T;
  int result = 0;
  for(int i = 0; i < S.length(); i++){
    if(S[i] != T[i]){
      result ++;
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 3844
#include <stdio.h>
int main(void){
    int a, b, c, i;
    scanf("%d", &a);
    b = 1;
    for(i = 0; i < a; i++){
        if(a >= b){
            c = b;
            b = b * 2;
        }
    }
    printf("%d", c);
}


Measured memory_bytes: 1712
N, K = map(int, input().split())
mod = 10 ** 9 + 7

def comb(n, k):
  if n < k: 
    return 0
  if n < 0 or k < 0: 
    return 0
  if k > n - k:
    return comb(n, n - k)
  mul, div = 1, 1
  for i in range(k):
    mul = mul * (n - i) % mod
    div = div * (k - i) % mod
  return mul * pow(div, mod-2, mod) % mod

for i in range(1, K + 1):
  print(comb(N - K + 1, i) * comb(K - 1, i - 1) % mod)

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

#define int long long
// logic: Print, Help, For, Equal, eXclusive, Decrease
#define P(x) cout << x << endl
#define H(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(n); i++)      // [0,n)
#define FE(i,n) for (int i=0; i<=(n); i++)    // [0,n]
#define FX(i,a,b) for (int i=(a); i<(b); i++) // [a,b)
#define D(i,n) for (int i=(n); --i>=0;)       // (n,0]
#define DX(i,a,b) for (int i=(b); --i>=(a);)  // (b,a]
#define S(s) (int)((s).size())
#define ALL(v) v.begin(), v.end()
#define V vector
#define pb push_back
#define mt make_tuple

using namespace std;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int m; cin >> m;
	cout << (48-m) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> ps;
  std::vector<int> qs(n);
  for (int i = 0; i < n; ++i) {
    int64_t p;
    std::cin >> p;
    ps.push_back(p);
    qs[p-1] = i;
  }
  int t = 1, ans = 1;
  for (int i = 1; i < n; ++i) {
    if (qs[i] > qs[i-1])
      ++t;
    else
      t = 1;
    ans = std::max(ans, t);
  }
  std::cout << n - ans << std::endl;
}


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

#define mod 1000000007

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int K, X;
	
	cin >> K >> X;
	
	for(int i=X-K+1; i<=X+K-1; i++)
		cout << i << " ";
	
	return 0;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
mod=10**9+7
dp=[[0]*(w+1) for i in range(h+1)]
dp[1][0]=1
for i in range(1,h+1):
    line=input()
    for j in range(1,w+1):
        if line[j-1]!='#':
            dp[i][j]+=dp[i-1][j]+dp[i][j-1]
print(dp[-1][-1]%mod)


Measured memory_bytes: 212476
#include<bits/stdc++.h>
using namespace std;
long long t[1005],a[1005],n,c,d;
int main(){
	cin>>n;
	cin>>t[1]>>a[1];
	for(int i=2;i<=n;i++)
	{
		cin>>t[i]>>a[i];
		   c=(t[i-1]+t[i]-1)/t[i];
		   d=(a[i-1]+a[i]-1)/a[i]; 
		if((t[i]<t[i-1])||(a[i]<a[i-1]))
		
		    a[i]=max(c,d)*a[i], 
		   t[i]=max(c,d)*t[i];
		  
	
		    
		 
	}
	cout<<a[n]+t[n];
}

Measured memory_bytes: 256
/* ex 7_1
   YSK722 */

#include <stdio.h>

typedef struct point{  // xy座標
    int x_elem;
    int y_elem;
}point;

point shift_point(point vertice1, point vertice2);  // プロトタイプ宣言

int main(void){
    point vertice1, vertice2, vertice3, vertice4;
    scanf(
        "%d %d %d %d", &vertice1.x_elem, &vertice1.y_elem,
        &vertice2.x_elem, &vertice2.y_elem
    );
    // 反時計回りに順にvertice3とvertice4を求める
    vertice3 = shift_point(vertice1, vertice2);
    vertice4 = shift_point(vertice2, vertice3);
    printf(
        "%d %d %d %d", vertice3.x_elem, vertice3.y_elem,
        vertice4.x_elem, vertice4.y_elem
    );
    return 0;
}

// 既知の頂点から次の頂点を求める関数
point shift_point(point vertice1, point vertice2){
    point new_vertice;
    new_vertice.x_elem = vertice2.x_elem - (vertice2.y_elem - vertice1.y_elem);
    new_vertice.y_elem = vertice2.y_elem + (vertice2.x_elem - vertice1.x_elem);
    return new_vertice;
}

Measured memory_bytes: 1736
import java.lang.reflect.Array;
import java.util.*;

/**
 * Created by Santa.
 */
public class Main {

    static int N;
    static int K;
    static int Q;
    static int A;
    static long B;
    static long C;
    //    static int[][] map;
    static int min = 9999999;
    static long ans = 0;


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

        int N = scanner.nextInt();

        int[] x = new int[N];
        int[] y = new int[N];
        long[] h = new long[N];

        long high = -1;

        for (int i = 0; i < N; i++) {
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
            h[i] = scanner.nextLong();

            high = Math.max(high, h[i]);
        }

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

            for (int j = 0; j <= 100; j++) {
                for (long k = high; k < high + 10001; k++) {
                    boolean ok = true;
                    for (int l = 0; l < N; l++) {
//                        System.out.println(i + " " + j + " " + k);
//                        System.out.println(k - Math.abs(x[l] - i) - Math.abs(y[l] - j));
                        if(Math.max(0, k - Math.abs(x[l] - i) - Math.abs(y[l] - j)) != h[l]){
                            ok = false;
                            break;
                        }
                    }
                    if(ok){
                        System.out.println(i + " " + j + " " + k);
                    }
                }
            }
        }


    }
}



Measured memory_bytes: 24404
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
#include <map> // pair
#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;
#define START 0
#define FORWARD 1
#define BACK 2
using namespace std;
using ll = long long;
typedef pair <ll, ll > pll;
bool comp(const pll &a, const pll &b) {
	return a.first < b.first;
}
//*********************************************************
// 最大公約数（Greatest Common Divisor）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
ll gcd(ll a, ll b)
{
	ll tmp, r;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	/* ユークリッドの互除法 */
	r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
	//// 引数に０がある場合は０を返す
	//if ((0 == m) || (0 == n))
	//	return 0;

	//// ユークリッドの方法
	//while (m != n)
	//{
	//	if (m > n) m = m - n;
	//	else         n = n - m;
	//}
	//return m;
}//gcd

int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll x[200004] = {};
	ll y[200004] = {};
	ll z[2003][2003] = { {} };
	vector<tuple<ll, ll>> vec;
	string s;
	string t;
	//IntStack yStack;
	//charStack Stack;
	//vector<pair<int, int> > pairs(a);
	//cout << LLONG_MAX<< endl;

	cin >> a;
	for (int i = 1; i <= a; i++)
	{
		cin >> x[i];
	}
	sort(x+1, x + a+1);
	/*for (int i = 1; i <= a; i++)
	{
		cout<< x[i]<<endl;
	}*/


	cout << x[a/2+1]-x[a/2] << endl;


	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//sort(x, x + a, std::greater<ll>());

//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得
//
//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}
//
//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え


/*vector<pair<ll, ll> > hoges(a);
for (int i = 0; i < a; i++)
{
cin >> x[i];
cin >> y[i];
hoges[i] = make_pair(x[i], y[i]);
}
sort(hoges.begin(),hoges.end(),comp);
for (int i = 0; i < a; i++)
{
if (hoges[i].second>=b)
{
ans += hoges[i].first*b;
break;
}
else
{
ans += hoges[i].first*hoges[i].second;
b -= hoges[i].second;

}
}*/

Measured memory_bytes: 1792
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int count = 0;
    
    //x以下の間繰り返す
    for(int i = 0; i <= x; ++i){
      //1からべき乗か調べる
      for(int j = 2; j <= x; ++j){
        if((Math.pow(i,j)<= x) && (count<Math.pow(i,j))){
          count = (int)Math.pow(i,j);
        }
      }
    }
    if(count==0){
      count = 1;
    }
    System.out.println(count);
    
  }
}

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

int main(){
    int c[3][3];
    int x[3]={0},y[3]={0};
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>c[i][j];
        }
    }
    for(int i=0;i<3;i++){
        y[i]=c[0][i]-x[0];
        x[i]=c[i][0]-y[0];
    } 
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(c[i][j]!=x[i]+y[j]){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
CHANGE_COUNT = 0

def print_output(_list):
    for index in range(len(_list)):
        if index == len(_list) - 1:
            print(_list[index])
        else:
            print(_list[index],end=' ')

def insertion(target_list, g=1):
    global CHANGE_COUNT
    target_length = len(target_list)
    for index in range(g, target_length):
        v = target_list[index]
        j = index - g
        while (j >= 0 and target_list[j] > v):
            target_list[j + g] = target_list[j]
            j -= g
            CHANGE_COUNT += 1
        target_list[j + g] = v
    return target_list

def shellsort(target_list, shell_list):
    shell_length = len(shell_list)
    for shell_index in shell_list:
        target_list = insertion(target_list, shell_index)
    return target_list

target_list = [int(input()) for i in range(int(input()))]
target_length = len(target_list)
shell_list = []
shell_value = 1
while shell_value <= target_length:
    shell_list.append(shell_value)
    shell_value = 3 * shell_value + 1
shell_list.reverse()
print()
print(len(shell_list))
print_output(shell_list)
shellsort_list = shellsort(target_list, shell_list)
print(CHANGE_COUNT)
for shellsort_value in shellsort_list:
    print(shellsort_value)


Measured memory_bytes: 45520
#include <iostream>
using namespace std;
int main() {
    long long n,a=10,b=9,c=8,mod=1000000007;
	cin>>n;
    for(int i=1;i<n;i++) {
        a=a*10%mod;
        b=b*9%mod;
        c=c*8%mod;
    }
    a=(a+c)%mod;
  	cout<<(a-(2*b)%mod+mod)%mod<<endl;
  	return 0;
}

Measured memory_bytes: 3584
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        while(true){
 
            int a = sc.nextInt();
            String op = sc.next();
            int b = sc.nextInt();
 
            if(op.equals("?"))break;
 
            int ans = 0;
 
            switch(op){
            case "+":
                ans = a+b;
                break;
            case "-":
                ans = a-b;
                break;
            case "*":
                ans = a*b;
                break;
            case "/":
                ans = a/b;
                break;
            }
 
            System.out.println(ans);
        }
    }
}


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

int main() {
  long N;
  long A, B;
  cin >> N >> A >> B;
  long loop = A + B;
  long surplus;
  
  cout << (N / loop * A + ((surplus = N % loop) > A ? A : surplus)) << endl;
  return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
ll mo=1000000007;
int num[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		x=i;
		for(j=2;j<=x;j++) {
			while(x%j==0) num[j]++, x/=j;
			
		}
	}
	ll ret=1;
	for(i=1;i<=1000;i++) ret=ret*(num[i]+1)%mo;
	cout<<ret<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 764
def calc(i)
    case $char[i]
    when "*"
        $children[i].inject(1) {|r, v| r * calc(v)}
    when "+"
        $children[i].inject(0) {|r, v| r + calc(v)}
    else
        $char[i].to_i
    end
end

loop do
    break if (l = gets.to_i) == 0

    $char = Array.new(l)
    $char[0] = gets.chomp
    $children = Array.new(l){[]}

    (l-1).times do |i|
        i += 1
        s = gets.chomp
        n = s.count(".")

        now = 0
        (n-1).times {now = $children[now][-1]}

        $children[now] << i
        $char[i] = s[-1]
    end
    
    puts calc(0)
end


Measured memory_bytes: 6888
n = int(input())
w = list(map(int, input().split()))

ans = 100*100*10
for t in range(n):
    a = sum(w[:t])
    b = sum(w[t:])
    abssum = abs(a-b)
    #print(t, a, b, abssum)
    if abssum < ans:
        ans = abssum
print(ans)

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

using namespace std;

int main(){
    string s;
    cin>>s;
    if(s[0]==s[1] && s[0]==s[2]) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    
    return 0;
}

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

using namespace std;

int main(){
	char s1[200],s2[200];
	int l1,l2;
	scanf("%s%s",s1,s2);
	l1=strlen(s1); l2=strlen(s2);
	if(l1!=l2){
		if(l1>l2) puts("GREATER"); else puts("LESS");
		return 0;
	}
	for(int i=0;i<l1;i++){
		if(s1[i]<s2[i]){puts("LESS"); return 0;}
		if(s1[i]>s2[i]){puts("GREATER"); return 0;}
	}
	puts("EQUAL"); 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)

int v[100001];
int main(){
   int s,k;
   cin >> k >> s;
   int ans = 0;
   for (int x = 0; x < k+1;x++){
      for (int y = 0;y < k+1;y++){
         if (0 <= s-x-y && s-x-y <= k) ans++;
      }
   }
   cout << ans << endl;
   
   return 0;
   
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def correct():
    N = int(input())
    list_a = [int(a) for a in input().split()]

    nxt = 1
    ans = 0
    for a in list_a:
        if a == nxt:
            nxt += 1
        else:
            ans += 1
    if ans == N:
        ans = -1

    print(ans)


if __name__ == "__main__":
    correct()


Measured memory_bytes: 24744
#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    aveA=sum(A)/N
    d=K/N
    K_i=[int(A[i]/aveA*d) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    b=[]
    for i in range(N):
        b.append([dA[i],i])
    b.sort(reverse=True)
    now=0
    for i in range(res):
        K_i[b[now][1]]+=1
        dA[b[now][1]]=A[b[now][1]]/(K_i[b[now][1]]+1)
        if dA[b[now][1]]<b[now+1][0]:
            now+=1
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 122680
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>

using namespace std;

int main() {
  string s;
  cin >> s;
  bool b = true;
  string ans = "AKIHABARA";
  int j = 0;
  for(int i = 0; i < ans.size(); i++) {
    if(j >= s.size()) {
      if(i == ans.size() - 1) {
        break;
      } else {
        b = false;
        break;
      }
    }
    if(s[j] == ans[i]) j++;
    else if(ans[i] == 'A') continue;
    else b = false;
  }
  if(s.size() != j) {
    b = false;
  }
  if(b) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define endl "\n"
#define sp " "
#define mod 1000000007
#define PI 3.1415926535
#define w(t) int t;cin>>t;while(t--)
using namespace std;
void tezi()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

int frog(int *h,int n,int k)
{
    if(n==1) return h[1];
    if(n==2) return abs(h[2]-h[1]);

    vector<int> dp(n+1);
    dp[1]=0;
    dp[2]=abs(h[2]-h[1]);

    for(int i=3;i<=n;i++)
    {
        dp[i]=INT_MAX;

        for(int j=i-1; j>=1 && i-j<=k; j--)
        {
            dp[i]=min( dp[i], abs(h[i]-h[j])+dp[j] );
        }        
    }
    return dp[n];
}

int taaro(int *a, int *b, int *c,int n)
{
    // cout<<"h";
    int dp[n+1][3];
    dp[1][0]=a[1];
    dp[1][1]=b[1];
    dp[1][2]=c[1];

    for(int i=2;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+c[i];
    }
    // for(int i=0;i<=n;i++)
    // {
    //     cout<<dp[i][0]<<sp<<dp[i][1]<<sp<<dp[i][2]<<endl;
    // }
    return max(dp[n][0],max(dp[n][1],dp[n][2]));
}

int compare( pair<int,int> a,  pair<int,int> b)
{
    if(a.fi==b.fi) return a.sec>b.sec;
    return a.fi<b.fi;
}
int knapsack(vector< pair<int,int> > item,int W,int n)
{
    int dp[n+1][W+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
           dp[i][j]=0;
        }//cout<<endl;
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if ( i==0 || j==0 ) dp[i][j]=0 ;
            else if ( item[i].fi <= j ) {
                if( j - item[i].fi >= 0 )  dp[i][j] = max( item[i].sec + dp[i-1][ j - item[i].fi ], dp[i-1][j] ) ;
                else dp[i][j] = max( item[i].sec , dp[i-1][j] );
            }
            else dp[i][j]=dp[i-1][j] ;
        }
    }

    // for(int i=0;i<=n;i++)
    // {
    //     cout<<i<<" ";
    //     if(i==0){
    //     for(int x=0;x<=W;x++) cout<<x<<" ";
    //     cout<<endl;
    //     }
    //     for(int j=0;j<=W;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }cout<<endl;
    // }
    return dp[n][W];
}

int32_t main(){

	// tezi();
    //main body
    int n,W;
    cin>>n>>W;
    vector< pair<int,int> > item(n+1);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        item[i]=make_pair(a,b);
    }
    sort(item.begin(),item.end(),compare);
    // for(int i=0;i<=n;i++)
    // {
    //     cout<<item[i].fi<<" "<<item[i].sec<<endl;
    // }
    cout<<knapsack(item,W,n)<<endl;
    
    return 0;
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
     cin>>s;
     bool flag = true;
     int l=s.size();
     for(int i=0;i<l;i++ )
     {
         if((s[i]=='R'&& (i+1)%2==0)  || (s[i]=='L' && (i+1)%2!=0) )
         {
             flag=false;
             break;
         }
     }

    if(flag)
    cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, D;
  cin >> N >> D;
  int q = D * 2 + 1;
  int r = (N + q - 1) / q;
  cout << r;
}
#endif


Measured memory_bytes: 3572
#include <iostream> 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define MAX 1000001
ll prime[MAX];
#define FAST           ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define gcd __gcd
ll rec(vector<vector<ll> >& dp,vector<ll>& arr,int n,int i,int k,int w)
{
  ll ans=0;
  if(i>=n)
    return 0;

  if(dp[i][k]!=-1)
    return dp[i][k];


  if(k!=0)
  ans=max(rec(dp,arr,n,i+1,w,w),arr[i]+rec(dp,arr,n,i+1,k-1,w));
  else
  ans=max(rec(dp,arr,n,i+1,k,w),rec(dp,arr,n,i+1,w,w));

  return dp[i][k]=ans;

}

//ll t[400008];
// void build(vector<ll>& a, int v, int tl, int tr) {
//     if (tl == tr) {
//         t[v] = a[tl];
//     } else {
//         int tm = (tl + tr) / 2;
//         build(a, v*2, tl, tm);
//         build(a, v*2+1, tm+1, tr);
//         t[v] = max(t[v*2] ,t[v*2+1]);
//     }
// }

// ll maxi(int v, int tl, int tr, int l, int r) {
//     if (l > r) 
//         return 0;
//     if (l == tl && r == tr) {
//         return t[v];
//     }
//     int tm = (tl + tr) / 2;
//     return max(maxi(v*2, tl, tm, l, min(r, tm)) ,maxi(v*2+1, tm+1, tr, max(l, tm+1), r));
// }



// void update(int v, int tl, int tr, int pos, ll new_val) {
//     if (tl == tr) {
//         t[v] = new_val;
//     } else {
//         int tm = (tl + tr) / 2;
//         if (pos <= tm)
//             update(v*2, tl, tm, pos, new_val);
//         else
//             update(v*2+1, tm+1, tr, pos, new_val);
//         t[v] = max(t[v*2] ,t[v*2+1]);
//     }
// }


struct hash_pair {
   template <class T1, class T2>
   size_t operator()(const pair<T1, T2>& p) const{
      auto hash1 = hash<T1>{}(p.first);
      auto hash2 = hash<T2>{}(p.second);
      return hash1 ^ hash2;
   }
};

ll rec(ll a[],ll first,ll last,int n)
{
  if(first>last)
    return 0;

  ll temp=1000000000;
  ll ind=0;
  for(ll i=first;i<=last;i++)
   {
    if(temp>a[i])
    {
      temp=a[i];
      ind=i;
    }
   }
   for(ll i=first;i<=last;i++)
    a[i]-=temp;


return min(last-first+1,(rec(a,first,ind-1,n)+rec(a,ind+1,last,n)+temp));

}
int temp[1000002]={0};

void sieve()
{
  temp[1]=1;
  for(int i=2;i<1000002;i++)
  {
    if(temp[i]==0)
    { temp[i]=i;
      for(int j=i*2;j<1000002;j+=i)
      { 
        if(temp[j]==0)
        temp[j]=i;
      }
    }
  }

}




int main() { 

int n;
cin>>n;
ll a[n];

for(int i=0;i<n;i++)
  cin>>a[i];

sort(a,a+n,greater<ll>());

vector<ll> c;
for(int i=0;i<n;i++)
{
  if(c.size()==0)
    c.pb(0);
  else if(i<=(n)/2)
  c.pb(a[i-1]);
  else
  c.pb(a[i-(n)/2]);
}

ll ans=0;
for(int i=0;i<n;i++)
  ans+=c[i];

cout<<ans;

return 0;
}


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

typedef long long int ll;
#define endl "\n"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pair<int, int>>
#define mems(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define forn(i, s, e) for(int i = s; i < (e); ++i)
#define FASTIO                                                                                     \
	ios_base::sync_with_stdio(false);                                                              \
	cin.tie(NULL);
#define FILEIO                                                                                     \
	freopen("./input.txt", "r", stdin);                                                            \
	freopen("./output.txt", "w", stdout);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                                                  \
	for(auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); blockTime.second;  \
		debug("%s : %lld ms\n ",                                                                   \
			  d,                                                                                   \
			  chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() -   \
														  blockTime.first)                         \
				  .count()),                                                                       \
			 blockTime.second = false)
const int M = 1e9 + 7;

template <class T>
T ABS(const T& x) {
	return x > 0 ? x : -x;
}
ll gcd(ll n1, ll n2) { return n2 == 0 ? ABS(n1) : gcd(n2, n1 % n2); }
ll lcm(ll n1, ll n2) { return n1 == 0 && n2 == 0 ? 0 : ABS(n1 * n2) / gcd(n1, n2); }
ll ceil2(ll a, ll b) { return (a + b - 1) / b; }

vector<int> dp;

int f(int s) {
	if(dp[s] != -1) return dp[s];
	if(s == 0) { return dp[s] = 1; }

	ll ways = 0;
	for(int i = 3; i <= s; ++i) {
		if(s - i < 0) break;
		ways += f(s - i);
		ways %= M;
	}
	return dp[s] = ways % M;
}

int main() {
	FASTIO
#ifdef LOCAL
	FILEIO
#endif
	int s;
	cin >> s;
	dp.resize(s + 1, -1);
	cout << f(s);
	return 0;
}

Measured memory_bytes: 3628
ans=0
n=int(input())
k=str(input())
r=k.count("R")
b=k.count("B")
g=k.count("G")
ans+=r*b*g
    
for i in range(n-2):
  ii=k[i]
  for j in range(i+1,(n-i)//2+1+i):
    jj=k[j]
    l=j+(j-i)
    #print(l)
    if jj!=ii and l<n:
      #print(i,j)
      ll=k[l]
      if ii!=ll and jj!=ll:
        ans-=1
          #print(i,j,l)
print(ans)

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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

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

void solution() {
  int a;
  string b;
  cin >> a >> b;
  string num;
  for (char c : b) {
    if (c >= '0' && c <= '9') num += c;
  }
  int bb = 0;
  for (char c : num) {
    bb = bb * 10 + (c - '0');
  }
  a *= bb;
  cout << a / 100 << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  solution();
}


Measured memory_bytes: 3616
#include <stdio.h>
int is_prime(int n){
  int i;
  for(i=2;i*i<=n;i++){
    if(n%i==0)return 0;
  }
  return 1;
}

int main(void)
{
  int n,i;
  while(scanf("%d",&n),n){
    for(i=n;;i--){
      if(is_prime(i)&&is_prime(i-2)){
	printf("%d %d\n",i-2,i);
	break;
      }
    }
  }
  return 0;
}

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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)5e5 + 123, mod = (int)1e9 + 7, inf = (int)1e9;
int n, k, a[N], b[N], t[4*N], cnt[N], c[N];
vector< int > up[N];

void upd(int v, int tl, int tr, int pos, int val){
	if(tl == tr){
		t[v] = val;
		return ;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)
		upd(v + v, tl, tm, pos, val);
	else
		upd(v + v + 1, tm + 1, tr, pos, val);
	t[v] = min(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r){
	if(r < tl || tr < l)
		return inf;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) / 2;
	return min(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

int main(){    

	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		b[a[i]] = i;
	}
	a[n + 1] = b[n + 1] = n + 1;
	for(int i = 1; i <= n; i++)
		upd(1, 1, n, i, n + 1);
	for(int i = n; i >= 1; i--){
		int x = b[i];
		int l = get(1, 1, n, x - k + 1, x);
		int r = get(1, 1, n, x, x + k - 1);
		upd(1, 1, n, x, i);
		/*
		for(int i = 1; i <= n; i++)
			cerr << get(1, 1, n, i, i) << " ";
		cerr << endl;
		
		cerr << b[i] << " " << l << " " << r << endl;
		*/
		up[b[l]].pb(i);
    	up[b[r]].pb(i);
    }
    
    priority_queue< int > q;
    vector< int > ans;
    q.push(n + 1);
    
    while(!q.empty()){
    	int v = q.top();
    	ans.pb(v);
    	q.pop();
    	for(int i = 0; i < up[v].size(); i++){
    		int x = up[v][i];
    		cnt[x]++;
    		if(cnt[x] == 2)
    			q.push(b[x]);
    	}	
    }
    
    reverse(ans.begin(),ans.end());
    
    for(int i = 0; i < n; i++)
    	c[ans[i]] = i + 1;
    for(int i = 1; i <= n; i++)
    	cout << c[i] << endl;
	return 0;
}


Measured memory_bytes: 48496
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>

typedef long long int llint;

template<long long int MODVALUE> class modllint{
  typedef long long int llint;
  llint val;
  void mod(){
    while( this->val < 0 ) this->val += MODVALUE;
    this->val %= MODVALUE;
  }
  void assign(const llint val){
    this->val = val;
    mod();
  }
public:
  modllint(): val(0){};
  modllint(const llint val){assign(val);};
  
  modllint& operator+=(const llint val){
    this->assign(this->val + val);
    return *this;
  }
  modllint& operator+=(const modllint& obj){
    this->assign(this->val + obj.val);
    return *this;
  }
  modllint operator+(const llint val){return this += val;}
  modllint operator+(const modllint& obj){return this += obj;}
  
  modllint& operator*=(const llint val){
    this->assign(this->val * val);
    return *this;
  }
  modllint& operator*=(const modllint& obj){
    this->assign(this->val * obj.val);
    return *this;
  }
  modllint operator*(const llint val){return this *= val;}
  modllint operator*(const modllint& obj){return this *= obj;}

  modllint& operator=(const modllint& obj){
    assign(obj.val);
    return *this;
  }
  modllint& operator=(const llint intvalue){
    assign(intvalue);
    return *this;
  }
  
  friend std::ostream& operator<<(std::ostream& os, const modllint<MODVALUE>& val){
    os << val.val;
    return os;
  }
  friend std::istream& operator>>(std::istream& is, modllint<MODVALUE>& val){
    is >> val.val;
    return is;
  }
};



int main(void){

  llint n, k;
  std::cin >> n >> k;

  modllint<1000000007> count = 0;

  std::vector<llint> smallest(n+2,0);
  std::vector<llint> largest(n+2,0);
  for(int i=1; i<=n+1; i++){
    smallest[i] = smallest[i-1] + (i-1);
    largest[i] = largest[i-1] + (n-i+1);
  }

  for(int i=k; i<=n+1; i++){
    count += (largest[i]-smallest[i] + 1);
  }

  std::cout << count << std::endl;

  return 0;
}


Measured memory_bytes: 6428
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define deb(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
typedef long long int ll;
typedef string str;

ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;     
  
    x = x % p;   
    while (y) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;  
        x = (x*x) % p; 
    } 
    return res; 
} 
 
ll nCrModP(ll n, ll r, ll p) 
{ 
    if (!r) 
      return 1; 
  
	ll fac[n+1]; 
   	fac[0] = 1; 
    for (ll i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* power(fac[r], p-2,p) % p * power(fac[n-r], p-2,p) % p) % p; 
}

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

void fast(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n;
	cout << n+n*n+n*n*n << "\n";
	return 0;
}

Measured memory_bytes: 3620