akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<int,int> ,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long MOD = 1e9+7;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
long long fastpow(long long x,long long k)
{
    if(!k)
        return 1;
    if(k & 1)
        return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
    long long ans = fastpow(x,k/2);
    ans %= MOD;
    ans *= ans;
    ans %= MOD;
    return ans;
}
long long sumF(long long x)
{
    int s = 0;
    while(x)
        s += x%10,x /= 10;
    return s;
}
int arr[105];
long long dp[2][100005];
int solve(int idx,int left)
{
    if(idx == 0)
        return left == 0;
    int C = 0;
    for(int i = 0;i <= arr[idx] && i <= left;i++)
        C += solve(idx - 1,left - i);
    return C;
}
int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
        cin >> arr[i];
    dp[0][0] = 1;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j <= k;j++)
        {
            dp[i%2][j] = 0;
            int f1 = j;
            int f2 = j - min(arr[i],j);
            dp[i%2][j] += (((dp[(i-1)%2][f1] - (f2 ? dp[(i-1)%2][f2-1] : 0)) % MOD) + MOD )%MOD;
            dp[i%2][j] %= MOD;
            if(j)
            dp[i%2][j] += dp[i%2][j-1];
            dp[i%2][j] %= MOD;
        }
    }
    cout << dp[n%2][k] % MOD;
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 100100
#define ll long long
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
void WA(){puts("NO");exit(0);}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1,dg[MAX];
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;++dg[u];}
int n,a[MAX],rt;
void dfs(int u,int ff)
{
	int mx=0;ll sum=0;
	for(int i=h[u];i;i=e[i].next)
	{
		int v=e[i].v;if(v==ff)continue;
		dfs(v,u);mx=max(mx,a[v]);sum+=a[v];
	}
	if(dg[u]==1)return;
	ll mn=min(sum/2,sum-mx);
	if(a[u]>sum)WA();
	else
	{
		if(sum-a[u]>mn)WA();
		else a[u]-=sum-a[u];
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	if(n==2){puts(a[1]==a[2]?"YES":"NO");return 0;}
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		Add(u,v);Add(v,u);
	}
	for(int i=1;i<=n;++i)
		if(dg[i]>1){dfs(rt=i,0);break;}
	if(a[rt])WA();
	puts("YES");return 0;
}


Measured memory_bytes: 9600
def cross(x, y):
    return (x.conjugate() * y).imag

def is_convex(points):
    n = len(points)
    x = points[1] - points[0]
    y = points[2] - points[1]
    c0 = cross(x, y)
    for i in range(1, n):
        x = y
        y = points[(i+2)%n] - points[(i+1)%n]
        if c0 * cross(x, y) < 0:
            return False
    return True
        

import sys

for line in sys.stdin:
    li = list(map(float, line.split(',')))
    p = []
    for i in range(0, len(li), 2):
        p.append(complex(li[i], li[i+1]))
    if is_convex(p):
        print('YES')
    else:
        print('NO')

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
const int M = 1e9 + 7;
const ll INF = 1e9;
const int MAX_V = 1000 + 5;
const int MAX_N = 1e5 + 5;

bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1; // exclude 1
}

int main() {
    int q;
    int sum = 0;
    cin >> q;
    vector<P> query(q);
    rep(i, q) {
        int a, b;
        cin >> a >> b;
        query[i] = make_pair(a, b);
    }
    vector<int> cusum(100020, 0);
    rep(i, 100020) {
        if (is_prime(i) && is_prime((i + 1) / 2)) {
            sum += 1;
        }
        cusum[i] = sum;
    }
    vector<int> ans(q);
    rep(i, q) {
        auto p = query[i];
        int begin = p.first;
        begin = max(0, begin - 1);
        int end = p.second;
        ans[i] = cusum[end] - cusum[begin];
    }
    rep(i, q) out(ans[i]);
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
 
using namespace std;
 
long long h[100005],n;
long long dp[100005];
long long mn(int i)
{
    if(i == n)
        return 0;
    if(i > n)return 1e9;
    long long rfr = dp[i];
    if(rfr != -1)return rfr;
 
    return dp[i] = min(abs(h[i] - h[i+1]) + mn(i+1), abs(h[i] - h[i+2]) + mn(i+2));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    memset(dp,-1,sizeof(dp));
    cout<<mn(1)<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

void dump(int n) {
		out(n, ':');
		for (int j = 0, t; (t = n >> j); j++)
			if (t & 1)
				out(' ', j);
		outl();
}

typedef vector<int> v;
void enumeration(int t, size_t i, v &k, v &r) {
	if (i >= k.size()) {
		r.push_back(t);
		return;
	}

	enumeration(t, i + 1, k, r);
	enumeration((1 << k[i]) | t, i + 1, k, r);
}

int main() {
	in();
	v k(in()),r;
	for (int &x: k)
		x = in();
	enumeration(0, 0, k, r);
	sort(r.begin(), r.end());
	for (int x: r)
		dump(x);
}


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

int main(void){
    int a, b;
    string s;
    cin >> a;
    if(a < 1200) cout << "ABC";
    else if(a<2800) cout << "ARC";
    else cout << "AGC";
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt64)
}

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

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

func main() {
	// Input
	n, m := readInt(), readInt()
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = readString()
	}
	b := make([]string, m)
	for i := 0; i < m; i++ {
		b[i] = readString()
	}

	l := n - m
	for i := 0; i <= l; i++ {
		for j := 0; j <= l; j++ {
			tmp := make([]string, m)
			for k := 0; k < m; k++ {
				tmp[k] = a[k+j][i : m+i]
			}
			if reflect.DeepEqual(tmp, b) {
				fmt.Println("Yes")
				os.Exit(0)
			}
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 1024
import itertools

def main():
    n,m,q = map(int,input().split())
    a = [0] * (q+1)
    b = [0] * (q+1)
    c = [0] * (q+1)
    d = [0] * (q+1)

    for i in range(1,q+1):
        a[i],b[i],c[i],d[i] = map(int,input().split())

    Alist = itertools.combinations_with_replacement(range(1,m+1),n)

    ans = 0
    for A in Alist:
        cnt = 0
        for i in range(1,q+1):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                cnt += d[i]
        ans = max(ans,cnt)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9096
#include <bits/stdc++.h>
using namespace std;
int main(void){
    double n,sum1=0.0,sum2=0.0,x,m,a;
    std::deque<double> deq;
    while (cin>>n) {
        if (n==0) {
            break;
        } else {
            for (int i=0;i<n;i++) {
                cin>>x;
                deq.emplace_back(x);
                sum1+=x;
            }
            m=sum1/n;
            for (int j=0;j<n;j++) {
                sum2=sum2+(deq[j]-m)*(deq[j]-m);
            }
            a=sum2/n;
            printf("%.8f",sqrt(a));
            cout<<endl;
            sum1=0;
            sum2=0;
            deq.clear();
        }
    }
}



Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

int main()
{
    string s;
    getline(cin, s);

    for (auto&& c : s) {
        if (isupper(c)) {
            c = tolower(c);
        } else if (islower(c)) {
            c = toupper(c);
        }
    }

    cout << s << endl;
}



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

int main()
{
    int n, m, d[100];

    cin >> n;

    for( int i = 0; i < n; i++ )
    {
        cin >> m;
        for( int j = 0; j < m; j++ )
            cin >> d[j];

        int max = 0, min = 0;
        for( int j = 0; j < m - 1; j++ )
        {
            if( max < d[j+1] - d[j] )
                max = d[j+1] - d[j];
            if( min > d[j+1] - d[j] )
                min = d[j+1] - d[j];
        }

        cout << max << " " << min * -1 << endl;
    }

    return 0;
}



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

ans = 0
is_broken = False
for num in sorted(a):
    if num > k:
        is_broken = True
        break
    else:
        k -= num
        ans += 1
if k != 0 and ans >= 1 and not is_broken:
    ans -= 1
print(ans)


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

int main()
{
    string S;
    cin >> S;
    int N = S.size();
    int c0 = 0, c1 = 0;
    rep(i, N)
    {
        if (S[i] == '0')
            c0++;
        else
            c1++;
    }
    //   cout << c0 << " " << c1 << endl;
    int ans = min(c0, c1) * 2;
    cout << ans << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <sstream>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())

#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using namespace std;

typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;

const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 1e6 + 100;

vector<int> a[N];

inline int match(vector<int> a, vector<int> b) {
    if (len(a) < len(b)) {
        swap(a, b);
    }
    int can = len(b);
    int left = (len(a) - len(b)) / 2;
    map<int, int> c;
    for (int i : a) {
        c[i]++;
    }
    for (auto i : c) {
        int cnt = min(left, i.sc / 2);
        left -= cnt;
        can += cnt;
    }
    return can;
}

int main() {
#ifdef XCODE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x; scanf("%d", &x);
        a[x % m].pb(x);
    }
    for (int i = 0; i < m; i++) {
        sort(all(a[i]));
    }
    int ans = 0;
    for (int i = 0; i < m && i <= m - i; i++) {
        if ((2 * i) % m == 0 || i == 0) {
            ans += len(a[i]) / 2;
        } else {
            ans += match(a[i], a[m - i]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 26752
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

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

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int main() {
	ll H, W;
	cin >> H >> W;
	ll res = 1e11;
	rep(_, 2) {
		ll a, b, c;
		for(int i = 0; i <= H; i++) {
			a = i*W;
			b = (H-i)*(W/2);
			c = (H-i)*(W - W/2);

			res = min(res, max(a,max(b,c)) - min(a,min(b,c)));

			b = ((H-i)/2)*(W);
			c = ((H-i) - (H-i)/2)*(W);

			res = min(res, max(a,max(b,c)) - min(a,min(b,c)));
		}
		swap(H,W);
	}
	cout << res << endl;
	return 0;
}


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

int main(){
  int A, B, Q;
  cin >> A >> B >> Q;
  
  vector<int64_t> temple(A+2);
  temple.at(0) = -1000000000000;
  temple.at(A+1) = 1000000000000; 
  for(int i=1; i<=A; i++){
    cin >> temple.at(i);
  }
  
  vector<int64_t> shrine(B+2);
  shrine.at(0) = -10000000000000;
  shrine.at(B+1) = 1000000000000; 
  for(int i=1; i<=B; i++){
    cin >> shrine.at(i);
  }
  
  vector<int64_t> query(Q);
  for(int i=0; i<Q; i++){
    cin >> query.at(i);
  }
  
  vector<int64_t>::iterator pos;
  int64_t idx_T1;
  int64_t idx_T2;
  int64_t idx_S1;
  int64_t idx_S2;
  
  for(int i=0; i<Q; i++){
    int64_t ans = 1000000000000;
    
    pos = lower_bound(temple.begin(),temple.end(),query.at(i));
    idx_T1 = distance(temple.begin(),pos);
    idx_T1 = abs(query.at(i) - temple.at(idx_T1));
    idx_T2 = distance(temple.begin(),pos-1);
    idx_T2 = abs(query.at(i) - temple.at(idx_T2));
    
    pos = lower_bound(shrine.begin(),shrine.end(),query.at(i));
    idx_S1 = distance(shrine.begin(),pos);
    idx_S1 = abs(query.at(i) - shrine.at(idx_S1));
    idx_S2 = distance(shrine.begin(),pos-1);
    idx_S2 = abs(query.at(i) - shrine.at(idx_S2));
    
    ans = min({max(idx_T1,idx_S1), max(idx_T2,idx_S2), idx_S1*2 + idx_T2, idx_S1 + idx_T2*2, idx_S2*2 + idx_T1, idx_S2 + idx_T1*2});
    
    cout << ans << endl;
  }
}

Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <utility>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define SUM(n) ((n)+1)*(n)/2
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = (1e9)+7;
#define all(v) v.begin(),v.end()
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

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

  int n;
  cin >> n;
  int x[n + 5];
  rep(i,n){
    cin >> x[i];
  }
  sort(x,x +n);
  lol sum = 0, minv = LINF;
  rep(nasu,100){
    rep(i,n){
      sum += (nasu - x[i]) * (nasu - x[i]);
    }
    minv = min(sum,minv);
    sum = 0;
  }
  cout << minv << '\n';
  return 0;
}


Measured memory_bytes: 256
// test: 

#include<iostream>
#include<vector>

using namespace std;

class UnionFind {
    public:
        vector<int> rank, size, p;
    
    UnionFind(){}
    UnionFind(int n){ // 初期化: rankが0のノードをn個生成する
        rank.resize(n, 0); // rank(木の深さ)
        size.resize(n, 1); // ノード数を親番号で管理
        p.resize(n, 0); // 親の番号
        for(int i=0; i < n; i++) makeSet(i);
    }

    void makeSet(int x){// 各ノードの親を自分自身で初期化
        p[x] = x;
        rank[x] = 0;
        size[x] = 1;
    }

    int findSet(int x){
        if( x!= p[x]){ // 根を見つけるまで遡る
            p[x] = findSet(p[x]); // 経路圧縮
        }
        return p[x];
    }

    bool same(int x, int y){
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y){
        link(findSet(x), findSet(y));
    }

    void link(int x, int y){ // 親が管理する集合を連結
        if(rank[x] > rank[y]){ // rankが小さい方の親を、大きい方の子とする
            p[y] = x;
            size[x] += size[y]; // sizeを更新
        } else {
            p[x] = y;
            size[y] += size[x];
            if(rank[x] == rank[y]){ // rankが等しければインクリメントする
                rank[y]++;
            }
        }
    }

    int getSize(int x){
        return size[findSet(x)];
    }
};

int main(){
    int n, a, b, q, t;

    cin >> n >> q;
    UnionFind UF = UnionFind(n);

    for(int i=0; i < q; i++){
        cin >> t >> a >> b;
        if(t==0) UF.unite(a, b);
        else if(t==1){
            if(UF.same(a, b)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3236
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

bool pc(pair<int,int>& first,pair<int,int>& second){
    if(first.first==second.first)return first.second > second.second;
    else return first.first < second.first;
}

int main(){
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    vector<pair<int,int>> v;
    REP(i,n){
        scanf("%d%d",&a,&b);
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end(),pc);
    auto comp=[](pair<int,int> l,pair<int,int> r){
        return l.second<r.second;
    };
    priority_queue<pair<int,int>,vector<pair<int,int> >,decltype(comp)> pq(comp);
    ll ans=0;
    auto itr=v.begin();
    pair<int,int> keep;
    for(int i=1;i<=m;i++){
        while(itr!=v.end() && (*itr).first==i){
            pq.push(*itr);
            //printf("####%d %d\n",(*itr).first,(*itr).second);
            ++itr;
        }
        //printf("hoge\n");
        if(!pq.empty()){
            keep=pq.top();
            pq.pop();
            ans+=keep.second;
            //printf("hoge2 %d\n",keep.second);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 2548
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}

int ncr[105][105] = {};

void init(){
    rep(i,105){
        ncr[i][0] = 1;
        ncr[i][i] = 1;
    }
    loop(i,1,105)loop(j,1,i){
        ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
    }
}


signed main(void) {
    int l,k;
    cin >> l >> k;
    init();
    int ans = 0;
    rep(i,l+1)rep(j,l)if(i+j >= 1 && i+k*j+(i+j-1) <= l){
         ans += ncr[i+j][i];
    }
    cout << ans << endl;
}



Measured memory_bytes: 3176
import sys
from itertools import combinations

import numpy as np

input = sys.stdin.readline


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = np.zeros(shape=(N, M), dtype=int)
    for i in range(N):
        CA = list(map(int, input().split()))
        C[i], A[i] = CA[0], CA[1:]

    ans = float("inf")
    for i in range(1, 13):
        for comb in combinations(range(N), i):
            total = 0
            B = np.zeros(shape=M, dtype=int)
            for j in comb:
                total += C[j]
                B += A[j]
            if all(b >= X for b in B):
                if total < ans:
                    ans = total

    if ans == float("inf"):
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 27060
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    int n,h,w,ans = 0;
    cin >> n >> h >> w;

    repi(i,n,0){
        int a,b;
        cin >> a >> b;
        if(a >= h && b >= w)ans++;
    }
    cout << ans << endl;
    return 0;
}

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

#define fast ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)

typedef long long ll;
typedef long double ld;
const ll inf = (ll)1e14;
const ll N = (ll)1e6;


int main() {
    fast;
    int n, m;
    char k;
    cin >> n >> m;
    map<char, int> mp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> k;
            mp[k]++;
        }
    }

    if (n % 2 == 1 and m % 2 == 1) {
        int t = 0, o = 0;
        for (int i = 'a'; i <= 'z'; i++) {
            mp[i] %= 4;
            if (mp[i] % 4 == 0);
            else if (mp[i] % 4 == 1) o++;
            else if (mp[i] % 4 == 2) t++;
            else return cout << "No\n", 0;
        }

        if (o == 1) {
            if (2 * t <= n + m - 2) return cout << "Yes\n", 0;
            else return cout << "No\n", 0;
        } else return cout << "No\n", 0;
    } else if (n % 2 == 1) {
        int t = 0;
        for (int i = 'a'; i <= 'z'; i++) {
            mp[i] %= 4;
            if (mp[i] % 4 == 2) t++;
            else if (mp[i] % 4 != 0) return cout << "No\n", 0;
        }
        if (t * 2 <= m) return cout << "Yes\n", 0;
        else return cout << "No\n", 0;
    } else if (m % 2 == 1) {
        int t = 0;
        for (int i = 'a'; i <= 'z'; i++) {
            mp[i] %= 4;
            if (mp[i] % 4 == 2) t++;
            else if (mp[i] % 4 != 0) return cout << "No\n", 0;
        }
        if (t * 2 <= n) return cout << "Yes\n", 0;
        else return cout << "No\n", 0;
    } else {
        for (int i = 'a'; i <= 'z'; i++) if (mp[i] % 4 != 0) return cout << "No\n", 0;
        cout << "Yes\n";
    }

    return 0;
}

Measured memory_bytes: 256
S=raw_input()

if S=="keyence":
	print "YES"
	quit()

l=len(S)
l_amari=len(S)-7

for i in range( l - l_amari+1):
	str1=S[0:i]
	str2=S[i+l_amari:]
	if str1+str2 == "keyence":
		print "YES"
		quit()
else:
	print "NO"


Measured memory_bytes: 28012
#include <stdio.h>

int main(void)
{
    int p,m,f,r;
    char result;
    
    while(1){
        scanf("%d %d %d",&m,&f,&r);
        
        if(m==-1 && f==-1 && r==-1) break;
        
        p=m+f;
        
        if(m==-1 || f==-1){
            result='F';
        }else if(p>=80){
            result='A';
        }else if(p>=65){
            result='B';
        }else if(p>=50 || r>=50){
            result='C';
        }else if(p>=30){
            result='D';
        }else{
            result='F';
        }
        printf("%c\n",result);
    }
    return 0;
}


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

int main(){
	string s;
  	cin >> s;
  	bool x=true;
  	for (char i='a';i<='z';i++){
      	int k=0;
    	for (int j=0;j<s.size();j++){
        	if(i==s.at(j))k++;
        }
      	if(k==0) {
          	cout << i ;
          	x=false;
          break;
        }
     }
  	if(x==true) cout << "None";
}


Measured memory_bytes: 512
def main():
    n=int(input())
    mon6=[6]
    mon9=[1]
    for i in range(5):
        mon6.append(6*mon6[i])
        mon9.append(9*mon9[i])
    mon=mon6+mon9
    mon.sort()
    
    
    inf=10**9
    dp=[[inf]*(n+1) for i in range(13)]
    
    for i in range(13):
      dp[i][0]=0
    for i in range(12):
        for j in range(1,n+1):
            if j-mon[i]>=0:
                dp[i+1][j]=min(dp[i+1][j-mon[i]]+1,dp[i][j])
            else:
                dp[i+1][j]=dp[i][j]
    print(dp[-1][-1]) 
if __name__=='__main__':
    main()

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

int main(){
	string s;
	int a=0;
  	cin>>s;
	for(int i=0;i<4;i++){
		if(s[i]=='+'){
			a++;
		}else{
			a--;
		}
	}
	cout<<a<<endl;
	return 0;
}


Measured memory_bytes: 256
from math import sqrt
from itertools import combinations_with_replacement
from collections import defaultdict

N=int(input())
MAX=int(sqrt(N))
num=[i for i in range(1,MAX+1)]
d=defaultdict(int)
for x,y,z in list(combinations_with_replacement(num,3)):
    val=x**2+y**2+z**2+x*y+y*z+z*x
    if x==y and y==z and z==x:
        d[val]+=1
    elif x==y or y==z or z==x:
        d[val]+=3
    else:
        d[val]+=6

for i in range(1,N+1):
    print(d[i])

Measured memory_bytes: 24028
/*
 *
 * so-suu
 */
#include<stdio.h>
#include<math.h>
int A[10000];

int main(void){
    int num=0, length, i, j, sq, flag;

    scanf("%d", &length);
    for(i=0; i<length; i++){
        scanf("%d",&A[i]);
    }

    for(i=0; i<length; i++){
        flag = 0;
        sq = (int)sqrt(A[i]);
        for(j=2; j<=sq; j++){
            if((A[i]%j) == 0){
                flag = 1;
                break;
            }
        }

        if(!flag)num++;
    }

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


    return 0;
}



Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using pll = pair<ll,ll>;
using Graph = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i,l,r) for(ll i = (l); i <= (ll)(r); i++)
#define rep3(i,l,r) for(ll i = (l); i >= (ll)(r); i--)
#define dup(x,y) (((x)+(y)-1)/(y)) // x/yの除算の切り上げ
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = 1001001001;
const ll INF = 1LL << 60;
const ll mod = 1000000007; //1000000007
const ld pi = acos(-1);
 
//xor演算
//a^b=b^a
//a^(b^c)=(a^b)^c
//a^a=0
//a+b=a^b + 2(a&b)
//(4a)^(4a+1)^(4a+2)^(4a+3)=0
 
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    ll n=s.size();
    ll dp[101010][5]={};
    dp[0][0]=1;
    rep2(i,0,n-1){
        rep2(j,0,3){
            if(s[i]=='?'){
                dp[i+1][j] = (dp[i][j]*3)%mod;
            }
            if(s[i]!='?'){
                dp[i+1][j] = dp[i][j]%mod;
            }
        }
            if(s[i]=='A'){
                dp[i+1][1] += dp[i][0]%mod;
            }
            if(s[i]=='B'){
                dp[i+1][2] += dp[i][1]%mod;
            }
            if(s[i]=='C'){
                dp[i+1][3] += dp[i][2]%mod;
            }
            if(s[i]=='?'){
                dp[i+1][1] += dp[i][0]%mod;
                dp[i+1][2] += dp[i][1]%mod;
                dp[i+1][3] += dp[i][2]%mod;
            }
        }
    cout << dp[n][3]%mod << '\n';
}


Measured memory_bytes: 7732
from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit as setreclim
from sys import maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits

prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x,y)%mod, l)

class Dijkstra:
    """Dijkstra's algorithm : find the shortest path from a vertex
       used in GRL1A(AOJ)
    """

    def __init__(self, V, E, start, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF] * self.V # distance from start
        self.prev = [-1] * self.V # prev vertex of shortest path
        self.distance[start] = 0
        heappush(que, (0, start))

        while len(que) > 0:
            dist, v = heappop(que)
            if self.distance[v] < dist: continue
            for to, cost in self.E[v]:
                if self.distance[v] + cost < self.distance[to]:
                    self.distance[to] = self.distance[v] + cost
                    heappush(que, (self.distance[to], to))
                    self.prev[to] = v

    def getPath(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

V, E, r = map(int, input().split())
INF = maxsize
edge = [[] for _ in range(V)]
for i in range(E):
    s, t, cost = map(int, input().split())
    edge[s].append((t, cost))
sp = Dijkstra(V, edge, r, INF)
for d in sp.distance:
    print(d if d != INF else 'INF')

Measured memory_bytes: 101524
#include<stdio.h>

int main(void){
	int n, i, a, b, c;

	scanf("%d", &n);

	for ( i = 0; i < n; i++) {
		scanf("%d %d %d", &a, &b, &c);

		if ((a*a) + (b*b) == (c*c)) {
			printf("YES\n");
		} else if ((b*b) + (c*c) == (a*a)) {
			printf("YES\n");
		} else if ((c*c) + (a*a) == (b*b)) {
			printf("YES\n");
		} else
			printf("NO\n");
	}

	return 0;
}

Measured memory_bytes: 0
a,b,k=map(int,input().split())
flag=0
for i in range(k):
    if flag==0:
        if a%2!=0:
            a-=1
        b+=a//2
        a=a//2
        flag=1
    else:
        if b%2!=0:
            b-=1
        a+=b//2
        b=b//2
        flag=0
print(a,b)


Measured memory_bytes: 3060
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int n,w,dp[110][100100];

signed main() {
    cin >> n >> w;
    vi weight(n),value(n);
    rep(i, n)cin >> weight[i] >> value[i];
    rep(i, n) {
        rep(j, w+1) {
            if(j-weight[i]>=0) {
                chmax(dp[i+1][j],dp[i][j-weight[i]]+value[i]);
            }
            chmax(dp[i+1][j],dp[i][j]);
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

Measured memory_bytes: 81668
#include <stdio.h>

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


Measured memory_bytes: 2060
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i < (int)n; i++)
ll mod = 1e9+7;

ll gcd(ll a, ll b){
  return (b != 0) ? gcd(b, a%b) : a;
}

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

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> zyou(1002, 1); 
  auto soinsubunkai = [&](int n, int& x){
    ll cnt = 0;
    while(x > 1 && x%n == 0){
      x /= n;
      ++cnt;
    }
    zyou[n] += cnt;
  };

  for(int i = n; i >= 2; --i){
    int x = i;
    rep1(j, 1000) soinsubunkai(j+1, x);
  }
  ll ans = 1;
  rep1(i, 1000){ ans *= zyou[i+1]; ans %= mod;}
  cout << ans << "\n";
  return 0;
}   

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

int main(int argc, char const *argv[])
{
    int n,d;cin>>n>>d;
    vector<vector <double>> x(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<d;j++){
            int xx;cin>>xx;
            x[i].push_back(xx);
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            double tmp=0.0l;
            for(int k=0;k<d;k++){
                tmp +=pow(x[i][k]-x[j][k],2.0);
            }
            double tmp2;
            // cout << "tmp "<< tmp << " ";
            tmp2 = pow(tmp,0.5);
            // cout << "tmp2 "<< tmp2 << endl;
            if(abs(tmp2-round(tmp2))<0.0001)cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 640
<?php
$ans = 0;
$arr=[];
fscanf(STDIN, "%d", $n);
$arr = explode(" ", trim(fgets(STDIN)));
$yu = explode(" ", trim(fgets(STDIN)));
for ($i=0; $i < $n; $i++) { 
	if ($arr[$i]<$yu[$i]){
  		$ans += $arr[$i];
  		$yu[$i] -= $arr[$i];
  		if ($yu[$i] > $arr[$i+1]){
  			$ans += $arr[$i+1];
  			$arr[$i+1] = 0;
  		}else{
  			$ans += $yu[$i];
  			$arr[$i+1] -= $yu[$i];
  		}
  	}else{
  		$ans += $yu[$i];
  	}
}

printf("%d", $ans);

Measured memory_bytes: 20980
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()
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; }

int main(){
  int n,a;
  cin >> n >> a;
  n %= 500;
  if(n <= a) YES;
  else NO;
  
}


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

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	int p_min = 1e6;
	int ans = 0;
	for(int i = 0; i<n; i++){
		cin >> p[i];
	}
	for(int i = 0; i<n; i++){
		p_min = min(p_min,p[i]);
		if(p[i] <= p_min){
			ans++;
		}
		//printf("i:%d,p_min:%d,p[i];%d\n",i,p_min,p[i]);
	}
	cout << ans << endl;

	return 0;
}


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

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 111; i <= 999; i += 111)
        {
            if(n <= i)
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65
//おまじない



int main() {

	int n, k;
	int pos[100] = {0};
	int ans = 0;
	cin >> n >> k;

	rep(i, 0, n) {
		cin >> pos[i];
	}


	rep(i, 0, n) {
		ans += min(2 * pos[i], 2 * (k - pos[i]));
	}

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#include <limits.h>

int main(void){
    double a,b,c,d,e,f;
    while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
        double y=0,x=0;
        double g=e*a;
        double h=f*a;
        double i=b*d;
        double j=c*d;
        double k=i-g;
        double l=j-h;
        y=l/k;
        x=(c-b*y)/a;
        printf("%.3lf %.3lf\n",x,y);
    }
    return 0;
}


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

using namespace std;
int main()
{
    int k;
    string s;

    cin>>k>>s;
    if(s.length()<=k)
    {
        cout<<s<<endl;
    }

    else
    {
        for(int i=k;i<k+3;i++)
        {
            s[i]='.';
        }

       for(int j=0;j<k+3;j++)
       {
           cout<<s[j];
       }
    }
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;

int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string  A,B;

    cin >> A >> B;

    
    if ( A.length() > B.length() ) cout << "GREATER" << endl;

    else if ( A.length() < B.length() ) cout << "LESS" << endl;


    else if ( A > B )  cout << "GREATER" << endl;

    else if ( A < B ) cout << "LESS" << endl;

    else if ( A == B ) cout <<"EQUAL" << endl;

    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<string.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1<<29;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

int main() {

	ll n;
	ll t=0;
	cin>>n;

	for(int i=1; i<n; i++){
		t+=i;
	}
	cout<<t<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

ll const INF = 1000000000000000000;
int const I_MAX = 2147483647;
ll const MOD = 1e9 + 7;
int const POW_MAX = 1e5;
int const N_MAX = 1e5;

// nCr
ll po[POW_MAX + 2];
ll mod_pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}
ll mod_inv (ll x) {
  return mod_pow(x, MOD - 2) % MOD;
}
ll comb(int n, int r) {
  if (!po[n]) {
    po[0] = 1;
    FOR(i, 1, n + 1) po[i] = po[i - 1] * i % MOD;
  }
  return (((po[n] * mod_inv(po[r])) % MOD) * mod_inv(po[n - r])) % MOD;
}
// greatest common divisor
ll gcd(ll a, ll b) {
  while (a % b != 0) {
    ll tmp = a;
    a = b;
    b = tmp % b;
  }
  return b;
}

int N;
int ds[N_MAX + 1];

int main() {
  scanf("%d", &N);
  rep(i, N) scanf("%d", &ds[i]);
  sort(ds, ds + N);

  int pa = N / 2;
  int pb = pa - 1;
  printf("%d\n", ds[pa] - ds[pb]);
}


Measured memory_bytes: 768
S = gets.chomp!

lefts = Array.new(S.size + 1, 0)
S.each_char.with_index do |c, i|
  if c == '<'
    lefts[i+1] = lefts[i] + 1
  end
end

rights = Array.new(S.size + 1, 0)

S.each_char.reverse_each.with_index do |c, i|
  if c == '>'
    rights[i+1] = rights[i] + 1
  end
end

rights.reverse!
ans = 0
(S.size + 1).times do |i|
  ans += [lefts[i], rights[i]].max
end

puts ans


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

int main() {
  int hon;
  cin >> hon;
  if(hon % 10 == 3) {
    cout << "bon" << endl;
  } else if(hon % 10 == 0 || hon % 10 == 1 || hon % 10 == 6 ||hon % 10 == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL X;
  cin >> X;
  LL n = 100;
  int cnt=0;
  while (n < X) {
    n *= 1.01;
    cnt++;
  }
  cout<<cnt<<endl;


  return 0;
}


Measured memory_bytes: 3624
def MI():
    return map(int,input().split())
n,m,q=MI()
t=[[0]*(1+n) for _ in range(1+n)]
for i in range(m):
    l,r=MI()
    t[l][r]+=1
for i in range(n):
    for j in range(n):
        t[i+1][j+1]+=t[i+1][j]+t[i][j+1]-t[i][j]

for i in range(q):
    p,q=MI()
    p-=1
    print(t[q][q]-t[q][p]-t[p][q]+t[p][p])


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

#define Max(a,b) max({a,b})
#define Min(a,b) min({a,b})
#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define len(n) n.size()
#define print(n); cout << n << endl;

// s.substr(i,n)

using namespace std;

//char a = 65;

int n,m,a,b,c,cou,co;
double d,k;
char num = 65;
string s,t;


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

    int ans;

    if(m != 100){
        ans = m;
        rep(i,n) ans *= 100;
    }
    else{
        ans = m+1;
        rep(i,n) ans *= 100;
    }

    print(ans)
    
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 200005
 
using namespace std;
typedef long long int ll;
 
int A[SIZE];
int imos1[SIZE];
ll imos2[SIZE];
 
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	int now;
	scanf("%d",&now);now--;
	ll all=0;
	for(int i=1;i<n;i++)
	{
		int to;
		scanf("%d",&to);to--;
		now%=m;
		if(now>to) to+=m;
		all+=to-now;
		imos1[now+1]++;
		imos1[to+1]--;
		imos2[now+1]+=now;
		imos2[to+1]-=now;
		now=to;
	}
	for(int i=1;i<2*m;i++)
	{
		imos1[i]+=imos1[i-1];
		imos2[i]+=imos2[i-1];
	}
	ll ret=all;
	for(int i=0;i<m;i++)
	{
		int a=imos1[i];
		ll b=imos2[i];
		ll nxt=all;
		nxt-=(ll) a*(ll) i-b-a;
		a=imos1[i+m],b=imos2[i+m];
		nxt-=(ll) a*(ll) (i+m)-b-a;
		ret=min(ret,nxt);
	}
	printf("%lld\n",ret);
	return 0;
}

Measured memory_bytes: 4076
#include <bits/stdc++.h>
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define mp(x,y) make_pair(x,y)
#define r(x) read(x)
#define rrr(x,y,z) read(x);read(y);read(z)
#define FOR(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
typedef long long LL;
typedef pair<int,int> pt;
const int N=2e5+5;
const int M=2e3+5;
const int INF=0x7fffffff;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1);
LL n,m;
template<class T>
inline void read(T &x){
    char c; x=1;
    while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
    T res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    x*=res;
}
LL qpow(LL a,LL p){LL res=1;while(p){if(p&1) res=res*a%mod;a=a*a%mod;p>>=1;}return res;}
LL inv(LL x){return qpow(x,mod-2);}
LL hhh(LL a,LL b){
    a++; b++;
    LL res=1;
    FOR(i,1,a){
        res=res*(a+b-i+1)%mod;
    }
    FOR(i,1,a){
        res=res*inv(i)%mod;
    }
    return (res-1+mod)%mod;
}
int main()
{
	LL r1,r2,c1,c2;rrr(r1,c1,r2); r(c2);LL a1=hhh(r2,c2);LL a2=hhh(r1-1,c1-1);LL a3=hhh(r1-1,c2);LL a4=hhh(r2,c1-1);cout<<(a1+a2-a3-a4+mod+mod)%mod<<endl;
    return 0;
}                                                                        

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int W,a,b;
  cin >> W >> a >> b;
  if(b>a+W)
  {
    cout << b-a-W << endl;
  }
  else if(a>b+W)
  {
    cout << a-b-W << endl;
  }
  else
  {
     cout << 0 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
S = list(input())

ops = []
for i in range(2 ** (len(S) -1)):
    op = ["-"] * 3
    for j in range(len(S) - 1):
        if i >> j & 1:
            op[j] = "+"
    ops.append(op)

def fomula(S, op):
    s = list(S)
    count = 1
    for i in range(len(s) - 1):
        s.insert(i+count, op[i])
        count += 1
    fomula = ""
    for k in range(len(s)):
        fomula += s[k]

    return fomula


for i in range(2 ** (len(S) -1)):
    fomul = fomula(S, ops[i])
    if eval(fomul) == 7:
        print(fomul+"=7")
        exit()

Measured memory_bytes: 38256