akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

struct sieve {
  int n;
  vector<int> f, primes;
  sieve(int n) : n(n), f(n+1, 0) {
    /* O(n log log n) */
    f[0] = f[1] = -1;
    for(int i=2; i<=n; i++) {
      if(f[i]) continue;
      primes.push_back(i); f[i] = i;
      for(long long k=(long long)i*i; k<=n; k+=i) if(!f[k]) f[k] = i;
    }
  }
  bool is_prime(int x) {return f[x]==x;}
  template <typename T>
  vector<pair<T,int>> factors(T x) {
    assert((long long)n*n >= x);
    vector<pair<T,int>> fc;
    if( x>n ) {
      /* O(sqrt(x)) */
      for (int p : primes) {
        int c = 0;
        while (x%p == 0) x /= p, ++c;
        if (c != 0) fc.emplace_back(p,c);
      }
      if(x!=1) fc.emplace_back(x,1);
    }
    else {
      /* O(log x) */
      while (x != 1) {
        if (fc.back().first == f[x]) { fc.back().second++; }
        else { fc.emplace_back(f[x], 1); }
        x /= f[x];
      }
    }
    return fc;
  }
};

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

signed main() {
#if 0
  // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A
  int n;
  cin >> n;
  cout << n << ":";
  sieve s(ceil(sqrt(n)));
  auto factors = s.factors(n);
  for(auto f : factors) for(int i=0; i<f.second; i++) cout << " " << f.first;
  cout << endl;

#elif 0
  // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009
  const int n_max = 999999;
  sieve s(n_max);
  vector<int> csum(n_max, 0);
  for(int i=2; i<=n_max; i++)
    csum[i] = csum[i-1] + (s.is_prime(i) ? 1 : 0);

  int n;
  while(cin >> n) cout << csum[n] << endl;

#elif 0
  // https://atcoder.jp/contests/abc149/tasks/abc149_c
  int x;
  cin>>x;

  int p=x;
  while(!is_prime(p)) p++;

  cout << p << endl;
#else
  // https://atcoder.jp/contests/abc169/tasks/abc169_d
  long long N;
  cin >> N;
  sieve s(ceil(sqrt(N)));
  auto factors = s.factors(N);

  int ans = 0;
  for(auto f : factors) {
    int count = f.second;
    int now = 1;
    while(count >= now) {
      ans++;
      count -= now;
      now++;
    }
  }
  cout << ans << endl;
#endif
}


Measured memory_bytes: 7832
#include <iostream>
#include <string>
#define NMAX 36
using namespace std;

void BubbleSort(int n, string *CB);
void SelectiveSort(int n, string *CS);
bool isStable(string *In, string *Out, int n);

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

    string C[NMAX];
    string CB[NMAX];
    string CS[NMAX];
    for (int i=0; i<n; i++) {
        string c;
        cin >> c;
        C[i] = c;
        CB[i] = c;
        CS[i] = c;
    }

    // solve
    BubbleSort(n, CB);
    SelectiveSort(n, CS);

    // output
    for (int i=0; i<n; i++) {
        cout << CB[i];
        if (i == n-1) {
            cout << endl;
        } else cout << " ";
    }

    if ( isStable(C, CB, n) ) {
        cout << "Stable";
    } else cout << "Not stable";
    cout << endl;

    for (int i=0; i<n; i++) {
        cout << CS[i];
        if (i == n-1) {
            cout << endl;
        } else cout << " ";
    }

    if ( isStable(C, CS, n) ) {
        cout << "Stable";
    } else cout << "Not stable";
    cout << endl;
}

void BubbleSort(int n, string *CB) {
    for (int i=0; i<n; i++) {
        for (int j = n-1; j >= i+1; j--) {
            if ( CB[j][1] < CB[j-1][1] ) {
                swap( CB[j], CB[j-1] );
            }
        }
    }
}

void SelectiveSort(int n, string *CS) {
    for (int i=0; i<n; i++) {
        int minj = i;
        for (int j=i; j <= n-1; j++) {
            if ( CS[j][1] < CS[minj][1] ) {
                minj = j;
            }
        }
        swap( CS[i], CS[minj] );
    }
}

bool isStable(string *In, string *Out, int n) {
    for (int i=0; i<n; i++) {
        for (int j = i+1; j<n; j++) {
            for (int a=0; a<n; a++) {
                for (int b = a+1; b < n-1; b++) {
                    if ( In[i][1] == In[j][1] && In[i] == Out[b] && In[j] == Out[a] ) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}


Measured memory_bytes: 3164
#include<stdio.h>

int n, A[50];

int solve(int i, int m){
    if( m == 0 ) return 1;
    if( i >= n ) return 0;
    int res = solve(i + 1, m) || solve(i + 1, m- A[i]);
}

int main() {
  int q, M, i;

  scanf("%d", &n);
  for( i = 0; i < n; i++ ) scanf("%d", &A[i]);
  scanf("%d", &q);
  for( i = 0; i < q; i++ ) {
      scanf("%d", &M);
      if ( solve(0, M) )printf("yes\n");
      else printf("no\n");
  }
  
  return 0;
}


Measured memory_bytes: 2688
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <algorithm>

#define MOD_BIG 1000000007
#define MOD_BIG2 998244353
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;
using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using std::vector;

#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

//////////////////////////////////////



//////////////////////////////////////

int main() {
    
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    int root = 0, num = 0;
    FOR(i, 0, N-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
        if (g[a].size() > num) {
            num = (int)g[a].size();
            root = a;
        }
        if (g[b].size() > num) {
            num = (int)g[b].size();
            root = b;
        }
    }
    std::priority_queue<ll> C;
    FOR(i, 0, N) {
        ll c;
        cin >> c;
        C.push(c);
    }
    vector<ll> ans(N);
    ll val = 0;
    std::queue<int> q;
    q.push(root);
    ans[root] = C.top();
    C.pop();
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        for(auto e: g[v]) {
            if (ans[e] == 0) {
                ans[e] = C.top();
                val += C.top();
                C.pop();
                q.push(e);
            }
        }
    }
    
    cout << val << endl;
    for(auto a: ans) {
        cout << a << " ";
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

vector<int> a, b, c;
ll s = 0LL;
ll a2b[100100];
ll b2c[100100];
ll x[100100];

int main() {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        int x; cin >> x;
        a.push_back(x);
    }
    for(int i = 0; i < N; i++){
        int x; cin >> x;
        b.push_back(x);
    }
    for(int i = 0; i < N; i++){
        int x; cin >> x;
        c.push_back(x);
    }

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

    for(int i = 0; i < N; i++){
        auto itr = upper_bound(b.begin(), b.end(), a[i]);
        ll index = itr - b.begin();
        a2b[i] = index;
    }
    for(int i = 0; i < N; i++){
        auto itr = upper_bound(c.begin(), c.end(), b[i]);
        ll index = itr - c.begin();
        b2c[i] = index;
    }

    for(int i = 0; i < N; i++){
        x[i] = 0;
    }
    for(int i = 0; i < N; i++){
        x[a2b[i]] += 1;
    }
    for(int i = 0; i < N-1; i++){
        x[i+1] += x[i];
    }

    for(int i = 0; i < N; i++){
        s += x[i] * (N - b2c[i]);
    }
    cout << s << endl;

    return 0;
}

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

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for (auto &i : mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template <class T> ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template <class T> istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template <class T> ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n;
    cin >> n;
    vl a(n);
    cin >> a;
    sort(all(a));
    reverse(all(a));
    ll ans = 0;
    ll cnt = 1;
    rep(i, n) {
        if (cnt == n) break;
        ans += a[i];
        cnt++;
        if (cnt == n) break;
        if (i > 0) ans += a[i], cnt++;
    }
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> A(n), B(n);
	for (int i = 0; i < n; ++i) scanf("%d", &A[i]);
	for (int i = 0; i < n; ++i) scanf("%d", &B[i]);
	auto val = [&](int i, int pos) {
		if ((i + pos) & 1) return B[i];
		return A[i];
	};
	const int INF = 1e9;
	vector<vector<int>> dp(1 << n, vector<int>(n, INF));
	for (int i = 1; i < (1 << n); ++i) {
		int t = __builtin_popcount(i);
		for (int j = 0; j < n; ++j) {
			if (!(i & (1 << j))) continue;
			if (t == 1) dp[i][j] = j;
			// j is last among slots 0..t-1.
			int pos = 0;
			for (int k = 0; k < n; ++k) {
				if (i & (1 << k)) continue;
				// Move k to slot t.
				if (val(j, t - 1) <= val(k, t)) {
					dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + pos);
				}
				++pos;
			}
		}
	}
	int ans = INF;
	for (int i = 0; i < n; ++i) {
		ans = min(ans, dp[(1 << n) - 1][i]);
	}
	printf("%d\n", ans == INF ? -1 : ans);
}


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

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a; i<= b; ++i)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define Ld long double

using namespace std;
typedef long long ll;
const int mx = 1000;
int a[mx];

int main(){
    optimize();
    ll d,t,s;
    cin>>d>>t>>s;
    if(t*s >= d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <sstream>
#include <string>
#include <utility>
#include <map>
#include <memory>
#include <set>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>

using namespace std;

struct Node
{
  Node *parent;
  Node *left;
  Node *right;
  int key;
};

class BStree
{
public:
  Node *root;
  Node *nil;
  int solve();
  int print();
  int insert( Node *z );
  int preorder( Node *nd );
  int inorder( Node *nd );
};

int BStree::solve()
{
  int n;
  cin >> n;
  
  string com;
  int d;
  Node *nd;
  
  for ( auto i = 0; i < n; ++i )
    {
      cin >> com;

      if ( com == "print" )
        print();
      else
        {
          cin >> d;
          nd = new Node;
          nd->key = d;
          nd->parent = nil;
          nd->left = nil;
          nd->right = nil;
          insert( nd );
        }
    }
      
  return 0;
}

int BStree::print()
{
  inorder( root );
  cout << endl;
  preorder( root );
  cout << endl;
  return 0;
}

int BStree::insert( Node *z )
{
  Node *y = nil;
  Node *x = root;

  while ( x != nil )
    {
      y = x;
      if ( z->key < x->key )
        x = x->left;
      else
        x = x->right;
    }

  z->parent = y;

  if ( y == nil )
    root = z;
  else if ( z->key < y->key )
    y->left = z;
  else
    y->right = z;
  
  return 0;
}

int BStree::preorder( Node *nd )
{
  if ( nd == nil )
    return 0;

  cout << " " << nd->key;
  preorder( nd->left );
  preorder( nd->right );
  
  return 0;
}

int BStree::inorder( Node *nd )
{
  if ( nd == nil )
    return 0;

  inorder( nd->left );
  cout << " " << nd->key;
  inorder( nd->right );
  
  return 0;
}

int main()
{

  BStree b;

  b.nil = new Node;
  b.nil->parent = b.nil;
  b.nil->left = b.nil;
  b.nil->right = b.nil;
  b.nil->key = -1;

  b.root = b.nil;
  
  b.solve();

  return 0;
}

Measured memory_bytes: 24660
N, W = map(int, input().split())

V = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        V[0].append(v)
    else:
        V[w-w0].append(v)
J = []
for i in range(4):
    F = sorted(V[i], reverse=True)
    G = [0]
    for f in F:
        G.append(f+G[-1])
    J.append(G)

ans = 0
for s0 in range(len(J[0])):
    for s1 in range(len(J[1])):
        for s2 in range(len(J[2])):
            for s3 in range(len(J[3])):
                if s0*w0 + s1*(w0+1) + s2*(w0+2) + s3*(w0+3) > W:
                    continue
                ans = max(ans, J[0][s0]+J[1][s1]+J[2][s2]+J[3][s3])
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const long long INF = (1LL << 60);
using namespace std;

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

    long long a[100005];
    long long sum = 0, cnt = 0, ans = INF;
    rep(i,n) cin >> a[i];

    bool f = 1;
    rep(i,n){
        sum += a[i];
        if(f){
            if(sum <= 0){
                cnt += -sum + 1;
                sum = 1;
            }
            f = 0;
        }else{
            if(sum >= 0){
                cnt += sum + 1;
                sum = -1;
            }
            f = 1;
        }
    }
    ans = min(ans, cnt);
    f = 0;
    sum = 0;
    cnt = 0;
    rep(i,n){
        sum += a[i];
        if(f){
            if(sum <= 0){
                cnt += -sum + 1;
                sum = 1;
            }
            f = 0;
        }else{
            if(sum >= 0){
                cnt += sum + 1;
                sum = -1;
            }
            f = 1;
        }
    }
    ans = min(ans, cnt);
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define LL long long

int n,q;
LL ret=0;
LL tablex[200001],tabley[200001];
bool freex[200001],freey[200001];
int findx,findy;

int main(){
  cin>>n>>q;
  LL fx=n-2,fy=n-2;
  REP(i,200001){
    tablex[i]=n-2;
    tabley[i]=n-2;
    freex[i] = false;
    freey[i] = false;
  }
  findx=n;
  findy=n;
  REP(i,q){
    int qk,coord;
    cin>>qk>>coord;
    if(qk==1){
      FOR(l,coord,n){
        tabley[coord]=0;
        if(freey[l])break;
        freey[l]=true;
        tabley[l]=fx;
        tabley[coord]=0;
      }
      fy = min(fy,(LL)coord-2);
    }else{
      FOR(l,coord,n){
        tablex[coord]=0;
        if(freex[l])break;
        freex[l]=true;
        tablex[l]=fy;
        tablex[coord]=0;
      }
      fx = min(fx,(LL)coord-2);
    }
  }
  FOR(i,2,n){
    if(freex[i])ret+=tablex[i];
    if(freey[i])ret+=tabley[i];
  }
  ret+=fx*fy;
  cout<<ret<<endl;
  return 0;
}


Measured memory_bytes: 7140
import java.util.*;

class Main {
	static int cnt;
	static int[] flag;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] a = new int[M];
		int[] b = new int[M];
		flag = new int[N];
		cnt = 0;
		for (int i=0;i<M;i++) {
			a[i]=sc.nextInt();
			b[i]=sc.nextInt();
		}
		int[][] next = new int[N][N];
		for (int i=0;i<N;i++) {
			for (int j=0;j<N;j++) {
				for (int k=0;k<M;k++) {
					if (a[k]-1==i && b[k]-1==j) {
						next[i][j]=1;
					}
					if (a[k]-1==j && b[k]-1==i) {
						next[i][j]=1;
					}
				}
			}
		}
		flag[0]=1;
		DFS(0,flag,N,M,next);
		System.out.println(cnt);
	}

	static void DFS(int v,int[] flag,int N,int M,int[][] next) {
		boolean bool=false;
		for (int i=0;i<N;i++) {
			if (flag[i]==0) {
				bool = false;
				break;
			}
			if (i==N-1) {
				bool = true;
			}
		}
		if (bool) {
			cnt++;
			return;
		}
		for (int i=0;i<N;i++) {
			if (next[v][i]==1 && flag[i]==0) {
				flag[i]=1;
				DFS(i,flag,N,M,next);
				flag[i]=0;
			} else {
				continue;
			}
		}
		return;
	}
}

Measured memory_bytes: 23252
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

int main() {
  uint32_t N = 0, M = 0;
  std::cin >> N >> M;
  std::vector<uint32_t> A(M);
  for (size_t i = 0; i < M; i++) std::cin >> A[i];

  uint32_t A_sum = std::accumulate(A.begin(), A.end(), 0);
  std::cout << (int)((N >= A_sum) ? (N - A_sum) : -1) << std::endl;

  return 0;
}

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

#define N 1000

int main(){
  int key,i,j,n,A[N];
    scanf("%d",&n);
    if(n>100)exit(1);
    
    for(i=0;i<n;i++){
      scanf("%d",&A[i]);
      printf("%d",A[i]);
      if(i<n-1)printf(" ");
    }
    printf("\n");
for(j=1;j<=n-1;j++){
    key=A[j];
    i=j-1;
    while(i>=0&&A[i]>key){
        A[i+1]=A[i];
        i=i-1;
        A[i+1]=key; 
    }
    for(i=0;i<n;i++){
	  printf("%d",A[i]);
	  if(i<n-1)printf(" ");
        }
	printf("\n");
        
 }
 return 0;
}



Measured memory_bytes: 2760
#!python3

from collections import deque
iim = lambda: map(int, input().rstrip().split())

def resolve():
    K = int(input())

    if K <= 9:
        print(K)
        return

    s1 = "0123456789"
    s2 = { str(i) : s1[i-1:i+2] for i in range(1, 9) }
    s2["0"] = "01"
    s2["9"] = "89"

    dq = deque(s1[1:])
    for i in range(K):
        ans = dq.popleft()

        for c2 in s2[ans[-1]]:
            dq.append(ans + c2)

        if len(dq) + i >= K:
            print(dq[K-i-2])
            return


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 8044
n=int(input())
h=list(map(int,input().split()))
#dp[i]はiに来たときのコストの総和の最小値

dp=[float('inf')]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])+dp[0]

for i in range(2,n):
  dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]), dp[i-1]+abs(h[i-1]-h[i]))

print(dp[n-1])


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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  static map<string, int> cnt;

  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    ++cnt[s];
  }

  int mx = -1;
  for (auto &p : cnt) mx = max(mx, p.second);
  for (auto &p : cnt)
    if (p.second == mx) cout << p.first << '\n';
  return 0;
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int h,w;
	int ans=0;
	cin >>h>>w;
	vector<string>s(h);
	vector<vector<int>>dis(h,Vi(w));
	queue<pair<int,int>>q;
	pair<int,int>at;
	rep(i,h){
		cin>>s[i];
	}
	rep(i,h){
		rep(j,w){
			if (s[i][j] == '#')
			{
				continue;
			}
			rep(I,h){
				rep(J,w){
					dis[I][J]=INF;
				}
			}
			at=mp(i,j);
			dis[i][j]=0;
			q.push(at);
			while (!q.empty()){
				at=q.front();
				q.pop();
				for(int ni=at.F-1;ni<=at.F+1;ni++){
					for(int nj=at.S-1;nj<=at.S+1;nj++){
						if(ni <0 or nj<0 or ni ==h or s[ni][nj]=='#' or nj==w or !((ni==at.F) xor (nj==at.S))){continue;}
						if ( chmin(dis[ni][nj], dis[at.F][at.S] + 1))
						{
							//dis[ni][nj]=dis[at.F][at.S]+1;
							q.push(mp(ni,nj));
						}
					}
				}
			}
			rep(I, h)
			{
				rep(J, w)
				{
				//	clog << dis[I][J] << " ";
					if(dis[I][J]==INF){continue;}
					chmax(ans,dis[I][J]);
					
				}
			//	clog<<endl;
			}
		//	clog << endl;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
#define endl '\n'
#define F first
#define S second
const int MAX_N=1e2+2;
const int MAX_K=1e5+5;
const int MOD=1000000007;

int n,k;
int a[MAX_N];
ll dp[2][MAX_K];

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	bool f=0;
	dp[f^1][k]=1;
	for(int i=0;i<n;i++,f^=1)
	{
		memset(dp[f],0,sizeof(dp[f]));
		for(int j=0;j<=k;j++)
		{
			dp[f][j]=(dp[f][j]+dp[f^1][j])%MOD;
			if(j-a[i]-1>=0) dp[f][j-a[i]-1]=(dp[f][j-a[i]-1]-dp[f^1][j])%MOD;
		}
		for(int j=k;j>=0;j--)
			dp[f][j]=(dp[f][j]+dp[f][j+1])%MOD;
	}
	printf("%lld\n",(dp[f^1][0]%MOD+MOD)%MOD);
	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  double sum = 0;
  for(int i = 0;i<n;i++){
    double x ;
    string u;
    cin >> x >>u;
    if( u == "BTC"){
      sum += 380000*x;
    }
    else{
      sum += x;
    }
  }
  printf("%f",sum);
}

Measured memory_bytes: 256
N,K = [int(i) for i in input().split(" ")]
num = [0]*((10**5)+1)
for i in range(N):
    a_k,b_k = [int(i) for i in input().split(" ")]
    num[a_k] += b_k
for i, v in enumerate(num): # i は index v は 中身
    K = K - v
    if K<=0:
        print(i)
        break

Measured memory_bytes: 5740
#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=1e9+7;
int n,f[N][N],m;char s[N];
int main(){
  scanf("%d%s",&n,s+1);m=strlen(s+1);
  f[0][0]=1;
  for(int i=0;i<n;i++)
	  for(int j=0;j<=i;j++){
		  if(j)f[i+1][j-1]=(f[i+1][j-1]+f[i][j])%mod;
		  else f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
		  f[i+1][j+1]=(f[i+1][j+1]+1ll*f[i][j]*2)%mod;
	  }
  for(int i=1;i<=m;i++)f[n][m]=1ll*f[n][m]*500000004%mod;
  printf("%d\n",f[n][m]);
  return 0;
}


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

int main()
{
    int h1,h2,m1,m2,k;

    cin >> h1 >> m1 >> h2 >> m2 >> k;

    cout << (h2 * 60 + m2) - (h1 * 60 + m1) - k << endl;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define mod2 1000000000
#define mod1 998244353
#define lol ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define F(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define ss second

set <ll> s1;
void primeFactors(ll n)  
{   
    while (n % 2 == 0)  
    {  
        s1.insert(2);  
        n = n/2;  
    }  
    for (ll i = 3; i <= sqrt(n); i = i + 2)  
    {  
        while (n % i == 0)  
        {  
            s1.insert(i);
            n = n/i;  
        }  
    }  
   if (n > 2) s1.insert(n);
}  
int main()
{
    ll n;cin >> n;
    primeFactors(n);
    ll ans = 0;
    for(auto i:s1)
    {
        ll k1 = n;
        ll cnt = 0;
        while(k1%i==0) {cnt++;k1 = k1/i;}
        ll nn = 1;
        while(nn*(nn+1)<=2*(cnt))
        {
            nn++;
        }
        nn--;
        ans = ans + nn;
    }
    cout << ans << endl;
}
    

Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = 1001002003004005006ll;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, W;
	cin >> n >> W;
	ll num = 0;
	vector<vector<int>> p(4);
	rep(i, n) {
		ll w, v;
		cin >> w >> v;
		if (i == 0) num = w, p[0].emplace_back(v);
		else {
			p[w - num].emplace_back(v);
		}
	}
	rep(i, 4) sort(rall(p[i]));
    ll ans = 0;
	rep(i, p[0].size() + 1)rep(j, p[1].size() + 1)rep(k, p[2].size() + 1)rep(l, p[3].size() + 1) {
		ll tmp = 0;
		ll lim = num * (i) + (num + 1) * (j) + (num + 2) * (k) + (num + 3) * (l);
		if (lim > W) continue;
		rep(q, i) tmp += p[0][q];
		rep(q, j) tmp += p[1][q];
		rep(q, k) tmp += p[2][q];
		rep(q, l) tmp += p[3][q];
		maxs(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}

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

using ll = long long;
using std::abs, std::min, std::max;
const int maxn = 1e5 + 3;

struct dmt {
    ll a[maxn * 2]; int l;
    void add(const ll &x) {
        a[l++] = x;
    }
    void init() {
        std::sort(a, a + l);
        l = std::unique(a, a + l) - a;
    }
    void clear() {
        l = 0;
    }
    int query(const ll &x) {
        return std::lower_bound(a, a + l, x) - a;
    }
} dm, dmb;
struct fenwick {
    ll a[maxn]; int l;
    void clear(int x) {
        l = x;
        memset(a, 0, sizeof(*a) * (l + 1));
    }
    void add(int x, const ll &y) {
        for(int i = std::max(1, x + 1); i <= l; i += i & -i)
            a[i] += y;
    }
    ll query(int x) {
        ll ans = 0;
        for(int i = std::min(x + 1, l); i > 0; i -= i & -i)
            ans += a[i];
        return ans;
    }
} fw;
struct pt {
    ll x, y, z;
} d[maxn];
int dl;
ll solve2dcnt(int l, int r, const ll &qz) {
    dm.clear();
    for(int i = l; i < r; ++i) {
        dm.add(d[i].x);
        dm.add(d[i].x - 1);
    }
    dm.init();
    for(int i = l; i < r; ++i)
        d[i].x = dm.query(d[i].x);
    fw.clear(dm.l);
    ll ans = 0;
    std::sort(d + l, d + r, [](const pt &u, const pt &v) {
        return u.y < v.y;
    });
    for(int i = l, j = l; i < r; ++i) {
        while(j < r && d[j].y < d[i].y) {
            // if(d[j].z < qz)
                fw.add(d[j].x, 1);
            j += 1;
        }
        // if(d[j].z >= qz)
            ans += fw.query(d[i].x - 1);
    }
    return ans;
}
ll solve3dcnt(ll zl, ll zr, int l, int r) {
    if(r - l <= 0 || zr - zl <= 0)
        return 0;
    ll zmid = (zl + zr) / 2;
    ll ans = 0;
    ans += solve2dcnt(l, r, zmid);
    int mid = std::partition(d + l, d + r, [zmid](const pt &u) {
        return u.z < zmid;
    }) - d;
    ans += solve3dcnt(zl, zmid, l, mid);
    ans += solve3dcnt(zmid, zr, mid, r);
    return ans;
}

int n, a[maxn];

bool check(int x) {
    dl = 0;
    d[dl++] = {0, 0, 0};
    for(int i = 0; i < n; ++i) {
        if(a[i] <= x)
            d[dl] = {dl, d[dl - 1].y + 1, 0};
        else
            d[dl] = {dl, d[dl - 1].y - 1, 0};
        dl += 1;
    }
    ll ans = solve2dcnt(0, dl, 0);
    return ans >= (n + 1ll) * (ll)(n) / 2ll / 2ll + 1ll;
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        dmb.add(a[i]);
    }
    dmb.init();
    int l = 0, r = dmb.l;
    while(r - l > 1) {
        int mid = (l + r) / 2;
        if(check(dmb.a[dmb.l - 1 - mid]))
            l = mid;
        else
            r = mid;
    }
    printf("%lld\n", dmb.a[dmb.l - 1 - l]);
    return 0;
}

Measured memory_bytes: 9596
lines = []
while line = gets.chomp
    break if line == "END_OF_TEXT"
    lines << line
end

cursor_y, cursor_x = 0, 0
buffer = nil
while true
    line = gets.chomp
    case line
    when "a"
        cursor_x = 0
    when "e"
        cursor_x = lines[cursor_y].length
    when "p"
        cursor_y -= 1 if cursor_y > 0
        cursor_x = 0
    when "n"
        cursor_y += 1 if cursor_y < lines.length - 1
        cursor_x = 0
    when "f"
        if cursor_x < lines[cursor_y].length
            cursor_x += 1
        else
            if cursor_y < lines.length - 1
                cursor_y += 1
                cursor_x = 0
            end
        end
    when "b"
        if cursor_x > 0
            cursor_x -= 1
        else
            if cursor_y > 0
                cursor_y -= 1
                cursor_x = lines[cursor_y].length
            end
        end
    when "d"
        if cursor_x < lines[cursor_y].length
            lines[cursor_y][cursor_x, 1] = ""
        else
            if cursor_y < lines.length - 1
                lines[cursor_y] += lines[cursor_y + 1]
                lines.delete_at(cursor_y + 1)
            end
        end
    when "k"
        if cursor_x < lines[cursor_y].length
            buffer = lines[cursor_y][cursor_x..-1]
            lines[cursor_y] = lines[cursor_y][0...cursor_x]
        else
            if cursor_y < lines.length - 1
                lines[cursor_y] += lines[cursor_y + 1]
                lines.delete_at(cursor_y + 1)
                buffer = ""
            end
        end
    when "y"
        if buffer == ""
            temp = lines[cursor_y][cursor_x..-1]
            lines[cursor_y] = lines[cursor_y][0...cursor_x]
            cursor_y += 1
            cursor_x = 0
            lines[cursor_y, 0] = temp
        elsif !buffer.nil?
            lines[cursor_y][cursor_x, 0] = buffer
            cursor_x += buffer.length
        end
    when "-"
        break
    end
end
lines.each{|line| puts line}



Measured memory_bytes: 6892
#include <bits/stdc++.h>
#define ll long long int
#define r(a, b) for(ll i = a; i < b; i++)
#define pb push_back
using namespace std;
#define mod 998244353
const long long int INF = 1e10;
vector<ll>v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,a;
    cin>>n>>a;
    ll arr[n];
    for(ll x=0; x<n; x++){
        cin>>arr[x];
    }
    sort(arr,arr+n);
    if(a<n){
        ll sum=0;
        for(ll x=0; x<n-a;x++){
            sum+=arr[x];
        }
        cout<<sum<<"\n";
    }
    else{
        cout<<"0\n";
    }
    return 0;
}



Measured memory_bytes: 1792
import java.util.*;
class Main{
	public static void main(String[]z){
		Scanner cin=new Scanner(System.in);
		int y,m,d;
		for(y=cin.nextInt();cin.hasNext();System.out.println(196471-(--y)*195-y/3*5-(--m)*20+(y%3!=2?m/2:0)-d)){y=cin.nextInt();m=cin.nextInt();d=cin.nextInt();}
	}
}

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
template<class T>
inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}
template<class T>
inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

int N, M;

int main(){
    cin >> N >> M;
    cout << (N==M?"Yes":"No") << endl;
    return 0;
}

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

int main()
{
    int n, x, t;
    cin >> n >> x >> t;
    int ans;
    if (n % x == 0)
    {
        ans = n / x * t;
    }
    else
    {
        ans = (n / x + 1) * t;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
const ll LINF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
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; }
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  int a, b;
  cin >> a >> b;
  string s = string(b, a+'0');
  string t = string(a, b+'0');
  cout << min(s,t) << endl;
  return 0;
}

Measured memory_bytes: 256
#https://atcoder.jp/contests/agc008/submissions/15248942
import sys
import math

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N,D = inm()
point = []
for i in range(N):
    X,Y = inm()
    point.append((X,Y))

ans = 0
for p in point:
    d = math.sqrt(p[0]*p[0] + p[1]*p[1])
    if d <= D:
        ans += 1

print(ans)



Measured memory_bytes: 35988
program main
  implicit none
  integer(8) i, N, M, K, ans, AllA, ta, tb, na, nb, j
  integer(8),allocatable :: A(:),B(:)
  read(*, *) N, M, K
  allocate(A(N))
  allocate(B(M))
  read(*, *) (A(i), i = 1,N)
  read(*, *) (B(i), i = 1,M)
  ans = 0
  tb = 0
  !全てBのとき
  do i = 1,M
    if (tb + B(i) > K) then
      exit
    else 
      tb = tb + B(i)
      ans = ans + 1
    end if
  end do
  !Aを一冊づつ増やす
  ta = 0
  tb = sum(B(1:ans))
  na = 0
  nb = ans
  AllA = 0
  do i = 1,N
    na = na + 1
    ta = ta + A(na)
    ALLA = K - ta
    if (ta > K) then
      exit
    end if
    !nb = 0
    !tb = 0
    do
      if (tb <= ALLA) then
        exit
      else
        tb = tb - B(nb)
        nb = nb - 1
        !tb = tb + B(j)
      endif
    enddo
    if (ans < na + nb) then
      ans = na + nb
    end if
  enddo
  write(*, *) ans
end program main


Measured memory_bytes: 6120
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            long[] dArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            long healing = 0;

            for (long f = 0; f < N; f++)
            {
                for (long p = 0; p < N; p++)
                {
                    if (p!=f)
                    {
                        healing += dArray[f] * dArray[p];
                    }
                }
            } 
            Console.WriteLine(healing/2);
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)

using namespace std;


ll solve(ll b, vector<ll>& a){
    ll n = a.size();
    ll sum = 0;
    rep(i, n) sum += abs(a[i]-(b+i+1));
    return sum;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    ll l = -1e10;
    ll r = 1e10;
    
    while(100 <= r-l){
        ll w = (r-l)/3;
        ll lls = solve(l+w, a);
        ll rrs = solve(l+2*w, a);

        if(lls < rrs) r = l+2*w;
        else          l = l+w;
    }
    
    ll minn = solve(0, a);
    for(ll b = l; b <= r; b++){
        minn = min(minn, solve(b, a));
    }

    cout << minn << endl;    
    
    return 0;
}


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

int main() {
  int N;
  bool isFour = false;
  cin >> N;
  for (int i = 0; i < N; i++){
    string S;
    cin >> S;
    if (S == "Y"){
      isFour = true;
    }
  }
  if(isFour){
    cout << "Four" << endl;
  }
  else{
    cout << "Three" << endl;
  }
}


Measured memory_bytes: 256
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
C = [int(input()) for i in range(n)]
pairs = [-1]*(n+1)
data = [-1]*(2*10**5+1)
for i,ci in enumerate(C):
  if data[ci] != -1 and abs(i-data[ci]) != 1:
    pairs[data[ci]] = i
  data[ci] = i
imos = [0] * (n+1)
for i in range(n-1,-1,-1):
  # ペアを持たないとき
  if pairs[i] == -1:
    imos[i] = imos[i+1]
    # print(i,imos[i],imos[i+1])
  else:
    j = pairs[i]
    imos[i] = imos[i+1] + imos[j] + 1
    imos[i] %= mod
  # ans += imos[i] + imos[j]
  # ans %= mod
  # imos[i-1] += imos[i]
print((imos[0]+1)%mod)
# print((ans+1)%mod)
# print(imos)

Measured memory_bytes: 84144
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
#from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
a, b = [list(i) for i in zip(*ab)]
a.sort()
b.sort()
if n%2==1:
    ma=a[(n-1)//2]
    mb=b[(n-1)//2]
    print(mb-ma+1)
else:
    ma=a[n//2]+a[n//2-1]
    mb=b[n//2]+b[n//2-1]
    print(mb-ma+1)

Measured memory_bytes: 124884
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    n = int(input())

    num = []
    for i in range(2, 55556):
        if i % 5 == 1 and is_prime(i):
            num.append(i)
    print(*num[:n])


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9276
#include<bits/stdc++.h>
using namespace std;
#define F(n) for(int i=0;i<n;++i)
#define Fj(n) for(int j=0;j<n;++j)
const int MOD=1e9+7;

int main(){
    long x;
    cin >> x;
    long xx=x%100;
    long cnt=0;
    for(int i=5;i>=1;--i){
        while(xx>=i){
            xx-=i;
            ++cnt;
        }
    }
    if(cnt*100<=x-xx) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
fun main(array: Array<String>){
    val (k, n) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    var list = mutableListOf<Int>()
    for (i in 0 until n-1){
        list.add(a[i+1] - a[i])
    }
    var max = k + a[0] - a[n-1]
    if(max <= list.max()!!){
        max = list.max()!!
    }
    print(k - max)
}

Measured memory_bytes: 82912
N = int(input())
P = []
for i in range(N):
  s, t = input().split()
  S = [s, int(t)]
  if 0 < i:
    S[1] += P[-1][1]
  P.append(S)
D = {}
for s, t in P:
  D[s] = t
print(P[-1][1] - D[input()])

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

int main(void){
    ll a,b;
    cin>>a>>b;
    if(a==b) cout<<a<<endl;
    else if(a%2==1&&b%2==1){
        if((b-a)%4==0) cout<<ll(a)<<endl;
        if((b-a)%4==2) cout<<ll(a^b^(b-1))<<endl;
    }
    else if(a%2==1&&b%2==0){
        if((b-a)%4==1) cout<<ll(a^b)<<endl;
        if((b-a)%4==3) cout<<ll(a^b^(b-1)^(b-2))<<endl;
    }
    else if(a%2==0&&b%2==1){
        if((b-a+1)%4==0) cout<<0<<endl;
        if((b-a+1)%4==2) cout<<1<<endl;
    }
    else if(a%2==0&&b%2==0){
        if((b-a)%4==0) cout<<b<<endl;
        if((b-a)%4==2) cout<<ll(b^(b-1)^(b-2))<<endl;
    }
}

Measured memory_bytes: 256
# coding: UTF-8

alphabets = "abcdefghijklmnopqrstuvwxyz"

while input = gets
   input.chomp!
   26.times.with_index do |i|
       output = input.tr("a-z", alphabets.split("").rotate(i).join)
       if output =~ /th(e|is|at)/
         puts output
         break
       end
   end
end

Measured memory_bytes: 6164
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	vector <int> h(n);
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	vector <int> dp(n,0);
	for(int i=1;i<n;i++)
	{
		int mini = 1000000010;
		for(int j=1;((j<=k)&&((i-j)>=0));j++)
		{
			int val = abs(h[i]-h[i-j]) + dp[i-j];
			mini = min(mini,val);
		}
		dp[i] = mini;
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

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

  int M; cin >> M;

  cout<<24+24-M<<endl;

    return 0;
}


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

int main() {
    int N;
    int cnt = 0;
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        string s = to_string(i);
        if(s.size() == 1 || s.size() == 3 || s.size() == 5)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define lli long long int
#define d double
#define mod 1000000007
#define mx 100001
using namespace std;
bool vis[mx];
void dfs(vector<list<int>>&adjList,vector<vector<lli>>&dp,int root){
	vis[root]=true;
    if(dp[root][0]!=-1 && dp[root][1]!=-1) return;
	for(int child : adjList[root]){
	     if(!vis[child]) dfs(adjList,dp,child);
	}
	lli black=1,white=1;
	for(int child : adjList[root]){
		 if(dp[child][1]==-1) continue;
	     black=((black%mod)*(dp[child][1]%mod))%mod;
	     white=((white%mod)*(((dp[child][0]%mod)+(dp[child][1]%mod)))%mod)%mod;
	}
	dp[root][0]=black;
	dp[root][1]=white;
	
}
int main() {
	FIO;
	int n;
	cin>>n;
	vector<list<int>> adjList(n+1);
	vector<int> degree(n+1,0);
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		adjList[x].push_back(y);
		adjList[y].push_back(x);
		degree[x]++;
		degree[y]++;
	}
	memset(vis,false,sizeof(vis));
	vector<vector<lli>> dp(n+1,vector<lli>(2,-1));
	int root=-1,deg=INT_MIN;
	for(int i=1;i<=n;i++){
		if(degree[i]==1){
			dp[i][0]=1;
			dp[i][1]=1;
		}
		if(degree[i]>deg){
			deg=degree[i];
			root=i;
		}
	}
	dfs(adjList,dp,root);
	lli ans=((dp[root][0]%mod)+(dp[root][1])%mod)%mod;
	cout<<ans<<endl;
}

Measured memory_bytes: 19584
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <deque>

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

int main() {

	int a;
	string s;
	cin >> a >> s;

	if (a >= 3200)
		cout << s;
	else
		cout << "red";

	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
using namespace std;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll fac(ll a) { return a > 1 ? fac(a - 1) * a : 1; }
bool echeck(ll a) { return a % 2 == 0 ? 1 : 0; }
ll comb(ll n, ll m){
  ll tmp = 1;
  for(int i = n; i >= n - m + 1; i--){
    tmp *= i;
  }
  ll temp = 1;
  for(int i = 1; i <= m; i++){
    temp *= i;
  }
  return tmp / temp;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  int n;
  cin >>n;
  vector<int>v(n);
  rep(i,n)cin >> v[i];
  ll ans = 0;
  rep(i,n)ans += v[i] - (i+1);
  cout << ans << endl;
  return 0;
} 


Measured memory_bytes: 3156
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
    public static void Main()
    {
        int a = GetInt();
        int b = GetInt();
        int c = GetInt();
        var n = Math.Max(a, Math.Max(b, c));
        int sum = a + b + c;
        if (n == sum - n)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

public static class MyIO
{
    private static string[] args = null;
    private static int num = -1;
    private static int used = -1;

    private static string getArg()
    {
        if (used == num)
        {
            args = Console.ReadLine().Split(' ');
            num = args.Length;
            used = 0;
        }
        return args[used++];
    }

    public static int GetInt() { return int.Parse(getArg()); }
    public static long GetLong() { return long.Parse(getArg()); }
    public static double GetDouble() { return double.Parse(getArg()); }
    public static string GetString() { return getArg(); }
}


Measured memory_bytes: 11092